UVA 11865 Stream My Contest 组网 （朱刘算法，有向生成树，树形图）

题意：

　　给n个点编号为0~n-1，0号点为根，给m条边（含自环，重边），每条边有个代价，也有带宽。给定c，问代价不超过c，树形图的最小带宽的最大值能达到多少？

思路：

　　点数才60，而带宽范围也不大，可以进行二分穷举最小带宽，将小于穷举值的边“禁用”，进行求树形图！只要能求得树形图，说明带宽还能继续往上提。

　　注：如果只有根，即n=1，那么输出其中最小的一条边的带宽。而求树形图比较简单，用朱刘算法O(n*m)，网上有模板。

　　朱刘算法的精髓在于：缩点就缩得彻底，将原来的图都给改掉了。如果产生了环，那就缩点，缩点后，属于原来环上的边u-v就会变成一条自环（没用的）。而找环的技术也经典，只是复杂度看起来不止O(n)了，随着环越来越少，复杂度越高。

　　

 #include <bits/stdc++.h>

 #define INF 0x7f7f7f7f

 #define pii pair<int,int>

 #define LL long long

 using namespace std;

 const int M=;

 const int N=;

 struct node

 {

     int from,to;

     int bps,cost;

     node(){};

     node(int from,int to,int bps,int cost):from(from),to(to),bps(bps),cost(cost){};

 }edge[M], cpy[M];

 int edge_cnt, n, m, c;

 void add_node(int from,int to,int bps,int cost)

 {

     edge[edge_cnt]=node(from, to, bps, cost);

     cpy[edge_cnt]=node(from, to, bps, cost);//拷贝

     edge_cnt++;

 }

 int far[N], In[N], ID[N], vis[N];

 bool MST(int bps,int cost,int n,int root)

 {

     LL ans=;

     while(true)

     {

         //找最小边

         for(int i=; i<n; i++)  In[i]=INF;

         for(int i=; i<edge_cnt; i++)

         {

             int u=edge[i].from;

             int v=edge[i].to;

             if(edge[i].cost<In[v] && u!=v && edge[i].bps>=bps)

             {

                 far[v]=u;

                 In[v]=edge[i].cost;

             }

         }

         //判断是否与生成树

         for(int i=; i<n; i++)

         {

             if(i==root)     continue;

             if(In[i]==INF)  return false;    //缩点后root可能不为0

         }

         //找环

         int cntnode=;

         memset(ID,  -, sizeof(ID));     //ID保存的是环的编号

         memset(vis, -, sizeof(vis));

         In[root]=;

         for(int i=; i<n; i++)

         {

             ans+=In[i];

             int v=i;

             while( vis[v]!=i && ID[v]==- && v!=root )  //用vis记录本次寻根所走过的点

             {

                 vis[v]=i;

                 v=far[v];

             }

             if(ID[v]==- && v!=root)

             {

                 for(int u=far[v]; u!=v; u=far[u])

                 {

                     ID[u]=cntnode;

                 }

                 ID[v]=cntnode++;

             }

         }

         if(cntnode==)  break;

         for(int i=;i<n;i++)   //不成环的点，单独作为1个环

             if(ID[i]==-)    ID[i]=cntnode++;

         //有环

         for(int i=; i<edge_cnt; i++)

         {

             int v=edge[i].to;

             edge[i].from =ID[edge[i].from];  //真的缩点,只不过边数仍然一样多

             edge[i].to =ID[edge[i].to];

             if(edge[i].from!=edge[i].to)

             {

                 edge[i].cost-=In[v];    //如果u和v不是同个环，那么v的入边的大小得改了。

             }

         }

         n=cntnode;

         root=ID[root];

     }

     if(ans<=cost)    return  true;

     else    return false;

 }

 int cal(int L,int R,int root)

 {

     while(L<R)    //二分答案

     {

         for(int i=; i<edge_cnt; i++)    edge[i]=cpy[i];    //注意要复制，因为原来的已经改变了

         int mid=L+(R-L+)/;

         if( MST(mid, c, n, root) )  L=mid;

         else       R=mid-;

     }

     return L;

 }

 int main()

 {

     //freopen("input.txt", "r", stdin);

     int t, u, v, a, b;

     cin>>t;

     while(t--)

     {

         scanf("%d%d%d", &n, &m, &c);

         edge_cnt=;

         int down=INF, up=;     //找最大和最小进行二分

         for(int i=; i<m; i++)

         {

             scanf("%d%d%d%d", &u, &v, &a, &b);

             down=min(down, a);

             up=max(up, a);

             add_node(u, v, a, b);

         }

         if(!MST(down, c, n, )) printf("streaming not possible.\n");

         else      printf("%d kbps\n",  cal(down, up, ));   //只有根的情况，输出down

     }

     return ;

 }

AC代码