【题意】：给出n个点，m条边，入口s和出口t，对于每条边有两个值a，b，如果保留这条边需要花费；否则，移除这条边需要花费b。
题目要求用最小费用构造一个有向图满足以下条件：
1.只有一个入口和出口
2.所有路都是唯一方向
3.对于入口s，它的出度 = 它的入度 + 1
4.对于出口t，它的入度 = 它的出度 + 1
5.除了s和t外，其他点的入度 = 其出度
最后如果可以构造，输出最小费用；否则输出impossib。
【题解】：参考了starvae的题解，加入了自己的见解。首先我们贪心构图，何为贪心构图？对于每条边只有两种操作，要么保留，要么删除，每种操作都对应一种费用a或b，然后我们总是选择费用小的操作。
这里定义两个数组in[]，out[]，in[u]表示u当前的入度，同理out[u]表示u当前的出度，sum存放初始费用。
对于每条边u v a b，如果a <= b,连边v->u，容量为1，费用为a-b，这样连边的意义是我们初始选择保留这条边u->v，所以in[v]++, out[u]++，sum+=a。
否则如果a > b,连边u->v,容量为1，费用为b-a,这样连边的意义是我们初始选择删除这条边，所以in[],out[]没有改变，sum+=b。
PS：我们这样选择费用肯定是最小的，但是不一定满足出度入度的要求，所以我们要在此基础上作出相应的调整。
添加一条由t指向s的虚拟边，加入这条边之后就可以把所有点都看成一样了，in[s]++, out[t]++。
再添加一个超级源点ss和一个超级汇点tt，然后对于每个点i，连边两条边，ss->i,容量为in[i],费用0，i->tt,容量为out[i],费用为0.
跑一次最小费用最大流，如果最大流等于所有in[i]的和，那么说明可以构造这样的有向图，费用就是sum+mincost；否则就是impossible了。
starvae加入超级源汇之后是这样连边的：
新建超级源汇S,T。
对于每个点i， 如果in[i] > out[i] . 建边S->i, 权值为0， 流量为in[i] – out[i];
否则的话 建边 i->T ,权值为0， 流量为out[i] – in[i];
其实这样连边和我那种本质是一样的，他这样做就减少了无为的增广，算是小优化吧。
这里说下算法是如何进行调整的：
举个简单的例子，假如某一个点i,in[i] > out[i],说明当前的入度大于当前的出度，那么我们可以这样调整：把之前删除的以i为起点的边添加回来 或者 把之前保留的以i为终点的边删除，现在边的费用其实是改变边状态所需要额外付的费用，而最小费用流算法就可以帮我选择最小的调整费用，也就是那个mincost。
所以最后的总费用ans = 初始费用sum + 最小调整费用mincost。
三点了，不写了，希望大家看得懂吧~
【代码】：
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 }