Random Maze

In the game “A Chinese Ghost Story”, there are many random mazes which have some characteristic：
1.There is only one entrance and one exit.
2.All the road in the maze are unidirectional.
3.For the entrance, its out-degree = its in-degree + 1.
4.For the exit, its in-degree = its out-degree + 1.
5.For other node except entrance and exit, its out-degree = its in-degree.

There is an directed graph, your task is removing some edge so that it becomes a random maze. For every edge in the graph, there are two values a and b, if you remove the edge, you should cost b, otherwise cost a.
Now, give you the information of the graph, your task if tell me the minimum cost should pay to make it becomes a random maze.

2
2 1 1 2
2 1 2 3
5 6 1 4
1 2 3 1
2 5 4 5
5 3 2 3
3 2 6 7
2 4 7 6
3 4 10 5

Case 1: impossible
Case 2: 27

//546MS	512K
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
#include<cstdio>
using namespace std;
const int MAXN=8007;
const int inf=1<<29;
int pre[MAXN];          // pre[v] = k：在增广路上，到达点v的边的编号为k
int dis[MAXN];          // dis[u] = d：从起点s到点u的路径长为d
int vis[MAXN];         // inq[u]：点u是否在队列中
int path[MAXN];
int head[MAXN];
int NE,tot,ans,max_flow;
int in[107];
struct node
{
    int u,v,cap,cost,next;
} Edge[MAXN<<2];
void addEdge(int u,int v,int cap,int cost)
{
    Edge[NE].u=u;
    Edge[NE].v=v;
    Edge[NE].cap=cap;
    Edge[NE].cost=cost;
    Edge[NE].next=head[u];
    head[u]=NE++;
    Edge[NE].v=u;
    Edge[NE].u=v;
    Edge[NE].cap=0;
    Edge[NE].cost=-cost;
    Edge[NE].next=head[v];
    head[v]=NE++;
}
int SPFA(int s,int t)                   //  源点为0，汇点为sink。
{
    int i;
    for(i=s;i<=t;i++) dis[i]=inf;
    memset(vis,0,sizeof(vis));
    memset(pre,-1,sizeof(pre));
    dis[s] = 0;
    queue<int>q;
    q.push(s);
    vis[s] =1;
 while(!q.empty())        //  这里最好用队列，有广搜的意思，堆栈像深搜。
    {
        int u =q.front();
        q.pop();
        for(i=head[u]; i!=-1;i=Edge[i].next)
        {
            int v=Edge[i].v;
            if(Edge[i].cap >0&& dis[v]>dis[u]+Edge[i].cost)
            {
                dis[v] = dis[u] + Edge[i].cost;
                pre[v] = u;
                path[v]=i;
                if(!vis[v])
                {
                    vis[v] =1;
                    q.push(v);
                }
            }
        }
        vis[u] =0;
    }
    if(pre[t]==-1)
        return 0;
    return 1;
}
void end(int s,int t)
{
    int u, sum = inf;
    for(u=t; u!=s; u=pre[u])
    {
        sum = min(sum,Edge[path[u]].cap);
    }
    max_flow+=sum;                          //记录最大流
    for(u = t; u != s; u=pre[u])
    {
        Edge[path[u]].cap -= sum;
        Edge[path[u]^1].cap += sum;
        ans += sum*Edge[path[u]].cost;     //  cost记录的为单位流量费用，必须得乘以流量。
    }
}
int main()
{
    int n,m,s,t,tt,cas=1;
    scanf("%d",&tt);
    while(tt--)
    {
        memset(head,-1,sizeof(head));
        memset(in,0,sizeof(in));
        NE=ans=max_flow=0;
        int sum=0,u,v,a,b;
        scanf("%d%d%d%d",&n,&m,&s,&t);
        in[s]++;in[t]--;
        int S=0,T=n+1,count=0;
        for(int i=0;i<m;i++)
        {
            scanf("%d%d%d%d",&u,&v,&a,&b);
            if(a<=b)
            {
                in[u]--;in[v]++;
                addEdge(v,u,1,b-a);
                sum+=a;
            }
            else
            {
                addEdge(u,v,1,a-b);
                sum+=b;
            }
        }
        for(int i=1;i<=n;i++)
        {
            if(in[i]>0)addEdge(S,i,in[i],0);
            if(in[i]<0)addEdge(i,T,-in[i],0),count+=-in[i];
        }
        while(SPFA(S,T))
        {
            end(S,T);
        }
        printf("Case %d: ",cas++);
        if(max_flow==count)printf("%d\n",sum+ans);
        else printf("impossible\n");
    }
    return 0;
}