| ||||||||||
| 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