【题意】：给出一个有向图，可能有平行边和环。对于图上的每一个点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 }