329ms。构图题, 自己建源点汇点,将源点连接所有的食物,将一头牛拆成两个点。牛i-1,牛i-2,将食物与牛i-1连,然后所有的牛i,连接牛i-1和牛i-2,将牛i-2于饮料相连。最后将所有的饮料与汇点相连。
构图就像这样: 源点s-->食物F-->牛1-->牛2-->饮料D-->汇点t
将牛拆成两个点并且放在中间就可以同时连接食物和饮料。然后牛的两个节点之间连边,容量为1. 食物及饮料读数据于牛1,牛2相连。
#include
#include //EK()算法。时间复杂度(VE^2)
#include
#include
using namespace std;
const int maxn = 500;
const int INF = 0x3fffffff;
int N,F,D;
int Fi[maxn];
int Di[maxn];
int g[maxn][maxn];
int flow[maxn],pre[maxn];
bool vis[maxn];
int n;
int bfs(int s,int e){
memset(pre,-1,sizeof(pre));
memset(vis,false,sizeof(vis));
queue q;
vis[s] = true;
for(int i=1;i<=n;i++)
flow[i]=INF;
q.push(s);
while(!q.empty()){
int now = q.front();
q.pop();
if(now==n) break;
for(int i=1;i<=n;i++){ //寻找增广路最小流量
if(!vis[i]&&g[now][i]>0){
vis[i] = true;
flow[i] = min(flow[now],g[now][i]);
pre[i] = now;
q.push(i);
}
}
}
if(!vis[e]|| e==1) //找不到完整的增广路or源点汇点重合
return -1;
else
return flow[e];
}
int EK(int s,int e){
int temp,d,res,maxflow;
maxflow = 0;
while((d=bfs(s,e))!=-1){
maxflow += d;
temp=n;
while(temp!=1){
res = pre[temp];
g[res][temp]-=d; //正向边
g[temp][res]+=d; //反向边
temp = res;
}
}
return maxflow;
}
int main(){
memset(g,0,sizeof(g));
memset(flow,0,sizeof(flow));
cin>>N>>F>>D;
n = 1 + F + N + N + D + 1;
for(int i = 1; i <= F; i++)
{
g[1][i+1] = 1;
}
for(int i = 1; i<= D; i++)
{
g[1+F+N+N+i][n] = 1;
}
for(int i = 1; i <= N; i++)
{
g[1+F+i][1+F+N+i] = 1;
}
int nf,nd;
for(int i = 1; i <= N; i++)
{
cin>>nf>>nd;
int x;
while(nf--)
{
cin>>x;
g[1+x][1+F+i] = 1;
}
while(nd--)
{
cin>>x;
g[1+F+N+i][1+F+N+N+x] = 1;
}
}
cout< return 0;
}