UVa 11865 Stream My Contest 二分+最小樹形圖

題目來源：UVa 11865 Stream My Contest

題意：0是服務器 其他每個點要接收到0傳送的數據 並且每條路單向 有最大帶寬和花費 求總花費不超過c的最大帶寬

思路：單向的0是根 是一顆有向樹 要最大化帶寬 是樹中所有邊最小的帶寬盡量大 然後總得花費不超過n 二分最小帶寬 然後選出帶寬大雨二分mid值的邊

判斷是否存在最小樹形圖 存在說明mid值可行 此外沒有用到白書上的兩個預處理

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
const int maxn = 66;
const int maxm = 10010;
const int INF = 999999999;
struct edge
{
	int u, v, b, c;
	edge(){}
	edge(int u, int v, int b, int c): u(u), v(v), b(b), c(c){}
};
edge e[maxm], a[maxm];
int c;
int pre[maxn];
int in[maxn];
int no[maxn];
int vis[maxn];
int MST(int n, int m, int rt)
{
	int ans = 0;
	while(1)
	{
		for(int i = 1; i <= n; i++)
			in[i] = INF;
		for(int i = 1; i <= m; i++)
		{
			int u = e[i].u;
			int v = e[i].v;
			if(u != v && in[v] > e[i].c)
			{
				pre[v] = u;
				in[v] = e[i].c;
			}
		}
		for(int i = 1; i <= n; i++)
		{
			
			if(i == rt)
				continue;
			if(in[i] == INF)
				return -1;
				
		}
		memset(no, -1, sizeof(no));
		memset(vis, -1, sizeof(vis));
		in[rt] = 0;
		int cnt = 0;
		for(int i = 1; i <= n; i++)
		{
			ans += in[i];
			int v = i;
			while(v != rt && vis[v] != i && no[v] == -1)
			{
				vis[v] = i;
				v = pre[v];
			}
			if(v != rt && no[v] == -1)
			{
				for(int u = pre[v]; u != v; u = pre[u])
					no[u] = cnt+1;
				no[v] = cnt+1;
				cnt++;
			}
		}
		if(!cnt)
		{
			if(ans > c)
				return -1;
			return ans;
		}
		for(int i = 1; i <= n; i++)
			if(no[i] == -1)
				no[i] = ++cnt;
		for(int i = 1; i <= m; i++)
		{
			int u = e[i].u;
			int v = e[i].v;
			e[i].u = no[u];
			e[i].v = no[v];
			if(no[u] != no[v])
			{
				e[i].c -= in[v];
			}
		}
		n = cnt;
		rt = no[rt];
	}
	return ans;
}

int main()
{
	int cas = 1;
	int T;
	scanf("%d", &T);
	while(T--)
	{
		int n, m;
		scanf("%d %d %d", &n, &m, &c);
		int l = INF;
		int r = 0;
		for(int i = 1; i <= m; i++)
		{
			scanf("%d %d %d %d", &a[i].u, &a[i].v, &a[i].b, &a[i].c);
			a[i].u++;
			a[i].v++;
			l = min(l, a[i].b);
			r = max(r, a[i].b);
			e[i] = a[i];
		}
		if(MST(n, m, 1) == -1)
		{
			printf("streaming not possible.\n");
			continue;
		}
		int ans = 0;
		while(l <= r)
		{
			int mid = (l + r) >> 1;
			int num = 0;
			for(int i = 1; i <= m; i++)
			{
				if(a[i].b >= mid)
					e[++num] = a[i];
			}
			int temp = MST(n, num, 1);
			if(temp == -1)
			{
				r = mid-1;
			}
			else
			{
				ans = mid;
				l = mid+1;
			}
		}
		printf("%d kbps\n", ans);
	}
	return 0;
}