POJ 3281(dinic)

本文主要是介绍POJ 3281(dinic)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

 

题目大意：n头牛，f种食物，d种饮料，然后给出每头牛想吃的食物和饮料，问如果每只牛选一个自己喜欢的食物和饮料，而且每个食物和饮料只能被选一次，问最多能让多少头牛满意

 

题目思路：这道题有两个限制条件：1、每种食物和饮料只能被选一次。2、每头牛只能选一个喜欢的食物和一个喜欢的饮料。考虑网络流建边。我们把整张图分成三个部分，第一个部分是食物，然后中间是牛，第三个部分是饮料，而牛应该拆成两部分，分成左牛和右牛，然后如果一个牛喜欢多个食物，就让左牛跟这多个食物连起来，然后左牛跟自己对应的右牛连接，这条边容量为1，这样能够保证每头牛只选一个喜欢的食物，然后右牛再跟喜欢的多个饮料连起来，由于流量只有1，所以不用担心他流多个饮料，也就保证了只能选一个食物。然后我们建立一个超级源点和超级汇点，超级源点跟每个食物相连，每个饮料跟超级汇点相连，容量为1，这样就能保证每个食物和每个饮料只能被选一次。

 

献上灵魂画师的丑图：

以下是代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define inf 0x3f3f3f3f
#define ll 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 MOD 998244353
const int MAXN = 2010;
const int MAXM=1200010;
struct Edge{int to,next,cap,flow;
}edge[MAXM];
int tol;
int head[MAXN];
void init(){tol=0;memset(head,-1,sizeof(head));
}
void addedge(int u,int v,int w,int rw=0){edge[tol].to=v;edge[tol].cap=w;edge[tol].flow=0;edge[tol].next=head[u];head[u]=tol++;edge[tol].to=u;edge[tol].cap=rw;edge[tol].flow=0;edge[tol].next=head[v];head[v]=tol++;
}
int Q[MAXN];
int dep[MAXN],cur[MAXN],sta[MAXN];
bool bfs(int s,int t,int n){int front=0,tail=0;memset(dep,-1,sizeof(dep[0])*(n+1));dep[s]=0;Q[tail++]=s;while(front<tail){int u=Q[front++];for(int i=head[u];i!=-1;i=edge[i].next){int v=edge[i].to;if(edge[i].cap>edge[i].flow&&dep[v]==-1){dep[v]=dep[u]+1;if(v==t)return true;Q[tail++]=v;}}}return false;
}
int dinic(int s,int t,int n){int maxflow=0;while(bfs(s,t,n)){rep(i,0,n-1)cur[i]=head[i];int u=s,tail=0;while(cur[s]!=-1){if(u==t){int tp=inf;per(i,tail-1,0){tp=min(tp,edge[sta[i]].cap-edge[sta[i]].flow);}maxflow+=tp;per(i,tail-1,0){edge[sta[i]].flow+=tp;edge[sta[i]^1].flow-=tp;if(edge[sta[i]].cap-edge[sta[i]].flow==0){tail=i;}}u=edge[sta[tail]^1].to;}else if(cur[u]!=-1&&edge[cur[u]].cap>edge[cur[u]].flow&&dep[u]+1==dep[edge[cur[u]].to]){sta[tail++]=cur[u];u=edge[cur[u]].to;}else{while(u!=s&&cur[u]==-1){u=edge[sta[--tail]^1].to;}cur[u]=edge[cur[u]].next;}}}return maxflow;
}
int main(){int n,f,d,x,y,temp;while(~scanf("%d%d%d",&n,&f,&d)){init();rep(i,1,f)addedge(0,i,1);rep(i,1,d)addedge(f+2*n+i,f+2*n+d+1,1);rep(i,1,n){scanf("%d%d",&x,&y);rep(j,1,x){scanf("%d",&temp);addedge(temp,f+i,1);}addedge(f+i,f+n+i,1);rep(j,1,y){scanf("%d",&temp);addedge(f+n+i,f+2*n+temp,1);}}int ans=dinic(0,f+2*n+d+1,f+2*n+d+2);printf("%d\n",ans);}
}

 

这篇关于POJ 3281(dinic)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---