uva11865 朱刘算法+二分

这题说的需要最多花费cost元来搭建一个比赛网络，网络中有n台机器，编号为0 - n-1其中机器0 为服务器，给了n条线有向的和他们的花费以及带宽计算，使得n台连接在一起，最大化网络中的最小带宽，我们二分答案，然后使用朱刘算法计算最小花费必须<=cost
  1 #include <iostream>
  2 #include <algorithm>
  3 #include <string.h>
  4 #include <vector>
  5 #include <cstdio>
  6 using namespace std;
  7 //出处 http://blog.csdn.net/wsniyufang/article/details/6747406
  8 /*
  9 最小树形图图模版-朱刘算法
 10 模版说明：点标号必须0-(N-1)
 11          必须去除到自身的点（到自身的边的边权赋无限大）
 12 */
 13 typedef long long LL;
 14 const LL inf=(1LL)<<60;
 15 const int maxn =105;
 16 struct Node{
 17     int u , v,b;
 18     LL cost;
 19     bool operator < (const Node &rhs)const{
 20       return b<rhs.b;
 21     }
 22 }E[10000+5],to[10000+5];
 23 int pre[maxn],ID[maxn],vis[maxn];
 24 LL In[maxn];
 25 LL Directed_MST(int root,int NV,int NE) {
 26     LL ret = 0;
 27     while(true) {
 28         //1.找最小入边
 29         for(int i=0;i<NV;i++) In[i] = inf;
 30         for(int i=0;i<NE;i++){
 31             int u = E[i].u;
 32             int v = E[i].v;
 33             if(E[i].cost < In[v] && u != v) {
 34                 pre[v] = u;
 35                 In[v] = E[i].cost;
 36             }
 37         }
 38         for(int i=0;i<NV;i++) {
 39             if(i == root) continue;
 40             if(In[i] == inf)    return -1;//除了跟以外有点没有入边,则根无法到达它
 41         }
 42         //2.找环
 43         int cntnode = 0;
 44     memset(ID,-1,sizeof(ID));
 45     memset(vis,-1,sizeof(vis));
 46         In[root] = 0;
 47         for(int i=0;i<NV;i++) {//标记每个环
 48             ret += In[i];
 49             int v = i;
 50             while(vis[v] != i && ID[v] == -1 && v != root) {
 51                 vis[v] = i;
 52                 v = pre[v];
 53             }
 54             if(v != root && ID[v] == -1) {
 55                 for(int u = pre[v] ; u != v ; u = pre[u]) {
 56                     ID[u] = cntnode;
 57                 }
 58                 ID[v] = cntnode ++;
 59             }
 60         }
 61         if(cntnode == 0)    break;//无环
 62         for(int i=0;i<NV;i++) if(ID[i] == -1) {
 63             ID[i] = cntnode ++;
 64         }
 65         //3.缩点,重新标记
 66         for(int i=0;i<NE;i++) {
 67             int v = E[i].v;
 68             E[i].u = ID[E[i].u];
 69             E[i].v = ID[E[i].v];
 70             if(E[i].u != E[i].v) {
 71                 E[i].cost -= In[v];
 72             }
 73         }
 74         NV = cntnode;
 75         root = ID[root];
 76     }
 77     return ret;
 78 }
 79 int lowbound(int v, int len){
 80      int ans=-1;
 81      int L=0,R=len-1;
 82      while(L<=R){
 83          int mid=(L+R)>>1;
 84          if(to[mid].b>=v){
 85             ans=mid;R=mid-1;
 86          }else{
 87             L=mid+1;
 88          }
 89      }
 90      return ans;
 91 }
 92 int main()
 93 {
 94     int T;
 95     scanf("%d",&T);
 96     for(int cc=1; cc<=T; ++cc){
 97         int n,m;
 98         LL cost;
 99         int R=0,L=0;
100         scanf("%d%d%lld",&n,&m,&cost);
101         for(int i=0; i<m; i++){
102                 scanf("%d%d%d%lld",&to[i].u,&to[i].v,&to[i].b,&to[i].cost);
103                 R=max(to[i].b,R);
104         }
105         for(int i=0; i<m; i++){
106              E[i]=to[i];
107         }
108         LL co= Directed_MST(0,n,m);
109         if(co>cost||co==-1){
110              puts("streaming not possible."); continue;
111         }
112         sort(to,to+m);
113         int ans=-1;
114         while(L<=R){
115              int mid = (L+R)>>1,num=0;
116              int loc = lowbound(mid,m);
117              for(int i=loc; i<m; i++) E[num++]=to[i];
118              LL ccc = Directed_MST(0,n,num);
119              if(ccc<=cost && ccc !=-1 ){
120                 ans = mid; L=mid+1;
121              }else{
122                 R=mid-1;
123              }
124         }
125         printf("%d kbps
",ans);
126     }
127     return 0;
128 }