hdu4067

source:  http://acm.hdu.edu.cn/showproblem.php?pid=4067

title     :  Random Maze

分析转载自：  http://blog.csdn.net/fp_hzq/article/details/6852778#reply

分析：说到这题不觉有些肉疼，毕竟比赛的时候构图算是对了，就是没判断a，b的大小，然后一直死循环。。。要是A了，这回就能完美7A了，囧

题目给出一张有向图，要求处理起点和终点的所有点满足入度=出度，起点的入度+1=出度，终点的入度=出度+1，其实也就是构造一个欧拉回路？应该是吧。。。然后就是构图

死循环的原因就是出现负环了，因为费用流不能有负环所以只能构图时加判断ab的大小了

1.对于u到v，如果a<=b，就保留那条边，也就是构建一条v到u的边，容量为1，费用为b-a，并且在答案ans上加a，并且u的出度加1，v的入度加1，这条边的意义就是如果这条保留下来的边要删除的话需要b-a的费用，因为咱们是先累加a了

2.对于u到v，如果a>b，就去掉那条边，也就是构建一条u到v的边，容量为1，费用为a-b，并且在答案ans上加b，并且u的入度加1，v的出度加1，这条边的意义就是如果这条删掉的边要恢复的话需要a-b的费用

3.为了保证起点和终点的条件，虚构一条边从终点到起点，也就是起点的出度加1，终点的入度加1，（不能真的把这条边加进图里，因为这是不可改的边）

4.增加源点S和汇点T，如果点I入度大于出度的话就是增加一条边从源点S到点I，容量为入度-出度，费用为0，相反的就是建一条边从点I到汇点T，容量为出度-入度，费用为0

5.求最小费用流，此时最大流如果=到汇点的所有容量之和，就是有解，答案为费用流+ans，否则无解

#include <stdio.h>
#include <cmath>
#include <algorithm>
using namespace std;
const int N = 105; //点数
const int M = (2000+N)<<1; //边数
const int inf = 0X7FFFFFFF;
struct e{
	int v, nxt;
	int flow;
	int cost;
}es[M];
int fir[N], dist[N], que[N+10], vis[N], par[N], path[N];
int n, en;
int m, s, t;
int in[N], ans, sum;

void add_e(int u, int v, int flow, int cost){
	es[en].v = v; es[en].flow = flow; es[en].cost = cost;
	es[en].nxt = fir[u]; fir[u] = en++;
}
void insert(int u, int v, int flow, int cost){
	add_e(u, v, flow, cost);
	add_e(v, u, 0, -cost);
}
bool spfa(int n, int s, int t){
	int l, r, i, v, u, cur, cnt;
	for(i = 0; i < n; i++) dist[i] = inf, vis[i] = 1;
	l = r = 0;
	que[r++] = s; dist[s] = 0; vis[s] = 0;
	cnt = n+1;
	while(l != r){
		for(v = que[l], l = (l+1)%cnt, cur = fir[v], vis[v] = 1; cur != -1; cur = es[cur].nxt){
			if(es[cur].flow > 0 && es[cur].cost+dist[v] < dist[u = es[cur].v]){
				dist[u] = es[cur].cost+dist[v];
				par[u] = v;
				path[u] = cur;    //path[u]表示的是通过path[u]这条边访问到u这个点的
				if(vis[u]){
					vis[u] = 0;
					if(l != r && dist[u] < dist[que[l]]){ //插入到队首
						l = (l == 0 ? cnt-1 : l-1);
						que[l] = u;
					}else{ //插入到队尾
						que[r] = u;
						r = (r+1)%cnt;
					}
				}
			}
		}
	}
	return dist[t] != inf;
}
int minflow(int n, int s, int t){  //n表示的是节点数,s为源点，t为汇点
	int Min, v, flow = 0;
	while(spfa(n, s, t)){
		Min = inf;
		v = t;
		while(v != s){
			Min = min(Min, es[path[v]].flow);
			v = par[v];
		}
		sum -= Min;
		v = t;
		while(v != s){
			flow += Min*es[path[v]].cost;
			es[path[v]].flow -= Min;
			es[path[v]^1].flow += Min;
			v = par[v];
		}
	}
	return flow;
}
template <typename T>
void getNum(T& a){
	a = 0;
	char ch;
	while(true){
		ch = getchar();
		if(ch >= '0' && ch <= '9') break;
	}
	a = ch - '0';
	while(true){
		ch = getchar();
		if(ch < '0' || ch > '9') break;
		a = a * 10 + ch - '0';
	}
}
bool input(){
	getNum(n);
	getNum(m);
	getNum(s);
	getNum(t);
	int i, u, v, a, b;
	for(i = 0; i <= n+1; i++){
		fir[i] = -1;
		in[i] = 0;
	}
	en = ans = sum = 0;
	for(i = 1; i <= m; i++){
		getNum(u);
		getNum(v);
		getNum(a);
		getNum(b);
		if(a <= b){
			insert(v, u, 1, b - a);
			in[v]++;
			in[u]--;
			ans += a;
		}else{
			insert(u, v, 1, a - b);
			ans += b;
		}
	}
	in[s]++;
	in[t]--;
	for(i = 1; i <= n; i++){
		if(in[i] > 0){
			insert(0, i, in[i], 0);
			sum += in[i];
		}else if(in[i] < 0){
			insert(i, n+1, -in[i], 0);
		}
	}
	s = 0;
	t = n+1;
	return true;
}
int cnt = 0;
void solve(){
	ans += minflow(n+2, s, t);
	if(sum == 0){
		printf("Case %d: %d\n", ++cnt, ans);
	}else{
		printf("Case %d: impossible\n", ++cnt);
	}
}
int main(){
	int t;
	getNum(t);
	while(t--){
		input();
		solve();
	}
	return 0;
}