二分找最小的带宽，然后最小树形图求cost
#include<iostream> #include<string> #include<cstdio> #include<set> #include<map> #include<stack> #include<list> #include<vector> #include<queue> #include<algorithm> #include<cstring> #include<cmath> #include<fstream> using namespace std; typedef long long ll; const int maxn = 10010,INF = 0x3f3f3f3f; int in[maxn],pre[maxn],id[maxn],vis[maxn]; struct node{ int u,v,b,w; }e[maxn],a[maxn]; int n,m,c,l,r; int Directed_MST(int root,int V,int E){ int ans = 0; while(1){ //找入边 for(int i = 0;i < V;++i) in[i] = INF; for(int i = 0;i < E;++i){ //寻找最小入边 int u = e[i].u,v = e[i].v,w = e[i].w; if (u != v && w < in[v]){//排除自环 in[v] = w; pre[v] = u; } } for(int i = 0; i < V; i++) { if(i == root) continue; if(in[i] == INF) return -1;//除了根以外有点没有入边 } //找环 int cnt = 0; memset(vis,-1,sizeof vis); memset(id,-1,sizeof id); in[root] = 0; for(int i = 0;i < V;++i){ ans += in[i]; int v = i; while(vis[v] != i && id[v] == -1 && v != root){//向前找直到出环或到根 vis[v] = i; v = pre[v]; } if(v != root && id[v] == -1)//缩点 { for(int u = pre[v]; u != v; u = pre[u]) id[u] = cnt; id[v] = cnt++; } } if (cnt == 0) break;//无环 for(int i = 0;i < V;++i) if (id[i] == -1) id[i] = cnt++; //建立新图 for(int i = 0;i < E;++i){ int u = e[i].u,v = e[i].v; e[i].u = id[u],e[i].v = id[v]; if (id[u] != id[v]) e[i].w -= in[v];//新边边权减环内旧边权 } V = cnt; root = id[root]; } if (ans > c) ans = -1; return ans; } void build(){ int ans = INF; if (Directed_MST(0,n,m) == -1) { cout << "streaming not possible." << endl; return; } while(l <= r){ int mid = (l + r) >> 1; int cnt = 0; for(int i = 0;i < m;++i){ if (a[i].b >= mid) e[cnt++] = a[i]; } int p = Directed_MST(0,n,cnt); if (p == -1) { r = mid - 1; } else { ans = mid; l = mid + 1; } } cout << ans << " kbps" << endl; } void init(){ cin >> n >> m >> c; l = INF,r = 0; memset(e,0,sizeof e); for(int i = 0;i < m;++i){ scanf("%d %d %d %d", &a[i].u, &a[i].v, &a[i].b, &a[i].w); l = min(l,a[i].b); r = max(r,a[i].b); e[i] = a[i]; } build(); } int main(){ int t; cin >> t; while(t--){ init(); } }