题目来源：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; }