题意：给出一张有向图，现在要你删去一些边构造一张新图，新图的要求有
1.对于起点s，出度-入度=1.
2.对于终点t，入度-出度=1.
3.对于其余的点，入度=出度.
另外，保留每条边需要花费ai,删掉每条边需要花费bi。
现在求一个最小花费的方案使得能够构造出符合要求的图。
看到这题首先想到以前做过的几个混合图欧拉回路的问题，因为本题跟混合图欧拉回路有一些类似的地方，比如说，我无法去控制每个点具体的出度入度到底是多少，但是可以知道它们之间的关系。并且对于每条边，我都不知道到底该不该留，所以可能会考虑先假定它到底是留下还是不留，然后利用每个点度数的关系跟源汇相连，用网络流去求解一个方案。
所以本题就应该是一个费用流的问题。具体操作起来的话，如果把这些边全部假定留下，然后考虑如果要删去这条边，这个费用就可能是负的也可能是正的了。这样一建图，如果建出个有费用负圈的，就跪了。。所以不能这样建图。其实费用肯定会有一个下界。
我默认费用小的方案为初始方案，即对每条边(u,v,a,b)，如果b>=a，那么我默认它留下，费用下限sum+=a，删去此边的额外费用是b-a,对应一条边(u,v,1,b-a)，in(v)++,out(u)++。
同理，如果a>b，那么我默认它应该删去，费用下限sum+=b，保留此边的额外费用是a-b，对应边(v,u,1,a-b)。这条边肯定跟原来的边是反向的，因为这条边如果是需要的，那肯定是因为u的出度多了，应该多入一个。
再接下来，利用前面默认统计的每个点的出度、入度再跟源汇相连构造网络流了。设val=in(i)-out(i)，如果i是起点s，val额外+1，如果i是汇点，val额外-1。如果val>0,那么对应边(i,T,val,0),否则对应边(S,i,val,0)。
构造完后跑费用流，如果满流，那么最小费用+费用下限sum就是答案，否则就是impossible。
1 #include <cstdio> 2 #include <algorithm> 3 #include <cstring> 4 #include <queue> 5 #define maxn 110 6 #define maxm 100000 7 #define INF 1<<30 8 using namespace std; 9 struct MCMF{ 10 int src,sink,e,n; 11 int first[maxn]; 12 int cap[maxm],cost[maxm],v[maxm],next[maxm]; 13 void init(){ 14 e = 0; 15 memset(first,-1,sizeof(first)); 16 } 17 void add_edge(int a,int b,int cc,int ww){ 18 //printf("add:%d to %d,cap = %d,cost = %d ",a,b,cc,ww); 19 v[e] = b;next[e] = first[a];cap[e] = cc; 20 cost[e] = ww;first[a] = e++; 21 v[e] = a;next[e] = first[b];cap[e] = 0; 22 cost[e] = -ww;first[b] = e++; 23 } 24 25 int d[maxn],pre[maxn],pos[maxn]; 26 bool vis[maxn]; 27 28 bool spfa(int s,int t){ 29 memset(pre,-1,sizeof(pre)); 30 memset(vis,0,sizeof(vis)); 31 queue<int> Q; 32 for(int i = 0;i <= n;i++) d[i] = INF; 33 Q.push(s);pre[s] = s;d[s] = 0;vis[s] = 1; 34 while(!Q.empty()){ 35 int u = Q.front();Q.pop(); 36 vis[u] = 0; 37 for(int i = first[u];i != -1;i = next[i]){ 38 if(cap[i] > 0 && d[u] + cost[i] < d[v[i]]){ 39 d[v[i]] = d[u] + cost[i]; 40 pre[v[i]] = u;pos[v[i]] = i; 41 if(!vis[v[i]]) vis[v[i]] = 1,Q.push(v[i]); 42 } 43 } 44 } 45 return pre[t] != -1; 46 } 47 48 int Mincost,Maxflow; 49 int MincostFlow(int s,int t,int nn){ 50 Mincost = Maxflow = 0,n = nn; 51 while(spfa(s,t)){ 52 int min_f = INF; 53 for(int i = t;i != s;i = pre[i]) 54 if(cap[pos[i]] < min_f) min_f = cap[pos[i]]; 55 Mincost += d[t] * min_f; 56 Maxflow += min_f; 57 for(int i = t;i != s;i = pre[i]){ 58 cap[pos[i]] -= min_f; 59 cap[pos[i]^1] += min_f; 60 } 61 } 62 return Mincost; 63 } 64 }; 65 MCMF g; 66 int in[maxn],out[maxn]; 67 68 int main() 69 { 70 int n,m,s,t,nkase; 71 scanf("%d",&nkase); 72 for(int kase = 1;kase <= nkase;kase++){ 73 g.init(); 74 scanf("%d%d%d%d",&n,&m,&s,&t); 75 int S = 0,T = n+1; 76 memset(in,0,sizeof(in)); 77 memset(out,0,sizeof(out)); 78 int sum = 0,cnt = 0; 79 for(int i = 0;i < m;i++){ 80 int from,to,a,b; 81 scanf("%d%d%d%d",&from,&to,&a,&b); 82 if(a <= b){ 83 in[to]++,out[from]++; 84 g.add_edge(from,to,1,b-a); 85 sum += a; 86 }else{ 87 g.add_edge(to,from,1,a-b); 88 sum += b; 89 } 90 } 91 for(int i = 1;i <= n;i++){ 92 int val = in[i]-out[i]; 93 if(i == s) val++; 94 if(i == t) val--; 95 if(val > 0){ 96 g.add_edge(i,T,val,0); 97 cnt += val; 98 }else{ 99 g.add_edge(S,i,-val,0); 100 } 101 } 102 int ans = sum + g.MincostFlow(S,T,T); 103 if(g.Maxflow == cnt){ 104 printf("Case %d: %d ",kase,ans); 105 }else{ 106 printf("Case %d: impossible ",kase); 107 } 108 } 109 return 0; 110 }