[题解] uva 11865 Stream My Contest (二分+最小树形图)

- 传送门 -

　https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2965

# 11865 - Stream My Contest

Time limit: 1.000 seconds
| Root |  
  |

(题面见pdf)

　

- 题意 -

　对于n个点, m条有向边, 边有两个参数A,B, 现在我们要禁用参数 A 小于 D 的边, 使在参数 B 总和不超过 C (C已给出)的情况下, 插入边使 0 号节点能直接或间接的指向1 - n-1 号节点.
　求最大的 D .
　

- 思路 -

　二分答案.
　将参数A大于等于当前答案的边记录下来, 以参数B作为边的权值去构造最小树形图, 在权值和小于C的情况下构造出来则说明当前答案可行.
　最小树形图的构造见这里.
　
　细节见代码.
　

- 代码 -

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N = 65;
const int M = 1e4 + 5;
const int inf = 0x3f3f3f3f;

struct edge {
	int frm, to, bit, cst;
}W[M];

struct use_edge {
	int frm, to, v;
}E[M];

int IN[N], PRE[N], ID[N], VIS[N];
int sz, n, m, c, cas;

void add_edge(int x) {
	E[++sz].frm = W[x].frm;
	E[sz].to = W[x].to;
	E[sz].v = W[x].cst;
}

bool zhuliu(int rt, int n, int m) {
	int ans = 0;
	while (true) {
		int cnt = 0;
		for (int i = 0; i < n; ++i) {
			IN[i] = inf; ID[i] = VIS[i] = -1;
		}// 该题的节点编号, 环的计数都是从0开始的, 初始化都得为-1
		for (int i = 1; i <= m; ++i)
			if (E[i].frm != E[i].to && IN[E[i].to] > E[i].v) {
				IN[E[i].to] = E[i].v;
				PRE[E[i].to] = E[i].frm;
			}
		for (int i = 0; i < n; ++i)
			if (i != rt && IN[i] == inf) return false;
		IN[rt] = 0;
		for (int i = 0; i < n; ++i) {
			ans += IN[i];
			if (ans > c) return false;
			int v = i;
			while (v != rt && ID[v] == -1 && VIS[v] != i) {
				VIS[v] = i;
				v = PRE[v];
			}
			if (v != rt && ID[v] == -1) {
				for (int j = PRE[v]; j != v; j = PRE[j])
					ID[j] = cnt;
				ID[v] = cnt++;
			}
		}
		if (cnt == 0) break;
		for (int i = 0; i < n; ++i)
			if (ID[i] == -1) ID[i] = cnt++;
		for (int i = 1; i <= m; ++i) {
			int a = E[i].frm, b = E[i].to;
			E[i].frm = ID[a], E[i].to = ID[b];
			if (E[i].frm != E[i].to)
				E[i].v -= IN[b];
		}
		n = cnt;
		rt = ID[rt];
	}
	return ans <= c ? true : false;
}

bool solve(int bt) {
	sz = 0;
	for (int i = 0; i < m; ++i)
		if (W[i].bit >= bt)
			add_edge(i);
	return zhuliu(0, n, sz);
}

int main() {
	scanf("%d", &cas);
	while (cas --) {
		scanf("%d%d%d", &n, &m, &c);
		for (int i = 0; i < m; ++i) {
			scanf("%d%d%d%d", &W[i].frm, &W[i].to, &W[i].bit, &W[i].cst);
			if (W[i].frm == W[i].to) i--, m--;
		}
		int l = 1, r = 1000000, ans = -1;
		while (l <= r) {
			int mid = (l + r) >> 1;
			if (solve(mid)) {
				ans = max(ans, mid);
				l = mid + 1;
			}
			else r = mid - 1;
		}
		if (ans == -1) printf("streaming not possible.
");
		else printf("%d kbps
", ans);
	}
	return 0;
}