POJ 3281 Dining(最大流+拆点)

题目链接:http://poj.org/problem?id=3281

题目大意:
农夫为他的 N (1 ≤ N ≤ 100) 牛准备了 F (1 ≤ F ≤ 100)种食物和 D (1 ≤ D ≤ 100) 种饮料。每头牛都有各自喜欢的食物和饮料,
而每种食物或饮料只能分配给一头牛。最多能有多少头牛可以同时得到喜欢的食物和饮料?

解题思路:
令st=0为源点,en=f+2*n+1为汇点,
st向每种食物建流量为1的边,
每种食物向喜欢它的牛(拆点1)建流量为1的边,
眉头牛的拆点之间建流量为1的边,
每头牛(拆点2)向它喜欢的饮料建流量为1的边,
每种饮料向en建流量为一的边。
注意,一定要将牛拆点,如果一头牛只用一个点然后连接饮料和食物,会导致一头牛同时消耗多种食物和饮料。
这个自己画图模拟一下就能理解了。

代码

 /*
此题需要对奶牛进行拆点,左边食物(水),中间奶牛1,奶牛2,右边水(食物)
拆点是为了限制奶牛只能吃一份食物和谁,若不对奶牛进行拆点,则一头奶牛可能会吃多份食物和水
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<vector>
#define LL long long
#define pii pair<int,int>
#define pll pair<long long,long long>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define per(i,a,b) for(int i=a;i>=b;i--)
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
#define bug cout<<"aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"<<endl;
#define bugc(_) cout << (#_) << " = " << (_) << endl;
using namespace std;
const int N=1e6+;
const int M=1e6+;
const int INF=0x3f3f3f3f; struct node{
int to,next,flow;
}edge[M*]; int cnt,st,en;
int head[N],dep[N]; void init(){
cnt=;
memset(head,,sizeof(head));
} void link(int u,int v,int flow){
edge[cnt]=node{v,head[u],flow};
head[u]=cnt++;
edge[cnt]=node{u,head[v],};
head[v]=cnt++;
} int bfs(){
memset(dep,,sizeof(dep));
dep[st]=;
queue<int>q;
q.push(st);
while(!q.empty()){
int u=q.front();
q.pop();
for(int i=head[u];i;i=edge[i].next){
node t=edge[i];
if(t.flow&&!dep[t.to]){
dep[t.to]=dep[u]+;
q.push(t.to);
}
}
}
return dep[en];
} int dfs(int u,int fl){
if(u==en) return fl;
int tmp=;
for(int i=head[u];i&&fl;i=edge[i].next){
node &t=edge[i];
if(t.flow&&dep[t.to]==dep[u]+){
int x=dfs(t.to,min(t.flow,fl));
if(x>){
t.flow-=x;
edge[i^].flow+=x;
tmp+=x;
fl-=x;
}
}
}
if(!tmp) dep[u]=-;
return tmp;
} int dinic(){
int ans=;
while(bfs()){
while(int d=dfs(st,INF)){
ans+=d;
}
}
return ans;
} int main(){
int n,f,d;
while(~scanf("%d%d%d",&n,&f,&d)){
init();
st=,en=f+*n+d+;
for(int i=;i<=n;i++){
int t1,t2;
scanf("%d%d",&t1,&t2);
for(int j=;j<=t1;j++){
int x;
scanf("%d",&x);
link(x,i+f,);
}
for(int j=;j<=t2;j++){
int x;
scanf("%d",&x);
link(i+f+n,x+f+*n,);
}
}
for(int i=;i<=f;i++) link(st,i,);
for(int i=;i<=n;i++) link(i+f,i+f+n,);
for(int i=;i<=d;i++) link(i+f+*n,en,);
printf("%d\n",dinic());
}
return ;
}
上一篇:大厂0距离:网易 Linux 运维工程师面试真题,内含答案


下一篇:第18讲——string类