程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 4067 Random Maze

HDU 4067 Random Maze

編輯：C++入門知識

HDU 4067 Random Maze

題意：

一幅“隨機圖”定義為有如下性質的圖：

有一個入口和一個出口

有向圖

對於入口出度比入度大1

對於出口入度比出度大1

對於其他點入度等於出度

現給出一幅有向圖每條邊有2個決策——留下、扔掉分別花費a和b 問如果用最少的費用改造出“隨機圖”

思路：

網絡流不錯的題目如果做過“混合圖歐拉回路”（後文把這個問題成為p）那個zoj的題的話這道題會有啟發

來回憶p的做法先將無向邊隨意定向再利用度來將點劃分成二分圖利用無向邊建邊利用度連接這些點與源匯然後做maxflow 滿流則有解

“隨意定向”啟發我們本題也可以對邊進行一定的處理因此我們可以先比較a和b 取其中小的狀態這樣得到的一定是費用最小的決策但不保證是“隨機圖” 那麼此時我們只需要改變決策在費用最小的情況下達到“隨機圖” 此時想到了費用流

“利用度構圖”啟發我們同樣討論 in>out in==out inout 的點我們與S連邊對於 in

雖然我們的圖不是二分圖但是層次關系仍然明顯

我們將m條輸入的邊按照a和b的大小關系分別建邊u->v 容量1 費用b-a 表示將邊從留下狀態改為扔掉狀態反之亦然

那麼此時流量就表示通過更改邊的策略能將多少“度”平衡掉也就是說如果maxflow滿流則可以構成“隨機圖”

剩下的就是最小費用很明顯就是剛才建邊的費用之和最後費用+“隨即定向”時的最小花費就是答案

PS：要盡量去理解網絡流中“流”的實際意義想辦法構造圖

代碼：

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
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 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;
}