题目链接：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.
All data concerning customers planning to visit the farm on that particular day are available to Mirko early in the morning so that he can make a sales-plan in order to maximize the number of pigs sold.
More precisely, the procedure is as following: the customer arrives, opens all pig-houses to which he has the key, Mirko sells a certain number of pigs from all the unlocked pig-houses to him, and, if Mirko wants, he can redistribute the remaining pigs across the unlocked pig-houses.
An unlimited number of pigs can be placed in every pig-house.
Write a program that will find the maximum number of pigs that he can sell on that day. 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.
The next line contains M integeres, for each pig-house initial number of pigs. The number of pigs in each pig-house is greater or equal to 0 and less or equal to 1000.
The next N lines contains records about the customers in the following form ( record about the i-th customer is written in the (i+2)-th line):
A K1 K2 ... KA B It means that this customer has key to the pig-houses marked with the numbers K1, K2, ..., KA (sorted nondecreasingly ) and that he wants to buy B pigs. Numbers A and B can be equal to 0. 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之后打开某个猪圈，则边
的容量为INF，因为如果顾客j紧跟顾客i之后打开某个猪圈，那么迈克就有可能根据顾客j的要求将其他猪圈中的猪调整到该猪圈，这样顾客j就能买到尽可能多的猪，
（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