题目描述：

200个点的图，告诉你一些单向边，每条边两个值a和b，表示选与不选的花费。

现在让起点的出度-入度=1，终点的入度-出度=1，其他点的入度=出度。

问是否可能，可能的话最小花费是多少。

解题报告：

入度不足的用流补上，出度不足的流满即可。

一开始没仔细想，简单认为：

默认所有边选，删除一条边的代价为b – a，费用流求解，但是这样就可能有负环，果断TLE。

 

随后，更改思路，具体算法如下：

Sum表示初始图的代价，开始时为0.

对于b>=a的边，那么默认这条边连接，边权为b-a（删除的费用），当前费用sum+=a，由于默认这条边连接，那么出度[from]++, 入度[to]++

对于b<a的边，那么默认这条边没有连接，加入to到from的反向边，在流中就表示用这条反向边维护节点度的平衡，边权为a-b（添加的费用），当前费用sum+=b，由于默认不加这条边，所以出度入度就不用更新。

超级源点S，汇点T

出度>入度的，S连接之，容量为差值

入度>出度的，连接T，容量为差值

（注意图中起点和终点的+1-1的要求）

这样，如果满流，每个节点就满足了度的要求。

Sum+费用就是答案。

代码如下：

#include<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

#include<map>

using namespace std;

 

 

#define size 200

#define Max 0x7fffffff

struct edge{int from, to, val, next, cost;} e[size * 40 + 20];

int v[size], cnt, pre[size], pos[size], dis[size], que[size * 10], vst[size];

void insert(int from, int to, int val, int cost)

{

    e[cnt].from = from, e[cnt].to = to, e[cnt].val = val;

    e[cnt].cost = cost, e[cnt].next = v[from];v[from] = cnt++;

    e[cnt].from = to, e[cnt].to = from;e[cnt].val = 0;

    e[cnt].cost = -cost, e[cnt].next = v[to];v[to] = cnt++;

}

bool spfa(int s, int t, int n)

{

    memset(pre, -1, sizeof(pre)); memset(vst, 0, sizeof(vst));

    int head, tail; head = tail = 0;

    for(int i = 1; i <= n; i++) dis[i] = Max;

    que[tail++] = s; pre[s] = s; dis[s] = 0; vst[s] = 1;

    while(head != tail)

    {

        int id = que[head++]; vst[id] = 0;

        id = v[id];

        while(id != -1)

        {

            if (e[id].val > 0 && dis[e[id].from] + e[id].cost < dis[e[id].to])

            {

                dis[e[id].to] = dis[e[id].from] + e[id].cost;

                pre[e[id].to] = e[id].from; pos[e[id].to] = id;

                if (!vst[e[id].to])

                {

                    vst[e[id].to] = 1;

                    que[tail++] = e[id].to;

                }

            }

            id = e[id].next;

        }

    }

    return pre[t] != -1 && dis[t] < Max;

}

int flow;

int MinCostFlow(int s, int t, int n)

{

    flow = 0; int cost = 0;

    while(spfa(s, t, n))

    {

        int fl = Max;

        for(int i = t; i != s; i = pre[i])

            if (e[pos[i]].val < fl) fl = e[pos[i]].val;

        flow += fl; cost += dis[t] * fl;

        for(int i = t; i != s; i = pre[i])

        {

            e[pos[i]].val -= fl;

            e[pos[i] ^ 1].val += fl;

        }

    }

    return cost; // flow是最大流值

}

int rd[200], cd[200];

int main()

{

    int tt, ca = 1; scanf("%d", &tt);while(tt--)

    {

        int n, m, a, b;

        scanf("%d%d%d%d", &n, &m, &a, &b);

        int s = 0, t = n + 1;

        memset(v, -1, sizeof(v)); cnt = 0; int sum = 0;

        memset(rd, 0, sizeof(rd));

        memset(cd, 0, sizeof(cd));

        for(int i = 0; i < m; i++)

        {

            int from, to, aa, bb;

            scanf("%d%d%d%d", &from ,&to, &aa, &bb);

            if (bb >= aa)

            {

                insert(from, to, 1, bb - aa);

                sum += aa;

                cd[from]++; rd[to]++;

            }else

            {

                insert(to, from, 1, aa - bb);

                sum += bb;

            }

        }

        int mm = 0, nn = 0;

        for(int i = 1; i <= n; i++)

        {

            int val = cd[i] - rd[i];

            if (i == a) val--;

            if (i == b) val++;

            if (val > 0) insert(s, i, val, 0), mm += val;

            else if (val < 0) insert(i, t, -val, 0), nn += -val;

        }

        int cost = MinCostFlow(s, t, t + 1);

        printf("Case %d: ", ca++);

        if (flow == mm && flow == nn) printf("%d\n", sum + cost);

        else printf("impossible\n");

    }

    return 0;

}