uva好题真多
本题用二分法找flow，把流量小于flow的全部筛掉，剩下的边建立最小树形图，如果权值大于c或者不能建图，那么修改二分边界
上代码，觉得最小树形图的代码很优美
/* 题意：给定n个点，m条边，c块钱 m条单向边 带有流量，并且会消耗一些钱 问怎么建立最大流量图 二分流量，找到流量最大的能使消费低于c的方案 在朱刘算法时筛掉所有流量小于当前流量的网络边 */ #include<iostream> #include<cstring> #include<cstdio> #define MAXN 10005 #define INF 0x3f3f3f3f #define ll long long using namespace std; struct Node{ int u,v,cost; }e[MAXN]; int pre[MAXN],id[MAXN],vis[MAXN]; ll in[MAXN]; ll zhuliu(int root,int n,int m){ ll res=0; while(1){ for(int i=0;i<n;i++) in[i]=INF; for(int i=0;i<m;i++) if(e[i].u!=e[i].v && e[i].cost<in[e[i].v]){ pre[e[i].v]=e[i].u; in[e[i].v]=e[i].cost; } for(int i=0;i<n;i++) if(i!=root && in[i]==INF) return -1; int tn=0; memset(id,-1,sizeof id); memset(vis,-1,sizeof vis); in[root]=0; for(int i=0;i<n;i++){ res+=in[i]; int v=i; while(v!=root && id[v]==-1 && vis[v]!=i){ vis[v]=i; v=pre[v]; } if(id[v]==-1 && v!=root){ for(int u=pre[v];u!=v;u=pre[u]) id[u]=tn; id[v]=tn++; } } if(tn==0) break; for(int i=0;i<n;i++) if(id[i]==-1) id[i]=tn++; for(int i=0;i<m;i++){ int v=e[i].v; e[i].u=id[e[i].u]; e[i].v=id[e[i].v]; if(e[i].u!=e[i].v) e[i].cost-=in[v]; } n=tn; root=id[root]; } return res; } struct Edge{ int u,v,cost; int flow; //网络的最大带宽 }edge[MAXN]; int judge(int flow,int n,int m,ll c){ int totm=0;//筛选边 for(int i=0;i<m;i++) if(flow<=edge[i].flow){ e[totm].u=edge[i].u; e[totm].v=edge[i].v; e[totm++].cost=edge[i].cost; } int root=0; int res=zhuliu(root,n,totm); if(res==-1 || res>c) return 0; else return 1; } int main(){ int T,n,m; ll c; cin >> T; while(T--){ scanf("%d%d%lld",&n,&m,&c); int l=9999999,r=0,mid; for(int i=0;i<m;i++){//先输入所有边 scanf("%d%d%d%d",&edge[i].u,&edge[i].v,&edge[i].flow,&edge[i].cost); l=min(l,edge[i].flow); r=max(r,edge[i].flow); } if(!judge(l,n,m,c)){ printf("streaming not possible. "); continue; } while(l<r){ mid = l+(r-l+1)/2; if(judge(mid,n,m,c))//mid流量可以联通 l=mid; else //无法联通，说明流量开大了 r=mid-1; } //二分到最后肯定是l==r printf("%d kbps ",r); } return 0; }