poj3281（最大流）

【建模方法】 此题的建模方法比较有开创性。以往一般都是左边一个点集表示供应并与源相连， 右边一个点集表示需求并与汇相连。现在不同了，供应有两种资源，需求仍只有 一个群体，怎么办？其实只要仔细思考一下最大流的建模原理，此题的构图也不 是那么难想。最大流的正确性依赖于它的每一条 s-t 流都与一种实际方案一一对 应。那么此题也需要用 s-t 流将一头牛和它喜欢的食物和饮料“串”起来，而食 物和饮料之间没有直接的关系，自然就想到把牛放在中间，两边是食物和饮料， 由 s, t 将它们串起来构成一种分配方案。至此建模的方法也就很明显了：每种食 物 i 作为一个点并连边(s, i, 1)，每种饮料 j 作为一个点并连边(j, t, 1)，将每头牛 k 拆成两个点 k’, k’’并连边(k’, k’’, 1), (i, k’, 1), (k’’, j, 1)，其中 i, j 均是牛 k 喜欢的食物

或饮料。求一次最大流即为结果。

#include<cstdio> #include<vector> #include<queue> #include<cstring> using namespace std; ×î´óÁ÷¿ªÊ¼// typedef int cap_type; #define MAX_V 800 + 30 + 16 // ÓÃÓÚ±íʾ±ßµÄ½á¹¹Ì壨Öյ㡢ÈÝÁ¿¡¢·´Ïò±ß£© struct edge { int to, rev; cap_type cap; edge(int to, cap_type cap, int rev) : to(to), cap(cap), rev(rev) {} }; vector <edge> G[MAX_V]; // ͼµÄÁÚ½Ó±í±íʾ int level[MAX_V]; // ¶¥µãµ½Ô´µãµÄ¾àÀë±êºÅ int iter[MAX_V]; // µ±Ç°»¡£¬ÔÚÆä֮ǰµÄ±ßÒѾ­Ã»ÓÐÓÃÁË // ÏòͼÖмÓÈëÒ»Ìõ´Ófromµ½toµÄÈÝÁ¿ÎªcapµÄ±ß void add_edge(int from, int to, int cap) { G[from].push_back(edge(to, cap, G[to].size())); G[to].push_back(edge(from, 0, G[from].size() - 1)); } // ͨ¹ýBFS¼ÆËã´ÓÔ´µã³ö·¢µÄ¾àÀë±êºÅ void bfs(int s) { memset(level, -1, sizeof(level)); queue<int> que; level[s] = 0; que.push(s); while (!que.empty()) { int v = que.front(); que.pop(); for (int i = 0; i < G[v].size(); ++i) { edge &e = G[v][i]; if (e.cap > 0 && level[e.to] < 0) { level[e.to] = level[v] + 1; que.push(e.to); } } } } // ͨ¹ýDFSÑ°ÕÒÔö¹ã· cap_type dfs(int v, int t, cap_type f) { if (v == t) { return f; } for (int &i = iter[v]; i < G[v].size(); ++i) { edge &e = G[v][i]; if (e.cap > 0 && level[v] < level[e.to]) { cap_type d = dfs(e.to, t, min(f, e.cap)); if (d > 0) { e.cap -= d; G[e.to][e.rev].cap += d; return d; } } } return 0; } // Çó½â´Ósµ½tµÄ×î´óÁ÷ cap_type max_flow(int s, int t) { cap_type flow = 0; for (;;) { bfs(s); if (level[t] < 0) { return flow; } memset(iter, 0, sizeof(iter)); cap_type f; while ((f = dfs(s, t, 0x3f3f3f3f3f3f3f3f)) > 0) { flow += f; } } } ///×î´óÁ÷½áÊø/ int main() { int n,f,d,a,b,c; scanf("%d%d%d",&n,&f,&d); int t = 2*n+f+d+2; for(int i=1;i<=f;i++) add_edge(0,i,1); for(int i=1;i<=d;i++) add_edge(i+f,t,1); for(int i=1;i<=n;i++) { scanf("%d%d",&a,&b); add_edge(i+f+d,i+f+d+n,1); for(int j=0;j<a;j++) { scanf("%d",&c); add_edge(c,i+f+d,1); } for(int j=0;j<b;j++) { scanf("%d",&c); add_edge(i+f+d+n,f+c,1); } } int ans = max_flow(0,t); printf("%d\n",ans); return 0; }