題目鏈接：POJ 1149 PIGS
PIGS Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 16533 Accepted: 7403
Description
Mirko works on a pig farm that consists of M locked pig-houses and Mirko can't unlock any pighouse because he doesn't have the keys. Customers come to the farm one after another. Each of them has keys to some pig-houses and wants to buy a certain number of pigs.Input
The first line of input contains two integers M and N, 1 <= M <= 1000, 1 <= N <= 100, number of pighouses and number of customers. Pig houses are numbered from 1 to M and customers are numbered from 1 to N.Output
The first and only line of the output should contain the number of sold pigs.Sample Input
3 3 3 1 10 2 1 2 2 2 1 3 3 1 2 6
Sample Output
7
Source
Croatia OI 2002 Final Exam - First day本題關鍵在如何構圖，構好圖就可以套模板直接求解了。其實大部分的網絡流題目只要能夠圖就基本簡單了。不過構圖是個費腦力的過程。
構圖方法如下：
（1）設一個源點s、一個匯點t，
（2）將顧客看做中間節點，
（3）s和每個豬圈的第一個顧客連邊，容量為開始時豬圈中豬的數目。如果和某個節點有重邊，則將容量值合並（因為源點流出的流量就是所有豬圈能提供的豬的數目），
（4）顧客j緊跟在顧客i之後打開某個豬圈，則邊
（5）每個顧客和匯點之間連邊，邊的容量是顧客所希望買的豬的數目。
完成構圖後，可以進行最大流的求解了。三種方法
（1）EK算法，最短增廣路算法（即先用BFS求增廣路，然後再增廣，但是每次都要BFS，時間復雜度不好。
實現如下：
#include#include #include #include #include using namespace std; #define maxn 1010 #define INF 0x3f3f3f3f int ans, s, t, n; int a[maxn], pre[maxn]; int flow[maxn][maxn]; int cap[maxn][maxn]; void EK() { queue q; memset(flow, 0, sizeof(flow)); ans = 0; while(1) { memset(a, 0, sizeof(a)); a[s] = INF; q.push(s); while(!q.empty()) //bfs找增廣路徑 { int u = q.front(); q.pop(); for(int v = 1; v <= n; v++) if(!a[v] && cap[u][v] > flow[u][v]) { pre[v] = u; q.push(v); a[v] = min(a[u], cap[u][v]-flow[u][v]); } } if(a[t] == 0) break; for(int u = t; u != s; u = pre[u]) //改進網絡流 { flow[pre[u]][u] += a[t]; flow[u][pre[u]] -= a[t]; } ans += a[t]; } } int main() { //freopen("poj_1149.txt", "r", stdin); int m, x, A, B, pig[maxn], pre[maxn]; memset(cap, 0, sizeof(cap)); scanf("%d%d", &m, &n); memset(pre, -1, sizeof(pre)); s = 0; t = n+1; for(int i = 1; i <= m; i++) scanf("%d", &pig[i]); for(int i = 1; i <= n; i++) { scanf("%d", &A); for(int j = 0; j < A; j++) { scanf("%d", &x); if(pre[x] == -1) cap[s][i] += pig[x]; else cap[pre[x]][i] = INF; pre[x] = i; } scanf("%d", &cap[i][t]); } n += 2; EK(); printf("%d\n", ans); return 0; }
（2）Dinic算法。與EK同屬SAP算法， 利用層次圖來找最短路，然後用DFS增廣。
#include#include #include #include #include using namespace std; #define maxn 1010 #define INF 0x3f3f3f3f struct Edge { int from, to, cap; }; vector EG; vector G[maxn]; int n, s, t, ans, d[maxn], cur[maxn]; void addEdge(int from, int to, int cap) { EG.push_back((Edge){from, to, cap}); EG.push_back((Edge){to, from, 0}); int x = EG.size(); G[from].push_back(x-2); G[to].push_back(x-1); } bool bfs() { memset(d, -1, sizeof(d)); queue q; q.push(s); d[s] = 0; while(!q.empty()) { int x = q.front(); q.pop(); for(int i = 0; i < G[x].size(); i++) { Edge& e = EG[G[x][i]]; if(d[e.to] == -1 && e.cap > 0) { d[e.to] = d[x]+1; q.push(e.to); } } } return (d[t]!=-1); } int dfs(int x, int a) { if(x == t || a == 0) return a; int flow = 0, f; for(int& i = cur[x]; i < G[x].size(); i++) { Edge& e = EG[G[x][i]]; if(d[x]+1 == d[e.to] && (f = dfs(e.to, min(a, e.cap))) > 0) { e.cap -= f; EG[G[x][i]^1].cap += f; flow += f; a -= f; if(a == 0) break; } } return flow; } void Dinic() { ans = 0; while(bfs()) { memset(cur, 0, sizeof(cur)); ans += dfs(s, INF); } } int main() { //freopen("poj_1149.txt", "r", stdin); int m, x, A, B, pig[maxn], pre[maxn]; scanf("%d%d", &m, &n); memset(pre, -1, sizeof(pre)); s = 0; t = n+1; for(int i = 1; i <= m; i++) scanf("%d", &pig[i]); for(int i = 1; i <= n; i++) { scanf("%d", &A); for(int j = 0; j < A; j++) { scanf("%d", &x); if(pre[x] == -1) addEdge(s, i, pig[x]); else addEdge(pre[x], i, INF); pre[x] = i; } scanf("%d", &B); addEdge(i, t, B); } n += 2; Dinic(); printf("%d\n", ans); return 0; }
#include比較#include #include #include #include using namespace std; #define maxn 1010 #define INF 0x3f3f3f3f struct Edge { int from, to, cap, flow; }; vector EG; vector G[maxn]; int n, s, t, ans, d[maxn], cur[maxn], p[maxn], num[maxn]; bool vis[maxn]; void addEdge(int from, int to, int cap) { EG.push_back((Edge){from, to, cap, 0}); EG.push_back((Edge){to, from, 0, 0}); int x = EG.size(); G[from].push_back(x-2); G[to].push_back(x-1); } void bfs() { memset(vis, false, sizeof(vis)); queue q; vis[t] = true; d[t] = 0; q.push(t); while(!q.empty()) { int x = q.front(); q.pop(); for(int i = 0; i < G[x].size(); i++) { Edge& e = EG[G[x][i]^1]; if(!vis[e.from] && e.cap > e.flow) { vis[e.from] = true; d[e.from] = d[x]+1; q.push(e.from); } } } } int augment() { int x = t, a = INF; while(x != s) { Edge& e = EG[p[x]]; a = min(a, e.cap-e.flow); x = EG[p[x]].from; } x = t; while(x != s) { EG[p[x]].flow += a; EG[p[x]^1].flow -= a; x = EG[p[x]].from; } return a; } void ISAP() { ans =0; bfs(); memset(num, 0, sizeof(num)); for(int i = 0; i < n; i++) num[d[i]]++; int x = s; memset(cur, 0, sizeof(cur)); while(d[s] < n) { if(x == t) { ans += augment(); x = s; } bool flag = false; for(int i = cur[x]; i < G[x].size(); i++) { Edge& e = EG[G[x][i]]; if(e.cap > e.flow && d[x] == d[e.to]+1) { flag = true; p[e.to] = G[x][i]; cur[x] = i; x = e.to; break; } } if(!flag) { int m = n-1; for(int i = 0; i < G[x].size(); i++) { Edge& e = EG[G[x][i]]; if(e.cap > e.flow) m = min(m, d[e.to]); } if(--num[d[x]] == 0) break; num[d[x] = m+1]++; cur[x] = 0; if(x != s) x = EG[p[x]].from; } } } void Clear() { EG.clear(); for(int i = 0; i < n; ++i) G[i].clear(); } int main() { //freopen("poj_1149.txt", "r", stdin); int m, x, A, B, pig[maxn], pre[maxn]; scanf("%d%d", &m, &n); memset(pre, -1, sizeof(pre)); s = 0; t = n+1; for(int i = 1; i <= m; i++) scanf("%d", &pig[i]); for(int i = 1; i <= n; i++) { scanf("%d", &A); for(int j = 0; j < A; j++) { scanf("%d", &x); if(pre[x] == -1) addEdge(s, i, pig[x]); else addEdge(pre[x], i, INF); pre[x] = i; } scanf("%d", &B); addEdge(i, t, B); } n += 2; ISAP(); printf("%d\n", ans); Clear(); return 0; }
