Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
用拓扑排序怎么错了,找不出来啊,求教TT,求改#include <iostream> #include <stdio.h> #include <string.h> #include <vector> using namespace std; const int maxn=10005; vector<int> map[maxn]; int in[maxn]; int step[maxn]; int used[maxn]; int ff[maxn]; int a[maxn]; int father[maxn]; int N,u,cnt_zero,sum; void Init() { for(int i=1 ; i <=N ; i++) father[i]=i; memset(step,0,sizeof(step)); memset(in,0,sizeof(in)); memset(used,0,sizeof(used)); cnt_zero=sum=0; } int find_(int x) { if(x==father[x]) return x; return father[x]=find_(father[x]); } void Union(int x,int y) { x=find_(x); y=find_(y); if(x!=y) father[x]=y; } void find_dz(int ii) { int i; u=0; for(i=1 ; i <= N ; i++) { if(in[i]==0 && used[i]==0 && find_(i)==ii ) { step[u++]=i; cnt_zero++; } } if(u!=0) { int mm=-1; for(i=0 ; i < u ; i++) { if(a[step[i]]>mm) mm=a[step[i]]; } if(mm!=-1) { sum+=mm; } } } void cut(int v) { used[v]=1; for(int i=0 ; i < map[v].size() ; i++) { in[map[v][i]]--; } } void topsort(int ii) { int i,j; for(i=1; i <= N ; i++) { find_dz(ii); for(j=0; j < u ; j++) { cut(step[j]); } } } int main() { int i,n,t,j,m; while(scanf("%d",&N)!=EOF) { Init(); for(i=1; i <= N ; i++) { map[i].clear(); scanf("%d%d",&t,&n); a[i]=t; for(j=0; j<n; j++) { scanf("%d",&m); Union(i,m); map[m].push_back(i); in[i]++; } } int minn=-1; for(i=1 ; i <= N ; i++) { sum=0; if(father[i]==i) { topsort(i); if(sum>minn) minn=sum; } } for(i=1 ; i <= N ; i++) if(minn<a[i]) minn=a[i]; printf("%d\n",minn); } return 0; } /* 5 4 0 2 1 1 2 1 2 3 0 5 1 4 */ Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator