题目大意：有N头牛，F种食物，D种饮料，每种食物和饮料都只有一
现在给出每头牛所喜爱的食物和饮料，问最多有多少头牛能同时得到自己喜欢的食物和饮料

解题思路：将牛拆成两点，权值为1，一条和喜欢的食物相连，权值为1，另一条和喜欢的饮料相连，权值为1
然后将所有食物和超级源点相连，权值为1
将所有的饮料喝超级汇点相连，权值为1

ISAP

#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         using namespace std; #define N 1010 #define INF 0x3f3f3f3f struct Edge { int from, to, cap, flow; Edge() {} Edge(int from, int to, int cap, int flow): from(from), to(to), cap(cap), flow(flow) {} }; struct ISAP { int p[N], num[N], cur[N], d[N]; int t, s, n, m; bool vis[N]; vector
        
          G[N]; vector
         
           edges; void init(int n) { this->n = n; for (int i = 0; i <= n; i++) { G[i].clear(); d[i] = INF; } edges.clear(); } void AddEdge(int from, int to, int cap) { edges.push_back(Edge(from, to, cap, 0)); edges.push_back(Edge(to, from, 0, 0)); int m = edges.size(); G[from].push_back(m - 2); G[to].push_back(m - 1); } bool BFS() { memset(vis, 0, sizeof(vis)); queue
          
            Q; d[t] = 0; vis[t] = 1; Q.push(t); while (!Q.empty()) { int u = Q.front(); Q.pop(); for (int i = 0; i < G[u].size(); i++) { Edge &e = edges[G[u][i] ^ 1]; if (!vis[e.from] && e.cap > e.flow) { vis[e.from] = true; d[e.from] = d[u] + 1; Q.push(e.from); } } } return vis[s]; } int Augment() { int u = t, flow = INF; while (u != s) { Edge &e = edges[p[u]]; flow = min(flow, e.cap - e.flow); u = edges[p[u]].from; } u = t; while (u != s) { edges[p[u]].flow += flow; edges[p[u] ^ 1].flow -= flow; u = edges[p[u]].from; } return flow; } int Maxflow(int s, int t) { this->s = s; this->t = t; int flow = 0; BFS(); if (d[s] > n) return 0; memset(num, 0, sizeof(num)); memset(cur, 0, sizeof(cur)); for (int i = 0; i < n; i++) if (d[i] < INF) num[d[i]]++; int u = s; while (d[s] <= n) { if (u == t) { flow += Augment(); u = s; } bool ok = false; for (int i = cur[u]; i < G[u].size(); i++) { Edge &e = edges[G[u][i]]; if (e.cap > e.flow && d[u] == d[e.to] + 1) { ok = true; p[e.to] = G[u][i]; cur[u] = i; u = e.to; break; } } if (!ok) { int Min = n; for (int i = 0; i < G[u].size(); i++) { Edge &e = edges[G[u][i]]; if (e.cap > e.flow) Min = min(Min, d[e.to]); } if (--num[d[u]] == 0) break; num[d[u] = Min + 1]++; cur[u] = 0; if (u != s) u = edges[p[u]].from; } } return flow; } }; //cow 1 -- 2 * n //food 2 * n + 1 --- 2 * n + f //drink 2 * n + f + 1 --- 2 * n + f + d //start 0 //sink 2 * n + f + d + 1 ISAP isap; int n, f, d; void init() { int s = 0, t = 2 * n + d + f + 1; isap.init(t); for (int i = 1; i <= f; i++) { isap.AddEdge(0, 2 * n + i, 1); } for (int i = 1; i <= d; i++) { isap.AddEdge(2 * n + f + i, t, 1); } int fi, di, x; for (int i = 1; i <= n; i++) { scanf(%d%d, &fi, &di); isap.AddEdge(i, n + i, 1); for (int j = 0; j < fi; j++) { scanf(%d, &x); isap.AddEdge(2 * n + x, i, 1); } for (int j = 0; j < di; j++) { scanf(%d, &x); isap.AddEdge(n + i, 2 * n + f + x, 1); } } int flow = isap.Maxflow(s, t); printf(%d , flow); } int main() { while (scanf(%d%d%d, &n, &f, &d) != EOF) { init(); } return 0; }
          
         
        
       
      
     
    
   

Dinic

#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         using namespace std; #define N 1010 #define INF 0x3f3f3f3f struct Edge{ int from, to, cap, flow; Edge() {} Edge(int from, int to, int cap, int flow) : from(from), to(to), cap(cap), flow(flow) {} }; struct Dinic{ int n, m, s, t; vector
        
          edges; vector
         
           G[N]; bool vis[N]; int d[N], cur[N]; void init(int n) { this->n = n; for (int i = 0; i <= n; i++) { G[i].clear(); } edges.clear(); } void AddEdge(int from, int to, int cap) { edges.push_back(Edge(from, to, cap, 0)); edges.push_back(Edge(to, from, 0, 0)); int m = edges.size(); G[from].push_back(m - 2); G[to].push_back(m - 1); } bool BFS() { memset(vis, 0, sizeof(vis)); queue
          
            Q; Q.push(s); vis[s] = 1; d[s] = 0; while (!Q.empty()) { int u = Q.front(); Q.pop(); for (int i = 0; i < G[u].size(); i++) { Edge &e = edges[G[u][i]]; if (!vis[e.to] && e.cap > e.flow) { vis[e.to] = true; d[e.to] = d[u] + 1; Q.push(e.to); } } } return vis[t]; } 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 = edges[G[x][i]]; if (d[x] + 1 == d[e.to] && (f = DFS(e.to, min(a, e.cap - e.flow))) > 0) { e.flow += f; edges[G[x][i] ^ 1].flow -= f; flow += f; a -= f; if (a == 0) break; } } return flow; } int Maxflow(int s, int t) { this->s = s; this->t = t; int flow = 0; while (BFS()) { memset(cur, 0, sizeof(cur)); flow += DFS(s, INF); } return flow; } }; Dinic dinic; //cow 1 -- 2 * n //food 2 * n + 1 --- 2 * n + f //drink 2 * n + f + 1 --- 2 * n + f + d //start 0 //sink 2 * n + f + d + 1 int n, f, d; void init() { int s = 0, t = 2 * n + d + f + 1; dinic.init(t); for (int i = 1; i <= f; i++) { dinic.AddEdge(0, 2 * n + i, 1); } for (int i = 1; i <= d; i++) { dinic.AddEdge(2 * n + f + i, t, 1); } int fi, di, x; for (int i = 1; i <= n; i++) { scanf(%d%d, &fi, &di); dinic.AddEdge(i, n + i, 1); for (int j = 0; j < fi; j++) { scanf(%d, &x); dinic.AddEdge(2 * n + x, i, 1); } for (int j = 0; j < di; j++) { scanf(%d, &x); dinic.AddEdge(n + i, 2 * n + f + x, 1); } } int flow = dinic.Maxflow(s, t); printf(%d , flow); } int main() { while (scanf(%d%d%d, &n, &f, &d) != EOF) { init(); } return 0; } 
          
         
        
       
      
     
    
   

EK