题目大意：有一张n个顶点，m条边的有向图，根节点为0。每条边有两个权值，一个是费用c，一个是长度b。问在总费用不超过cost的情况下选出若干条边，使得n个点连通时的边的最短长度的最大值是多少。

题目分析：如果已知这个最短距离的最大值d，则问题就变成了：用长度不小于d的边能否构成一个总权值不大于cost的最小树形图。因此，二分枚举d，用朱-刘 算法判断即可。

 

代码如下：

# include
     
      # include
      
       # include
       
        # include
        
         # include
         
          using namespace std;# define REP(i,s,n) for(int i=s;i
          
           e[i].w){ in[e[i].to]=e[i].w; pre[e[i].to]=e[i].fr; } in[root]=0; REP(i,0,nv) if(in[i]==INF) return -1; int nodeCnt=0; CL(ID,-1); CL(vis,-1); REP(i,0,nv){ res+=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]=nodeCnt; ID[v]=nodeCnt++; } } if(nodeCnt==0) break; REP(i,0,nv) if(ID[i]==-1) ID[i]=nodeCnt++; REP(i,0,ne){ int v=e[i].to; e[i].fr=ID[e[i].fr]; e[i].to=ID[e[i].to]; if(e[i].fr!=e[i].to) e[i].w-=in[v]; } nv=nodeCnt; root=ID[root]; } return res;}int main(){ int T; scanf("%d",&T); while(T--) { scanf("%d%d%d",&n,&m,&cost); int l=0,r=0; REP(i,0,m){ scanf("%d%d%d%d",&e1[i].fr,&e1[i].to,&e1[i].d,&e1[i].w); r=max(r,e1[i].d); } int ans=-1; while(l
           
            =mid) e[cnt++]=e1[i]; int x=judge(0,n,cnt); if(x>0&&x<=cost){ ans=l=mid; }else r=mid-1; } if(ans<0) printf("streaming not possible.\n"); else printf("%d kbps\n",ans); } return 0;}