【題意】：給出n個(gè)點(diǎn)，m條邊，入口s和出口t，對(duì)于每條邊有兩個(gè)值a，b，如果保留這條邊需要花費(fèi)；否則，移除這條邊需要花費(fèi)b。
題目要求用最小費(fèi)用構(gòu)造一個(gè)有向圖滿足以下條件：
1.只有一個(gè)入口和出口
2.所有路都是唯一方向
3.對(duì)于入口s，它的出度 = 它的入度 + 1
4.對(duì)于出口t，它的入度 = 它的出度 + 1
5.除了s和t外，其他點(diǎn)的入度 = 其出度
最后如果可以構(gòu)造，輸出最小費(fèi)用；否則輸出impossib。
【題解】：參考了starvae的題解，加入了自己的見(jiàn)解。首先我們貪心構(gòu)圖，何為貪心構(gòu)圖？對(duì)于每條邊只有兩種操作，要么保留，要么刪除，每種操作都對(duì)應(yīng)一種費(fèi)用a或b，然后我們總是選擇費(fèi)用小的操作。
這里定義兩個(gè)數(shù)組in[]，out[]，in[u]表示u當(dāng)前的入度，同理out[u]表示u當(dāng)前的出度，sum存放初始費(fèi)用。
對(duì)于每條邊u v a b，如果a <= b,連邊v->u，容量為1，費(fèi)用為a-b，這樣連邊的意義是我們初始選擇保留這條邊u->v，所以in[v]++, out[u]++，sum+=a。
否則如果a > b,連邊u->v,容量為1，費(fèi)用為b-a,這樣連邊的意義是我們初始選擇刪除這條邊，所以in[],out[]沒(méi)有改變，sum+=b。
PS：我們這樣選擇費(fèi)用肯定是最小的，但是不一定滿足出度入度的要求，所以我們要在此基礎(chǔ)上作出相應(yīng)的調(diào)整。
添加一條由t指向s的虛擬邊，加入這條邊之后就可以把所有點(diǎn)都看成一樣了，in[s]++, out[t]++。
再添加一個(gè)超級(jí)源點(diǎn)ss和一個(gè)超級(jí)匯點(diǎn)tt，然后對(duì)于每個(gè)點(diǎn)i，連邊兩條邊，ss->i,容量為in[i],費(fèi)用0，i->tt,容量為out[i],費(fèi)用為0.
跑一次最小費(fèi)用最大流，如果最大流等于所有in[i]的和，那么說(shuō)明可以構(gòu)造這樣的有向圖，費(fèi)用就是sum+mincost；否則就是impossible了。
starvae加入超級(jí)源匯之后是這樣連邊的：
新建超級(jí)源匯S,T。
對(duì)于每個(gè)點(diǎn)i， 如果in[i] > out[i] . 建邊S->i, 權(quán)值為0， 流量為in[i] – out[i];
否則的話 建邊 i->T ,權(quán)值為0， 流量為out[i] – in[i];
其實(shí)這樣連邊和我那種本質(zhì)是一樣的，他這樣做就減少了無(wú)為的增廣，算是小優(yōu)化吧。
這里說(shuō)下算法是如何進(jìn)行調(diào)整的：
舉個(gè)簡(jiǎn)單的例子，假如某一個(gè)點(diǎn)i,in[i] > out[i],說(shuō)明當(dāng)前的入度大于當(dāng)前的出度，那么我們可以這樣調(diào)整：把之前刪除的以i為起點(diǎn)的邊添加回來(lái) 或者 把之前保留的以i為終點(diǎn)的邊刪除，現(xiàn)在邊的費(fèi)用其實(shí)是改變邊狀態(tài)所需要額外付的費(fèi)用，而最小費(fèi)用流算法就可以幫我選擇最小的調(diào)整費(fèi)用，也就是那個(gè)mincost。
所以最后的總費(fèi)用ans = 初始費(fèi)用sum + 最小調(diào)整費(fèi)用mincost。
三點(diǎn)了，不寫了，希望大家看得懂吧~
【代碼】：
1 #include "iostream"
2 #include "cstdio"
3 #include "cstring"
4 #include "queue"
5 using namespace std;
6 #define maxn 105
7 #define maxm 10050
8 const int inf = 1 << 30;
9 int ans, anscost, eh[maxn], tot, low[maxn], p[maxn], dist[maxn];
10 int s, t, ss, tt;
11 int n, m;
12 int sum;
13 int in[maxn], out[maxn];
14 struct Edge {
15 int u, v, cost, cap, flow, next;
16 } et[maxm];
17 bool visit[maxn];
18
19 void init() {
20 sum = tot = 0;
21 memset(eh, -1, sizeof (eh));
22 memset(in, 0, sizeof(in));
23 memset(out, 0, sizeof(out));
24 }
25
26 void add(int u, int v, int cost, int cap, int flow) {
27 Edge e = {u, v, cost, cap, flow, eh[u]};
28 et[tot] = e;
29 eh[u] = tot++;
30 }
31
32 void addedge(int u, int v, int cost, int cap) {
33 add(u, v, cost, cap, 0), add(v, u, -cost, 0, 0);
34 }
35
36 bool spfa() {
37 queue<int> que;
38 memset(visit, false, sizeof (visit));
39 memset(p, -1, sizeof (p));
40 memset(low, 0, sizeof(low));
41 fill(&dist[0], &dist[maxn], inf);
42 visit[ss] = true, low[ss] = inf, dist[ss] = 0;
43 que.push(ss);
44 while (!que.empty()) {
45 int u = que.front();
46 que.pop();
47 visit[u] = false;
48 for (int i = eh[u]; i != -1; i = et[i].next) {
49 int v = et[i].v, cost = et[i].cost, cap = et[i].cap, flow = et[i].flow;
50 if (flow < cap && dist[u] + cost < dist[v]) {
51 dist[v] = dist[u] + cost;
52 p[v] = i;
53 low[v] = min(low[u], cap - flow);
54 if (!visit[v]) {
55 visit[v] = true;
56 que.push(v);
57 }
58 }
59 }
60 }
61 return dist[tt] != inf;
62 }
63
64 void costflow() {
65 ans = 0, anscost = 0;
66 while (spfa()) {
67 int x = p[tt];
68 ans += low[tt];
69 anscost += low[tt] * dist[tt];
70 while (x != -1) {
71 et[x].flow += low[tt];
72 et[x^1].flow -= low[tt];
73 et[x^1].cost = -et[x].cost;
74 x = p[et[x].u];
75 }
76 }
77 }
78
79 int main() {
80 int T, Case = 1;
81 int u, v, a, b;
82 scanf("%d", &T);
83 while(T--) {
84 scanf("%d%d%d%d", &n, &m, &s, &t);
85 init();
86 for(int i = 0; i < m; i++) {
87 scanf("%d%d%d%d", &u, &v, &a, &b);
88 if(a <= b) {
89 sum += a;
90 addedge(v, u, b - a, 1);
91 in[v]++, out[u]++;
92 } else {
93 sum += b;
94 addedge(u, v, a - b, 1);
95 }
96 }
97 in[s]++, out[t]++;
98 ss = 0, tt = n + 1;
99 int tmp = 0;
100 for(int i = 1; i <= n; i++) {
101 addedge(ss, i, 0, in[i]);
102 addedge(i, tt, 0, out[i]);
103 tmp += in[i];
104 }
105 /* for(int i = 1; i <= n; i++) {
106 if(in[i] >= out[i]) addedge(ss, i, 0, in[i] - out[i]), tmp += in[i] - out[i];
107 else addedge(i, tt, 0, out[i] - in[i]);
108 }*/
109 costflow();
110 printf("Case %d: ", Case++);
111 if(ans == tmp) printf("%d\n", sum + anscost);
112 else printf("impossible\n");
113 }
114 return 0;
115 }