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 |
大牛们帮忙看看,我第一个用邻接矩阵过了,第二个改用vector做邻接表,死活也WA,第一道 #include<iostream> #define inf 1000000000 using namespace std; int map[550][550]; int f[550][550]; int N,F,D; int food[110],drink[110]; int fl,dl; int S,T; int pre[550]; int que[550]; int d[550]; int ans; __inline int min(int x,int y) { return x<y?x:y; } void slove() { int i,j,p,q,now,next; ans=0; memset(f,0,sizeof(f)); while(1) { p=0; q=1; for(i=1;i<=T;i++) d[i]=inf; for(i=1;i<=T;i++) pre[i]=0; pre[S]=S; que[q]=S; while(p<q && pre[T]==0) { p++; now=que[p]; for(i=1;i<=T;i++) { if (map[now][i] && !pre[i] && f[now][i]!=map[now][i]) { que[++q]=i; pre[i]=now; d[i]=min(d[now],map[now][i]-f[now][i]); } if (!pre[i] && f[i][now]>0) { que[++q]=i; pre[i]=-now; d[i]=min(d[now],f[i][now]); } } } if (pre[T]==0) break; for(i=T;i!=S;) { if (pre[i]>0) { f[pre[i]][i]+=d[T]; i=pre[i]; } else { f[i][-pre[i]]-=d[T]; i=-pre[i]; } } ans+=d[T]; } printf("%d\n",ans); } int main() { int i,j,k; //freopen("dining.10.in","r",stdin); scanf("%d %d %d",&N,&F,&D); memset(map,0,sizeof(map)); for(i=1;i<=N;i++) map[F+i][F+N+i]=1; for(i=1;i<=N;i++) { scanf("%d %d",&fl,&dl); for(j=1;j<=fl;j++) scanf("%d",&food[j]); for(j=1;j<=dl;j++) scanf("%d",&drink[j]); for(j=1;j<=fl;j++) map[food[j]][F+i]=1; for(j=1;j<=dl;j++) map[F+N+i][F+2*N+drink[j]]=1; } S=2*N+F+D+1; T=S+1; for(i=1;i<=F;i++) map[S][i]=1; for(i=1;i<=D;i++) map[2*N+F+i][T]=1; slove(); return 0; } 第二道 #include<iostream> #include<vector> #define inf 1000000000 using namespace std; typedef struct { int num,v; }node; vector<node> map[550]; //int map[550][550]; int f[550][550]; int N,F,D; int food[110],drink[110]; int fl,dl; int S,T; int pre[550]; int que[550]; int d[550]; int ans; __inline int min(int x,int y) { return x<y?x:y; } void slove() { int i,j,p,q,now,next; ans=0; memset(f,0,sizeof(f)); while(1) { p=0; q=1; for(i=1;i<=T;i++) d[i]=inf; for(i=1;i<=T;i++) pre[i]=0; pre[S]=S; que[q]=S; while(p<q && pre[T]==0) { p++; now=que[p]; for(i=0;i<map[now].size();i++) { next=map[now][i].num; if (!pre[next] && f[now][next]!=map[now][i].v) { que[++q]=next; pre[next]=now; d[next]=min(d[now],map[now][i].v-f[now][next]); } if (!pre[next] && f[next][now]>0) { que[++q]=next; pre[next]=-now; d[next]=min(d[now],f[next][now]); } } } if (pre[T]==0) break; for(i=T;i!=S;) { if (pre[i]>0) { f[pre[i]][i]+=d[T]; i=pre[i]; } else { f[i][-pre[i]]-=d[T]; i=-pre[i]; } } ans+=d[T]; } printf("%d\n",ans); } int main() { int i,j,k; node temp; //freopen("dining.10.in","r",stdin); scanf("%d %d %d",&N,&F,&D); //memset(map,0,sizeof(map)); for(i=0;i<=520;i++) map[i].clear(); for(i=1;i<=N;i++) { temp.num=F+N+i; temp.v=1; map[F+i].push_back(temp); } for(i=1;i<=N;i++) { scanf("%d %d",&fl,&dl); for(j=1;j<=fl;j++) scanf("%d",&food[j]); for(j=1;j<=dl;j++) scanf("%d",&drink[j]); for(j=1;j<=fl;j++) { temp.num=F+i; temp.v=1; map[food[j]].push_back(temp); } for(j=1;j<=dl;j++) { temp.num=F+2*N+drink[j]; temp.v=1; map[F+N+i].push_back(temp); } } S=2*N+F+D+1; T=S+1; for(i=1;i<=F;i++) { temp.num=i; temp.v=1; map[S].push_back(temp); } for(i=1;i<=D;i++) { temp.num=T; temp.v=1; map[2*N+F+i].push_back(temp); } slove(); return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator