题目链接
题意：题意：你需要花费不超过cost元来搭建一个比赛网络。网络中有n台机器，编号0~n-1，其中机器0为服务器，其他机器为客户机。一共有m条可以使用的网线，其中第i条网线的发送端是机器ui，接收端是机器vi（数据只能从机器ui单向传输到机器vi），带宽是bi Kbps,费用是ci元。每台客户机应当恰好从一台机器接收数据。你的任务是最大化网络中的最小带宽。
solution：最小树形图 朱刘算法。
ps：边的值会随时改变。
#include <cstdio>
#include <iostream>
#include <cstring>
#include <vector>
#include <cstdlib>
#include <algorithm>
using namespace std;
const int N =
1010;
const int M =
1010000;
#define LL long long
#define Inf 0x7fffffff
int in[N], pre[N], id[N], use[N];
struct Edge{
int u, v, w, bit; }ee[M], e[M];
LL ZhuLiu(
const int k,
const int m,
const int cost,
const int bt,
int root){
long long ans=
0;
int n=k;
memset(pre,
0,
sizeof(pre));
memset(in,
0,
sizeof(in));
while(
1){
for (
int i=
0; i<n; i++ ) in[i]=Inf;
for (
int i=
1; i<=m; i++ ){
if( e[i].bit<bt )
continue;
int u=e[i].u, v=e[i].v;
if( e[i].w<in[v] && u!=v ){
in[v]=e[i].w;
pre[v]=u;
}
}
for (
int i=
0; i<n; i++ ){
if( i==root )
continue;
ans+=in[i];
if( in[i]==Inf )
return -
1;
}
if( ans>cost )
return -
1;
memset(id,-
1,
sizeof(id));
memset(use,-
1,
sizeof(use));
int cnt=
0;
for (
int i=
0; i<n; i++ ){
int v=i;
while( v!=root && use[v]!=i && id[v]==-
1 ){
use[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<n; i++ )
if( id[i]==-
1 ){
id[i]=cnt++;
}
for (
int i=
1; i<=m; i++ ){
if( e[i].bit<bt )
continue;
int u=e[i].u, v=e[i].v;
e[i].u=id[u];
e[i].v=id[v];
if( e[i].u!=e[i].v ) e[i].w-=in[v];
}
root=id[root];
n=cnt;
}
return ans;
}
int main(){
int T;
int n, m, cost;
scanf(
"%d", &T);
while( T-- ){
scanf(
"%d%d%d", &n, &m, &cost);
for (
int i=
1; i<=m; i++ )
scanf(
"%d%d%d%d", &ee[i].u, &ee[i].v, &ee[i].bit, &ee[i].w ), e[i]=ee[i];
int l =
1, r =
1000000;
int ans =
0;
while(l <= r){
int mid = (l+r)>>
1;
long long ret=ZhuLiu(n, m, cost, mid,
0);
for (
int i=
1; i<=m; i++ ) e[i]=ee[i];
if(ret!=-
1)
l = mid+
1, ans = max(ans, mid);
else r = mid-
1;
}
ans==
0 ?
puts(
"streaming not possible."):
printf(
"%d kbps\n",ans);
}
}
