专题十一 网络流
POJ 3436 ACM Computer Factory
√ POJ 3281 Dining
POJ 1087 A Plug for UNIX
POJ 2195 Going Home
POJ 2516 Minimum Cost
POJ 1459 Power Network
HDU 4280 Island Transport
HDU 4292 Food
HDU 4289 Control
UVA 10480 Sabotage
HDU 2732 Leapin' Lizards
HDU 3338 Kakuro Extension
HDU 3605 Escape
HDU 3081 Marriage Match II
HDU 3416 Marriage Match IV
// poj 3281
1 #include<cstdio> 2 #include<algorithm> 3 #include<queue> 4 #define INF 0x3f3f3f3f 5 using namespace std; 6 7 inline int read() { 8 char c=getchar();int x=0,f=1; 9 while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();} 10 while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();} 11 return x*f; 12 } 13 14 const int MAXN = 30000+5; 15 const int MAXE = 20400+5; 16 17 int num; 18 int head[MAXN]; 19 struct node { 20 int v, flow; 21 int next; 22 } edge[MAXE]; 23 24 inline void add(int x, int y, int w) { 25 edge[num].v = y; 26 edge[num].flow = w; 27 edge[num].next = head[x]; 28 head[x] = num++; 29 } 30 31 int n, cows, food, drink; 32 int cur[MAXN], dis[MAXN]; 33 34 bool bfs() { 35 for(int i = 1; i <= n; ++i) dis[i] = 0; 36 dis[1] = 1; 37 queue<int> q; 38 q.push(1); 39 while(!q.empty()) { 40 int u = q.front(); 41 q.pop(); 42 for(int i = head[u]; i != -1; i = edge[i].next) { 43 int v = edge[i].v; 44 if(!dis[v] && edge[i].flow) { 45 dis[v] = dis[u] + 1; 46 q.push(v); 47 } 48 } 49 } 50 return dis[n] != 0; 51 } 52 53 int dfs(int u, int f) { 54 if(u == n || (!f)) return f; 55 int flow = 0; 56 for(int& i = cur[u]; i != -1; i = edge[i].next) { 57 int v = edge[i].v; 58 if(dis[v] == dis[u] + 1) { 59 int di = dfs(v, min(f, edge[i].flow)); 60 if(di > 0) { 61 flow += di; 62 f -= di; 63 edge[i].flow -= di; 64 edge[i^1].flow += di; 65 if(!f) break; 66 } 67 } 68 } 69 if(!flow) dis[u] = -1; 70 return flow; 71 } 72 73 int Dinic() { 74 int ans = 0; 75 while(bfs()) { 76 for(int i = 1; i <= n; ++i) cur[i] = head[i]; 77 ans += dfs(1, INF); 78 } 79 return ans; 80 } 81 82 83 int main() { 84 cows = read(); food = read(); drink = read(); 85 n = cows*2 + food + drink + 2; 86 num = 0; 87 for(int i = 1; i <= n; ++i) head[i] = -1; 88 for(int i = 2; i <= 1+food; ++i) { 89 add(1, i, 1); 90 add(i, 1, 0); 91 } 92 for(int i = 2+food+cows*2; i <= 1+food+cows*2+drink; ++i) { 93 add(i, n, 1); 94 add(n, i, 0); 95 } 96 int fn, dn, x; 97 for(int i = 2+food; i <= 1+food+cows; ++i) { 98 fn = read(); dn = read(); 99 for(int j = 0; j != fn; ++j) { 100 x = read(); 101 add(1+x, i, 1); 102 add(i, 1+x, 0); 103 } 104 for(int j = 0; j != dn; ++j) { 105 x = read(); 106 add(i+cows, 1+food+cows*2+x, 1); 107 add(1+food+cows*2+x, i+cows, 0); 108 } 109 add(i, i+cows, 1); 110 add(i+cows, i, 0); 111 } 112 printf("%d\n", Dinic()); 113 return 0; 114 }