POJ 3469 最小割 Dual Core CPU

题意：

一个双核CPU上运行N个模块，每个模块在两个核上运行的费用分别为A_i和B_i。

同时，有M对模块需要进行数据交换，如果这两个模块不在同一个核上运行需要额外花费。

求运行N个模块的最小费用。

分析：

这是一个集合划分问题，将这两个模块划分成两个集合，一个集合中的模块在核A上运行，一个在核B上运行。

增加一个源点S和汇点T，每个模块分别和源点和汇点连一条边，容量为在该核上运行的花费。

然后在两个模块对之间连容量为额外花费的双向边。

图中的一个割就对应一个集合的划分，最小割就是最小的总费用。

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

代码君