uva11865 二分+最小树形图（朱刘算法）

  1 /*uva11865 二分+最小树形图（朱刘算法）
  2 注意二分的写法，树形图可作为模板，ps：杭电的模板有问题
  3 */
  4 #include<iostream>
  5 #include<string.h>
  6 #include<stdio.h>
  7 #include<stdlib.h>
  8 #include<cmath>
  9 #include<algorithm>
 10 #include<queue>
 11 #include<stack>
 12 #include<set>
 13 #include<map>
 14 #define typec int
 15 #define maxn 100+5
 16 #define maxe 10000+5
 17 using namespace std;
 18 
 19 const typec inf=0x3f3f3f3f;
 20 int nextint(){int x;scanf("%d",&x);return x;}
 21 struct Edge{
 22     int u,v;
 23     int b;
 24     typec c;//权值
 25 }edges[maxe],edge[maxe];
 26 
 27 int vis[maxn],pre[maxn],id[maxn],in[maxn],cost;
 28 int zhuliu(int root,int nv,int ne){//最小树形图
 29       int i,j,u,v;
 30       int ans=0;
 31       while(1){
 32               for(i=0;i<nv;i++)in[i]=inf;
 33               for(i=0;i<ne;i++){
 34                       u=edge[i].u;
 35                       v=edge[i].v;
 36                       if(u!=v&&edge[i].c<in[v]){
 37                               pre[v]=u;
 38                               in[v]=edge[i].c;
 39                       }
 40               }
 41               in[root]=0;
 42               for(i=0;i<nv;i++)if(in[i]==inf)return -1;
 43               int cnt=0;
 44               memset(id,-1,sizeof(id));
 45               memset(vis,-1,sizeof(vis));
 46               for(i=0;i<nv;i++){
 47                       v=i;
 48                       ans+=in[i];
 49                       while(vis[v]!=i&&id[v]==-1&&v!=root){
 50                               vis[v]=i;
 51                               v=pre[v];
 52                       }
 53                       if(v!=root&&id[v]==-1){
 54                               for(u=pre[v];u!=v;u=pre[u])id[u]=cnt;
 55                               id[v]=cnt++;
 56                       }
 57               }
 58               if(cnt==0)break;
 59               for(i=0;i<nv;i++)if(id[i]==-1)id[i]=cnt++;
 60               for(i=0;i<ne;i++){
 61                       v=edge[i].v;
 62                       edge[i].u=id[edge[i].u];
 63                       edge[i].v=id[edge[i].v];
 64                       if(edge[i].u!=edge[i].v)edge[i].c-=in[v];
 65               }
 66               nv=cnt;root=id[root];
 67       }
 68         return ans;
 69 }
 70 int T,Cost,n,m;
 71 int cnt;
 72 void built_tree(int M){
 73     cnt=0;
 74     for(int i=0;i<m;i++)
 75     if (edges[i].b>=M) edge[cnt++]=edges[i];
 76 }
 77 int main(){
 78 //    freopen("out.txt","w",stdout);
 79     cin>>T;
 80     while(cin>>n>>m>>Cost){
 81         int L=0,R=0;
 82         for(int i=0;i<m;i++) {
 83             int u,v,b,c;
 84             u=nextint();v=nextint();b=nextint();c=nextint();
 85             edges[i]=(Edge){u,v,b,c};
 86             R=max(R,edges[i].b);
 87         }
 88         bool ok=false;int ans=0;
 89         while(L<R){
 90             int M=(L+R+1)/2;
 91             built_tree(M);
 92             int mc=zhuliu(0,n,cnt);
 93             if (mc>0 && mc<=Cost) {
 94                 ok=true;
 95                 ans=L=M;
 96             }else R=M-1;
 97         }
 98         if (ok) printf("%d kbps
",ans);else printf("streaming not possible.
");
 99 
100     }
101     return 0;
102 }