题意：N台机器，M条有向边，总资金C，现要到搭建一个以0号机（服务器）为跟的网路，已知每条网线可以把数据从u传递到v，其带宽为d，花费为c，且d越大，传输速度越快，问能够搭建的传输速度最快的网络d值是多少？（即：在C的支持下，网络中d的最小值最大是多少？）
一开始把问题想简单了，以为网线可以随便接，其实是确定了u->v的= =
最小树形图，概念蛮好理解的，要学习的话
理论：http://hi.baidu.com/bin183/item/5d93ef69ceb541176895e682
代码标注的很详细：http://blog.csdn.net/hehedounima/article/details/9320173
其实，实质就是不断地缩点。需要注意的是选取以每个点为终点的最小边，以及重建图。
因为看人家缩点部分的代码写得略挫，于是我就写了个更挫的T^T——基于强连通缩点的。。细节在代码里已经标明
#include<cstdio>
#include<cmath>
#include<cstring>
#include<vector>
#include<queue>
#include<stack>
#include<algorithm>
#define clr(a,m) memset(a,m,sizeof(a))
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std; const int MAXN=;
const int MAXM=;
const int INF =1e9; struct Edge{
int u,v,d,c;
}; int _n,m,w;
int root,u[MAXM],v[MAXM],d[MAXM],c[MAXM]; int head[MAXN],tol; int pre[MAXN],low[MAXN],sccno[MAXN],scc_cnt,dfs_clock;
int stk[MAXN],top; bool mark[MAXN];
Edge into[MAXN]; vector<Edge>edge;
vector<int>G[MAXN]; void init()
{
edge.clear();
rep(i,,_n-)//!!写成m-1，RE的泪啊
G[i].clear();
} void add(int u,int v,int d,int c)
{
edge.push_back((Edge){u,v,d,c});
int m=edge.size();
G[u].push_back(m-);
} void build()
{
rep(i,,m-)
add(u[i],v[i],d[i],c[i]);
} void rebuild()
{
rep(i,,m-){
int v=edge[i].v;
edge[i].u=sccno[edge[i].u];//自环会在处理into[]时省略
edge[i].v=sccno[edge[i].v];
if(edge[i].u!=edge[i].v)
edge[i].c-=into[v].c;
}
root=sccno[root];//更新root、n的值
_n=scc_cnt;
} void dfs(int v)//因为into[]里是以终点v记录，所以反向缩点
{
int u;
low[v]=pre[v]=dfs_clock++;
stk[top++]=v; u=into[v].u;
if(u!=root)//!!必不可少
if(!pre[u]){
dfs(u);
low[v]=min(low[v],low[u]);
}else if(!sccno[u])
low[v]=min(low[v],pre[u]); if(low[v]==pre[v]){
scc_cnt++;
do{
u=stk[--top];
sccno[u]=scc_cnt;
}while(u!=v);
}
} int find_scc()
{
scc_cnt=dfs_clock=;
clr(pre,);
clr(sccno,); top=;
rep(i,,_n)
if(!pre[i])
dfs(i);
return scc_cnt;
} bool DMST(int lim,int n)
{
_n=n; init();
build(); int cnt=;
while()
{
clr(mark,);
rep(i,,m-){
if(edge[i].d<lim||edge[i].u==edge[i].v)//注意自环
continue;
if(!mark[edge[i].v]){
into[edge[i].v]=(Edge){edge[i].u,edge[i].v,edge[i].d,edge[i].c};
mark[edge[i].v]=true;
}else if(into[edge[i].v].c>edge[i].c)
into[edge[i].v]=(Edge){edge[i].u,edge[i].v,edge[i].d,edge[i].c};
}
into[root]=(Edge){root,root,,};//处理根 rep(i,,_n){//root的序号随缩点改变
if(i==root)
continue;
if(!mark[i]){
return false;
}
cnt+=into[i].c;
}
if(cnt>w)
return false; if(find_scc()==_n)//若不成环
return true;
else
rebuild();
}
} int main()
{
int T,n;
scanf("%d",&T);
while(T--)
{
int up=,down=INF;
scanf("%d%d%d",&n,&m,&w);
root=; rep(i,,m-){
scanf("%d%d%d%d",&u[i],&v[i],&d[i],&c[i]);
u[i]++;v[i]++;//注意scc_cnt是从1开始的，意味着所有的点都是1~n
up=max(up,d[i]);
down=min(down,d[i]);
} if(!DMST(down,n)){
printf("streaming not possible.\n");
continue;
} int l=down,r=up;
while(l<r)
{
int x=l+(r-l+)/;
if(DMST(x,n))
l=x;
else
r=x-;
}
printf("%d kbps\n",l);
}
return ;
}
/*
3
7 15 29
0 1 1 9
0 4 1 5
1 3 1 9
1 2 1 3
2 1 1 7
2 6 1 6
2 5 1 9
3 0 1 3
3 2 1 8
3 5 1 5
4 3 1 4
5 4 1 3
5 6 1 4
6 2 1 4
6 5 1 8
*/