【題意】：給出一個有向圖，可能有平行邊和環。對于圖上的每一個點i，給出兩個費用Wi+和Wi-，Wi+代表刪除點i所有入邊的費用，Wi-代表刪除點i所有出邊的費用。求刪除改圖所有邊的最小費用是多少？并輸出割邊集。
【題解】：我們先來分析一下，對于一條有向邊<u,v>，要刪除它的話顯然有兩種方法，要么刪除u的出邊，要么刪除v的入邊，這是一個選擇性問題。對于費用最小加上選擇性問題，我們很容易就想到最小割模型。構圖：對于每個點i，拆成 i 和 i' ，從源點s向 i 連邊，容量為Wi-；從 i' 向匯點t連邊，容量為Wi+。對于原圖的邊<u,v>，連邊u->v'，容量為inf，保證這條邊不會被割掉。最后，最小割就是最大流。題目中還要求我們輸出割邊，可以從源點s進行一次dfs染色，這樣S集和T集的顏色必然不同，如果某一條邊兩端點顏色不同，即為割邊。
【代碼】：
1 #include "iostream"
2 #include "cstdio"
3 #include "cstring"
4 using namespace std;
5 const int inf = 1 << 30;
6 #define maxn 250
7 #define maxm 15000
8 int n, m, s, t, k;
9 int out[maxn], in[maxn];
10 int eh[maxn], pre[maxn], cur[maxn], dist[maxn], tot, cnt[maxn], low[maxn];
11 int col[maxn];
12 struct Edge {
13 int u, v, cap, flow, next;
14 }et[maxm];
15
16 void init() {
17 tot = k = 0;
18 memset(eh, -1, sizeof(eh));
19 memset(col, 0, sizeof(col));
20 }
21
22 void add(int u, int v, int cap, int flow) {
23 Edge e = {u, v, cap, flow, eh[u]};
24 et[tot] = e;
25 eh[u] = tot++;
26 }
27
28 void addedge(int u, int v, int cap) {
29 add(u, v, cap, 0), add(v, u, 0, 0);
30 }
31
32 int isap(int s, int t, int n) {
33 int u, v, now, flow = 0;
34 memset(dist, 0, sizeof(dist));
35 memset(low, 0, sizeof(low));
36 memset(cnt, 0, sizeof(cnt));
37 for(u = 0; u <= n; u++) cur[u] = eh[u];
38 low[s] = inf, cnt[0] = n;
39 u = s;
40 while(dist[s] < n) {
41 for(now = cur[u]; now != -1; now = et[now].next)
42 if(et[now].cap - et[now].flow && dist[u] == dist[v = et[now].v] + 1)
43 break;
44 if(now != -1) {
45 cur[u] = pre[v] = now;
46 low[v] = min(low[u], et[now].cap - et[now].flow);
47 u = v;
48 if(u == t) {
49 for(; u != s; u = et[pre[u]].u) {
50 et[pre[u]].flow += low[t];
51 et[pre[u]^1].flow -= low[t];
52 }
53 low[s] = inf, flow += low[t];
54 }
55 } else {
56 if(--cnt[dist[u]] == 0) break;
57 dist[u] = n;
58 cur[u] = eh[u];
59 for(now = eh[u]; now != -1; now = et[now].next)
60 if(et[now].cap - et[now].flow && dist[u] > dist[et[now].v] + 1)
61 dist[u] = dist[et[now].v] + 1;
62 cnt[dist[u]]++;
63 if(u != s) u = et[pre[u]].u;
64 }
65 }
66 return flow;
67 }
68
69 void dfs(int u) {
70 col[u] = 1;
71 for(int i = eh[u]; i != -1; i = et[i].next) {
72 int v = et[i].v;
73 if(et[i].cap - et[i].flow && !col[v])
74 dfs(v);
75 }
76 }
77
78 int main() {
79 while(~scanf("%d%d", &n, &m)) {
80 init();
81 s = 0, t = n * 2 + 1;
82 for(int i = 1; i <= n; i++) scanf("%d", &in[i]), addedge(n + i, t, in[i]);
83 for(int i = 1; i <= n; i++) scanf("%d", &out[i]), addedge(s, i, out[i]);
84 for(int i = 1; i <= m; i++) {
85 int u, v;
86 scanf("%d%d", &u, &v);
87 addedge(u, n + v, inf);
88 }
89 printf("%d\n", isap(s, t, t - s + 1));
90 dfs(s);
91 for(int i = 1; i <= n; i++) {
92 if(col[i] == 0) k++;
93 if(col[i + n] == 1) k++;
94 }
95 printf("%d\n", k);
96 for(int i = 1; i <= n; i++) {
97 if(col[i] == 0) printf("%d -\n", i);
98 if(col[i + n] == 1) printf("%d +\n", i);
99 }
100 }
101 return 0;
102 }