HDU 4067 Random Maze

意甲冠军：

一个“随机图”它被定义为具有以下性质如：

一个入口和一个出口

有向图

对于入口  出度比入度大1

对于出口  入度比出度大1

对于其它点  入度等于出度

现给出一幅有向图  每条边有2个决策——留下、扔掉  分别花费a和b  问  假设用最少的费用改造出“随机图”

思路：

网络流不错的题目  假设做过“混合图欧拉回路”（后文把这个问题成为p）那个zoj的题的话  这道题会有启示

来回顾p的做法  先将无向边任意定向  再利用度来将点划分成二分图  利用无向边建边  利用度连接这些点与源汇  然后做maxflow  满流则有解

“任意定向”启示我们本题也能够对边进行一定的处理  因此我们能够先比較a和b  取当中小的状态  这样得到的一定是费用最小的决策  但不保证是“随机图”  那么此时我们仅仅须要改变决策  在费用最小的情况下达到“随机图”  此时想到了费用流

“利用度构图”启示我们相同讨论  in>out  in==out  in<out  的三种点（事实上入口和出口能够稍加处理归并到一般点中去）  对于 in>out 的点  我们与S连边  对于 in<out 的点  我们与T连边  容量即为|in-out|  来表示这个点须要修正的度数

尽管我们的图不是二分图  可是层次关系仍然明显

我们将m条输入的边依照a和b的大小关系  分别建边u->v 容量1 费用b-a 表示将边从留下状态改为扔掉状态  反之亦然

那么此时流量就表示通过更改边的策略  能将多少“度”平衡掉  也就是说  假设maxflow满流  则能够构成“随机图”

剩下的就是最小费用  非常明显就是刚才建边的费用之和  最后费用+“随即定向”时的最小花费就是答案

PS：要尽量去理解网络流中“流”的实际意义  想办法构造图

代码：

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<cstdlib>
#include<ctime>
#include<cmath>
using namespace std;
typedef long long LL;
#define N 110
#define M 2010
#define inf (1<<20)

int casnum, cas, n, m, s, t, S, T, ans, tot, flow, totflow, cost;
int head[N], pre[N], vis[N], dis[N], din[N], dout[N], temp[N];
struct edge {
	int u, v, w, c, next;
} ed[N * M];
queue<int> qu;

void init() {
	S = 0;
	T = n + 1;
	ans = 0;
	tot = 0;
	totflow = 0;
	flow = 0;
	cost = 0;
	memset(head, -1, sizeof(head));
	memset(din, 0, sizeof(din));
	memset(dout, 0, sizeof(dout));
}

void add(int U, int V, int W, int C) {
	ed[tot].u = U;
	ed[tot].v = V;
	ed[tot].w = W;
	ed[tot].c = C;
	ed[tot].next = head[U];
	head[U] = tot++;

	ed[tot].u = V;
	ed[tot].v = U;
	ed[tot].w = 0;
	ed[tot].c = -C;
	ed[tot].next = head[V];
	head[V] = tot++;
}

int spfa() {
	int i, u, v;
	while (!qu.empty())
		qu.pop();
	for (i = 0; i <= T; i++) {
		vis[i] = 0;
		dis[i] = inf;
		pre[i] = -1;
	}
	qu.push(S);
	vis[S] = 1;
	dis[S] = 0;
	while (!qu.empty()) {
		u = qu.front();
		qu.pop();
		vis[u] = 0;
		for (i = head[u]; ~i; i = ed[i].next) {
			if (!ed[i].w)
				continue;
			v = ed[i].v;
			if (dis[v] > dis[u] + ed[i].c) {
				dis[v] = dis[u] + ed[i].c;
				pre[v] = i;
				if (!vis[v]) {
					vis[v] = 1;
					qu.push(v);
				}
			}
		}
	}
	return dis[T] != inf;
}

void mcmf() {
	int i, tmp;
	while (spfa()) {
		tmp = inf;
		for (i = pre[T]; ~i; i = pre[ed[i].u]) {
			if (tmp > ed[i].w)
				tmp = ed[i].w;
		}
		for (i = pre[T]; ~i; i = pre[ed[i].u]) {
			ed[i].w -= tmp;
			ed[i ^ 1].w += tmp;
			cost += tmp * ed[i].c;
		}
		flow += tmp;
	}
}

struct input {
	int u, v, a, b;
} f[M];

int main() {
	int i, u, v, a, b;
	scanf("%d", &casnum);
	for (cas = 1; cas <= casnum; cas++) {
		scanf("%d%d%d%d", &n, &m, &s, &t);
		init();
		for (i = 1; i <= m; i++) {
			scanf("%d%d%d%d", &u, &v, &a, &b);
			f[i].u = u;
			f[i].v = v;
			f[i].a = a;
			f[i].b = b;
			if (a < b) { //stay
				ans += a;
				din[v]++;
				dout[u]++;
				add(u, v, 1, f[i].b - f[i].a);
			} else {
				ans += b; //remove
				add(v, u, 1, f[i].a - f[i].b);
			}
		}
		for (i = 1; i <= n; i++) {
			temp[i] = dout[i] - din[i];
			if (i == s)
				temp[i]--;
			else if (i == t)
				temp[i]++;
			if (temp[i] > 0) {
				add(S, i, temp[i], 0);
				totflow += temp[i];
			} else if (temp[i] < 0)
				add(i, T, -temp[i], 0);
		}
		mcmf();
		printf("Case %d: ", cas);
		if (totflow == flow)
			printf("%d\n", ans + cost);
		else
			printf("impossible\n");
	}
	return 0;
}