题目大意：有n台机器（编号为0—n-1,其中机器0是服务器），m条网线(每条网线相当于一条有向边，有相应的带宽和代价)，c的钱

现在要求用m条网线搭建一个网路，使得每台机器都可以从服务器接收到信息，且带宽的最小值达到最大

解题思路：朱刘算法的模版题了，不过加了一个条件，要二分，只要二分一下带宽，在判断一下能否网线能否被使用就可以了
如果连最小的带宽都弄不了，那就表明网路无法建成了，因为枚举值为最小带宽时，每条网线都可以用

#include 
   
     #include 
    
      #define N 100 #define M 10010 #define INF 0x3f3f3f3f #define min(a,b) ((a)<(b)?(a):(b)) #define max(a,b) ((a)>(b)?(a):(b)) #define ll long long struct Edge{ int from, to, b, c; }E[M*2]; int id[N], pre[N], in[N], vis[N]; int tot, n, m, C, Max, Min; void AddEdge(int u, int v, int b, int c) { E[tot + M].from = E[tot].from = u; E[tot + M].to = E[tot].to = v; E[tot + M].b = E[tot].b = b; E[tot + M].c = E[tot].c = c; tot++; } void init() { scanf(%d%d%d, &n, &m, &C); Max = -INF; Min = INF; tot = 0; int u, v, b, c; for (int i = 0; i < m; i++) { scanf(%d%d%d%d, &u, &v, &b, &c); AddEdge(u, v, b, c); Max = max(Max, b); Min = min(Min, b); } } bool Directed_MST(int root, int limit, int n) { ll ans = 0; while (1) { memset(pre, -1, sizeof(pre)); for (int i = 0; i < n; i++) in[i] = INF; int u, v; for (int i = 0; i < m; i++) { u = E[i].from; v = E[i].to; if (u != v && E[i].b >= limit && E[i].c < in[v]) { in[v] = E[i].c; pre[v] = u; } } for (int i = 0; i < n; i++) { if (i == root) continue; if (in[i] == INF) return false; } int subnode = 0, tmp; memset(vis, -1, sizeof(vis)); memset(id, -1, sizeof(id)); in[root] = 0; for (int i = 0; i < n; i++) { ans += in[i]; tmp = i; while (vis[tmp] != i && tmp != root && id[tmp] == -1) { vis[tmp] = i; tmp = pre[tmp]; } if (tmp != root && id[tmp] == -1) { u = pre[tmp]; while (u != tmp) { id[u] = subnode; u = pre[u]; } id[tmp] = subnode++; } } if (subnode == 0) break; for (int i = 0; i < n; i++) { if (id[i] == -1) id[i] = subnode++; } for (int i = 0; i < m; i++) { tmp = E[i].to; E[i].from = id[E[i].from]; E[i].to = id[E[i].to]; if (E[i].from != E[i].to) E[i].c -= in[tmp]; } root = id[root]; n = subnode; } if (ans <= C) return true; return false; } void solve() { if (!Directed_MST(0, Min, n)) { printf(streaming not possible. ); return ; } int r = Max, l = Min, mid; while (l < r) { mid = l + (r - l + 1) / 2; for (int i = 0; i < m; i++) E[i] = E[i + M]; if (Directed_MST(0, mid, n)) l = mid; else r = mid - 1; } printf(%d kbps , r); } int main() { int test; scanf(%d, &test); while (test--) { init(); solve(); } return 0; }
    
   

?