[POJ 1149]PIGS
转载请注明出处：http://danihao123.is-programmer.com/
这个题是经典的网络流题目。在经过一次次的思想过滤后你会发现，这个问题的瓶颈（换猪）大可以理解为前面的顾客给后面的留一些不是？这样问题就简单多了。
按顺序整理出到访每个猪圈的顾客，对于到访每个猪圈的第一个顾客，从向其连一条容量为此猪圈中猪的数量的边。然后每个猪圈前面一个顾客要个给后面的留一些猪，这个可以直接连一条容量为无限大的边来表示。
最后每个顾客向连一条容量为其买猪数量上限的边，然后求一遍
到
的最大流，问题得解。
这个题还有一个优化就是，有一些边是可以合并的（比如说从流出的一些边是可能指向同一顾客的，同一对顾客之间的连边数可能不止1条），但是我没有做这个优化，照样A了……
代码：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 | #include <cstdio>#include <cstring>#include <vector>#include <queue>#include <algorithm>using std::vector;using std::queue;using std::min;const int maxn=105,maxm=1005;namespace Dinic{ struct Edge{ int u,v,cap,flow; }; vector<Edge> edges; vector<int> G[maxn]; int s,t; int m; inline void AddEdge(int u,int v,int cap){ edges.push_back((Edge){u,v,cap,0}); edges.push_back((Edge){v,u,0,0}); m=edges.size(); G[u].push_back(m-2); G[v].push_back(m-1); } bool vis[maxn]; int d[maxn]; inline bool bfs(){ register int i,u,siz; queue<int> Q; memset(vis,0,sizeof(vis)); d[s]=0; Q.push(s); vis[s]=true; while(!Q.empty()){ u=Q.front();Q.pop(); siz=G[u].size(); for(i=0;i<siz;i++){ Edge& e=edges[G[u][i]]; if(!vis[e.v] && e.cap>e.flow){ d[e.v]=d[u]+1; Q.push(e.v); vis[e.v]=true; } } } return vis[t]; } int cur[maxn]; int dfs(int x,int a){ if(x==t || a==0){ return a; } int f,flow=0,siz=G[x].size(); for(int& i=cur[x];i<siz;i++){ Edge& e=edges[G[x][i]]; if(d[e.v]==d[x]+1){ f=dfs(e.v,min(a,e.cap-e.flow)); if(f>0){ flow+=f; e.flow+=f; edges[G[x][i]^1].flow-=f; a-=f; if(a==0){ break; } } } } if(a>0){ d[x]=-1; } return flow; } inline int solve(int S,int T){ register int ans=0; s=S;t=T; while(bfs()){ memset(cur,0,sizeof(cur)); ans+=dfs(s,0x7fffffff); } return ans; }};using Dinic::AddEdge;using Dinic::solve;int pigs[maxm];vector<int> Use[maxm];int main(){ register int i,j; int m,n; scanf("%d%d",&m,&n); for(i=1;i<=m;i++){ scanf("%d",&pigs[i]); } for(i=1;i<=n;i++){ int a,b,temp; scanf("%d",&a); for(j=1;j<=a;j++){ scanf("%d",&temp); Use[temp].push_back(i); } scanf("%d",&b); AddEdge(i,n+1,b); } for(i=1;i<=m;i++){ AddEdge(0,Use[i][0],pigs[i]); int siz=Use[i].size(); for(j=1;j<siz;j++){ AddEdge(Use[i][j-1],Use[i][j],0x7f7f7f7f); } } printf("%d\n",solve(0,n+1)); return 0;} |
评论 (0)
