【题意】:给出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, -1sizeof (eh));
 22     memset(in0sizeof(in));
 23     memset(out0sizeof(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, 00);
 34 }
 35 
 36 bool spfa() {
 37     queue<int> que;
 38     memset(visit, falsesizeof (visit));
 39     memset(p, -1sizeof (p));
 40     memset(low, 0sizeof(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, 0in[i]);
102             addedge(i, tt, 0out[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 }