首页 > 代码库 > POJ 3281 （最大流+匹配+拆点)
POJ 3281 （最大流+匹配+拆点)
题目链接：http://poj.org/problem?id=3281
题目大意：有一些牛，一堆食物，一堆饮料。一头牛要吃一份食物喝一份饮料才算满足，而且牛对某些食物和饮料才有好感，问最多有多少头牛是满足的。
解题思路：
没有费用的匹配最大流题。
我一开始是这么考虑的，S->牛->食物->饮料->T，cap都是1，啊哈，多简单。
这样是不对的。因为牛比较挑剔，假设牛1喜欢食物1，而不喜欢饮料1，那么食物1和饮料1之间连不连边呢？
不连吧，其它牛怎么办？
连吧，牛1怎么办？
果断不能这么建图。于是改成S->食物->牛->饮料->T，这样就解决了模棱两可的食物与饮料之间的联系。
但是新的问题又来了，假设有食物1->牛1->饮料1，那么又会有食物2->牛1->饮料2，这样一头牛就吞了多份食物和饮料。
解决方案是拆点，把牛插成牛->牛‘,cap=1,这样一头牛只会被用一次了。
最终的建图方案：S->食物->牛->牛’->饮料->T。
#include "cstdio"#include "vector"#include "cstring"#include "queue"using namespace std;#define maxn 405#define inf 100000000struct Edge{ int from,to,cap,flow; Edge(int FROM,int TO,int CAP,int FLOW):from(FROM),to(TO),cap(CAP),flow(FLOW) {}};int d[maxn],p[maxn],gap[maxn],cur[maxn];bool vis[maxn];vector<int> G[maxn],food[105],drink[105];vector<Edge> edges;void addedge(int from,int to,int cap){ edges.push_back(Edge(from,to,cap,0)); edges.push_back(Edge(to,from,0,0)); int m=edges.size(); G[from].push_back(m-2); G[to].push_back(m-1);}void bfs(int s,int t){ memset(vis,false,sizeof(vis)); memset(d,0,sizeof(d)); memset(p,0,sizeof(p)); d[t]=0;vis[t]=true; queue<int> Q;Q.push(t); while(!Q.empty()) { int u=Q.front();Q.pop(); for(int v=0;v<G[u].size();v++) { Edge e=edges[G[u][v]^1]; if(!vis[e.from]&&e.cap>e.flow) { vis[e.from]=true; d[e.from]=d[u]+1; Q.push(e.from); } } }}int augment(int s,int t){ int x=t,a=inf; while(x!=s) { Edge e=edges[p[x]]; a=min(a,e.cap-e.flow); x=e.from; } x=t; while(x!=s) { edges[p[x]].flow+=a; edges[p[x]^1].flow-=a; x=edges[p[x]].from; } return a;}int maxflow(int s,int t){ int flow=0,u=s; bfs(s,t); memset(gap,0,sizeof(gap)); memset(cur,0,sizeof(cur)); for(int i=0;i<=t;i++) gap[d[i]]++; while(d[s]<t+1) { if(u==t) { flow+=augment(s,t); u=s; } bool flag=false; for(int v=cur[u];v<G[u].size();v++) //Advance { Edge e=edges[G[u][v]]; if(e.cap>e.flow&&d[u]==d[e.to]+1) { flag=true; p[e.to]=G[u][v]; cur[u]=v; u=e.to; break; } } if(!flag) //Retreat { int m=t+1; for(int v=0;v<G[u].size();v++) { Edge e=edges[G[u][v]]; if(e.cap>e.flow) m=min(m,d[e.to]); } if(--gap[d[u]]==0) break; gap[d[u]=m+1]++; cur[u]=0; if(u!=s) u=edges[p[u]].from; } } return flow;}int main(){ int N,M,K,f,d,t; while(scanf("%d%d%d",&N,&M,&K)!=EOF) { for(int i=1;i<=M;i++) addedge(0,i,1); //S-food for(int i=1;i<=K;i++) addedge(i+M+N*2,K+M+N*2+1,1); //drink-T for(int i=1;i<=N;i++) { addedge(i+M,i+M+N,1); //cow-cow‘ scanf("%d%d",&f,&d); for(int j=1; j<=f; j++) { scanf("%d",&t); addedge(t,i+M,1); //food-cow } for(int j=1; j<=d; j++) { scanf("%d",&t); addedge(i+M+N,t+M+2*N,1); //cow‘-drink } } printf("%d\n",maxflow(0,2*N+M+K+1)); }}
| 13456393 | neopenx | 3281 | Accepted | 320K | 16MS | C++ | 3222B | 2014-09-19 00:28:49 |
POJ 3281 （最大流+匹配+拆点)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。