【題意】：給出n個(gè)模塊，2個(gè)核A,B，它們必須在某一個(gè)核中運(yùn)行，第i個(gè)模塊在A核或B核中運(yùn)行需要花費(fèi)Ai或Bi費(fèi)用。由于有m對模塊需要進(jìn)行數(shù)據(jù)交流，如果它們不在同一核運(yùn)行的話，則再需要多花費(fèi)額外費(fèi)用。問：把每個(gè)模塊運(yùn)行的最小費(fèi)用是多少？
【隨筆】：一上QQ，川大神就留言“poj 3469”給我，大神安排的題目，不能不做啊。
【題解】：剛看完題目，以為是個(gè)費(fèi)用流，因?yàn)樯婕白钚≠M(fèi)用，后來發(fā)現(xiàn)建不了費(fèi)用流模型。
想到昨天晚上剛學(xué)完最小割，然后根據(jù)sample畫了下圖，發(fā)現(xiàn)就是一個(gè)最小割。
根據(jù) 最小割 = 最大流 這個(gè)定理，直接構(gòu)圖求s到t的最大流即可。
加入源點(diǎn)s，表示A核，向每個(gè)模塊i連單向邊，s->i,容量為Ai。
加入?yún)R點(diǎn)t，表示B核，向每個(gè)模塊i連反向邊，i->t,容量為Bi。
再根據(jù)m對模塊連雙向邊，i->j,j->i,容量都是額外費(fè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