【题意】：给出n个模块，2个核A,B，它们必须在某一个核中运行，第i个模块在A核或B核中运行需要花费Ai或Bi费用。由于有m对模块需要进行数据交流，如果它们不在同一核运行的话，则再需要多花费额外费用。问：把每个模块运行的最小费用是多少？
【随笔】：一上QQ，川大神就留言“poj 3469”给我，大神安排的题目，不能不做啊。
【题解】：刚看完题目，以为是个费用流，因为涉及最小费用，后来发现建不了费用流模型。
想到昨天晚上刚学完最小割，然后根据sample画了下图，发现就是一个最小割。
根据 最小割 = 最大流 这个定理，直接构图求s到t的最大流即可。
加入源点s，表示A核，向每个模块i连单向边，s->i,容量为Ai。
加入汇点t，表示B核，向每个模块i连反向边，i->t,容量为Bi。
再根据m对模块连双向边，i->j,j->i,容量都是额外费用。
求s-t最大流就是答案。
【代码】：
1 #include "iostream"
2 #include "cstdio"
3 #include "cstring"
4 using namespace std;
5 #define maxn 20005
6 #define maxm 1000005
7 const int INF = 99999999;
8 int s, t, n, m;
9 int low[maxn], dist[maxn], pre[maxn], cur[maxn], tot, eh[maxn], cnt[maxn];
10
11 struct Edge {
12 int u, v, cap, flow, next;
13 }et[maxm];
14
15 void init() {
16 tot = 0;
17 memset(eh, -1, sizeof(eh));
18 }
19
20 void add(int u, int v, int cap, int flow) {
21 Edge E = {u, v, cap, flow, eh[u]};
22 et[tot] = E;
23 eh[u] = tot++;
24 }
25
26 void addedge(int u, int v, int cap) {
27 add(u, v, cap, 0), add(v, u, 0, 0);
28 }
29
30 int isap(int s, int t, int n) {
31 int u, v, now;
32 memset(dist, 0, sizeof(dist));
33 memset(low, 0, sizeof(low));
34 for(u = 0; u <= n; u++) cur[u] = eh[u];
35 low[s] = 0, cnt[0] = n;
36 u = s;
37 int flow = 0;
38 while(dist[s] < n) {
39 for(now = cur[u]; now != -1; now = et[now].next)
40 if(et[now].cap - et[now].flow && dist[u] == dist[v = et[now].v] + 1) break;
41 if(now != -1) {
42 cur[u] = pre[v] = now;
43 low[v] = min(low[u], et[now].cap - et[now].flow);
44 u = v;
45 if(u == t) {
46 for(; u != s; u = et[pre[u]].u) {
47 et[pre[u]].flow += low[t];
48 et[pre[u]^1].flow -= low[t];
49 }
50 flow += low[t];
51 low[s] = INF;
52 }
53 } else {
54 if(--cnt[dist[u]] == 0) break;
55 dist[u] = n;
56 cur[u] = eh[u];
57 for(now = eh[u]; now != -1; now = et[now].next)
58 if(et[now].cap - et[now].flow && dist[u] > dist[et[now].v] + 1)
59 dist[u] = dist[et[now].v] + 1;
60 cnt[dist[u]]++;
61 if(u != s) u = et[pre[u]].u;
62 }
63 }
64 return flow;
65 }
66
67 int main() {
68 int u, v, cap, i;
69 scanf("%d%d", &n, &m);
70 init();
71 s = 0, t = n + 1;
72 for(i = 1; i <= n; i++) {
73 scanf("%d", &cap);
74 addedge(s, i, cap);
75 scanf("%d", &cap);
76 addedge(i, t, cap);
77 }
78 for(i = 1; i <= m; i++) {
79 scanf("%d%d%d", &u, &v, &cap);
80 addedge(u, v, cap);
81 addedge(v, u, cap);
82 }
83 printf("%d\n", isap(s, t, t - s + 1));
84 return 0;
85 }
86