首页 > 代码库 > UVA 10779 （最大流)
UVA 10779 （最大流)
题目链接：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=33631
题目大意：Bob有一些贴纸，他可以和别人交换，他可以把自己独有的贴纸拿出去，也可以把重复的贴纸拿出去（有时候把独有的贴纸而不是重复的贴纸拿出去能换到更多贴纸）。
Bob的朋友也有一些贴纸，但是他们只会拿自己重复的贴纸和Bob换，而且换的是自己没有的贴纸。
求Bob最后最多能有多少种贴纸。
解题思路：
题目意思很明确了。就算把重复的贴纸拿出去也不一定最优，贪心就不用尝试了。
全局资源调配得使用网络流模型。
建图方式：
①S点(看作是Bob)->所有物品：连一条边，cap是Bob持有贴纸数量。
②：所有朋友->所有物品：如果这个人持有的该贴纸数量>=2,连一条边,cap是贴纸数量-1。（原因是这些人只会把重复的贴纸拿出去）。
③：所有物品->所有朋友：如果这个人没有改物品，连一条边，cap=1,。(原因是这些人会接受自己没有的贴纸）
④：所有物品->T点：连一条边，cap=1，统计物品的种类。
这样建图之后，所有物品可以看作Bob的总资产，这个总资产可以流进，也可以流出，在这基础上做一次最大流，就是结果了。
代码使用比较坑爹的边表，虽然速度不如链式前向星，但是ISAP+gap优化+当前弧优化已经足够快了。
#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],paste[15][30];bool vis[maxn];vector<int> G[maxn];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 T,n,k,id,num,no=0; scanf("%d",&T); while(T--) { scanf("%d%d",&n,&k); for(int i=1;i<=n;i++) { scanf("%d",&num); for(int j=1;j<=num;j++) { scanf("%d",&id); paste[i][id]++; } } for(int i=1;i<=k;i++) //S->Bob if(paste[1][i]) {addedge(0,i,paste[1][i]);} for(int i=2;i<=n;i++) //Bob->friends for(int j=1;j<=k;j++) { if(paste[i][j]>=2) addedge(k+i,j,paste[i][j]-1); if(!paste[i][j]) addedge(j,k+i,1); } for(int i=1;i<=k;i++) addedge(i,k+n+1,1);//Bob->T printf("Case #%d: %d\n",++no,maxflow(0,k+n+1)); for(int i=0;i<maxn;i++) G[i].clear(); edges.clear(); memset(paste,0,sizeof(paste)); }}
| 2817630 | neopenx | UVA 10779 | Accepted | 0 KB | 16 ms | C++ 4.8.2 | 3270 B | 2014-10-05 13:48:15 |
UVA 10779 （最大流)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。