POJ 3281 网络流拆点 Dining

题意：

有F种食物和D种饮料，每头牛有各自喜欢的食物和饮料，而且每种食物或者饮料只能给一头牛。

求最多能有多少头牛能同时得到它喜欢的食物或者饮料。

分析：

把每个牛拆点，中间连一条容量为1的边，保证一头牛不会被多个食物或者饮料分配。

然后把饮料和牛连边，食物和另外一边的牛连边，最后增加一个源点和汇点跑最大流。

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <algorithm>
  5 #include <vector>
  6 #include <queue>
  7 using namespace std;
  8 
  9 const int maxn = 100 + 10;
 10 const int maxnode = 400 + 10;
 11 const int INF = 0x3f3f3f3f;
 12 
 13 int N, F, D;
 14 
 15 int n, s, t;
 16 
 17 struct Edge
 18 {
 19     int from, to, cap, flow;
 20     Edge(int u, int v, int c, int f):from(u), to(v), cap(c), flow(f) {}
 21 };
 22 
 23 vector<Edge> edges;
 24 vector<int> G[maxnode];
 25 
 26 void init()
 27 {
 28     edges.clear();
 29     for(int i = 0; i < n; i++) G[i].clear();
 30 }
 31 
 32 void AddEdge(int u, int v, int c)
 33 {
 34     edges.push_back(Edge(u, v, c, 0));
 35     edges.push_back(Edge(v, u, 0, 0));
 36     int m = edges.size();
 37     G[u].push_back(m - 2);
 38     G[v].push_back(m - 1);
 39 }
 40 
 41 bool vis[maxnode];
 42 int d[maxnode];
 43 int cur[maxnode];
 44 
 45 bool BFS()
 46 {
 47     d[s] = 0;
 48     queue<int> Q;
 49     Q.push(s);
 50     memset(vis, false, sizeof(vis));
 51     vis[s] = true;
 52 
 53     while(!Q.empty())
 54     {
 55         int u = Q.front(); Q.pop();
 56         for(int i = 0; i < G[u].size(); i++)
 57         {
 58             Edge& e = edges[G[u][i]];
 59             int v = e.to;
 60             if(!vis[v] && e.cap > e.flow)
 61             {
 62                 vis[v] = true;
 63                 d[v] = d[u] + 1;
 64                 Q.push(v);
 65             }
 66         }
 67     }
 68 
 69     return vis[t];
 70 }
 71 
 72 int DFS(int u, int a)
 73 {
 74     if(u == t || a == 0) return a;
 75     int flow = 0, f;
 76     for(int& i = cur[u]; i < G[u].size(); i++)
 77     {
 78         Edge& e = edges[G[u][i]];
 79         int v = e.to;
 80         if(d[v] == d[u] + 1 && (f = DFS(v, min(a, e.cap - e.flow))) > 0)
 81         {
 82             flow += f;
 83             e.flow += f;
 84             a -= f;
 85             edges[G[u][i]^1].flow -= f;
 86             if(a == 0) break;
 87         }
 88     }
 89     return flow;
 90 }
 91 
 92 int Maxflow()
 93 {
 94     int flow = 0;
 95     while(BFS())
 96     {
 97         memset(cur, 0, sizeof(cur));
 98         flow += DFS(s, INF);
 99     }
100     return flow;
101 }
102 
103 int main()
104 {
105     while(scanf("%d%d%d", &N, &F, &D) == 3)
106     {
107         n = N * 2 + D + F + 2;
108         s = 0, t = n - 1;
109         init();
110 
111         //build graph
112         for(int i = 1; i <= F; i++) AddEdge(s, N*2+i, 1);
113         for(int i = 1; i <= D; i++) AddEdge(N*2+F+i, t, 1);
114         for(int i = 1; i <= N; i++) AddEdge(i, i + N, 1);
115 
116         for(int i = 1; i <= N; i++)
117         {
118             int f, d, x; scanf("%d%d", &f, &d);
119             while(f--)
120             {
121                 scanf("%d", &x);
122                 AddEdge(N*2+x, i, 1);
123             }
124             while(d--)
125             {
126                 scanf("%d", &x);
127                 AddEdge(N + i, N*2+F+x, 1);
128             }
129         }
130 
131         printf("%d
", Maxflow());
132     }
133 
134     return 0;
135 }

代码君

POJ 3281 网络流 拆点 Dining

POJ 3281 网络流拆点 Dining