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 |
百度了下,构图有点大问题,可又给WA掉了两次要改成两排牛, 这个我接受。。 且容量改为1,牛到食物那里写INT——MAX不行吗,非得1吗?? #include<stdio.h> #include<iostream> #include<string.h> #include<queue> #define intmax 200000000 #define arr 405 using namespace std; int N,F,D,S,T; int pre[arr],flow[arr],map[arr][arr]; int BFS() { int i,v,u; for(i=S;i<=T;i++) pre[i]=-1,flow[i]=intmax; //memset(pre,-1,sizeof(pre)); //memset(flow,intmax,sizeof(flow)); //如果用上面那两行的话就出不了结果; pre[S]=0; queue<int>que; que.push(S); while(!que.empty()) { v=que.front(); que.pop(); for(u=1;u<=T;u++) { if(pre[u]!=-1||map[v][u]==0) continue; pre[u]=v; flow[u]=min(flow[v],map[v][u]); que.push(u); } } if(flow[T]==intmax) return -1; else return flow[T]; } int EK() { int temp,now,last,ans=0; while(1) { temp=BFS(); if(temp==-1) break; ans+=temp; now=T; while(now!=S) { last=now; now=pre[now]; map[now][last]-=temp; map[last][now]+=temp; } } return ans; } int main() { int i,j,num_F,num_D,t; while(cin>>N>>F>>D) //N+F+D<=300; { S=0; T=N+F+D+1; memset(map,0,sizeof(map)); for(i=1;i<=F;i++) map[S][i]=1; for(i=1;i<=D;i++) map[i+F+N][T]=1; for(i=1;i<=N;i++) { scanf("%d%d",&num_F,&num_D); for(j=1;j<=num_F;j++) { scanf("%d",&t); map[t][i+F]=1; } for(j=1;j<=num_D;j++) { scanf("%d",&t); map[i+F+N][t+F+N+N]=1; } } for(i=1+F;i<=N+F;i++) map[i][i+N]=1; int ans=EK(); cout<<ans<<endl; } } /* 4 3 3 2 2 1 2 3 1 2 2 2 3 1 2 2 2 1 3 1 2 2 1 1 3 3 Sample Output 3 */ Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator