题目链接:http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2965
白书P347
#include <stdio.h> #include <string.h> #include <iostream> #include <algorithm> #include <math.h> using namespace std; /* * 最小树形图 * 复杂度O(NM) * 点下标[0,n-1] 边下标[0,m-1] * 有向边表示:u->v 花费为cost * 返回最小树形图的边权和,-1表示不存在最小树形图 */ const int INF = 100000000; const int MAXN = 1010; //点数 const int MAXM = 1010000;//边数 #define ll int struct Edge{ int u,v; ll cost; }edge[MAXM]; int pre[MAXN],id[MAXN],visit[MAXN],edgenum; void addedge(int u, int v, int cost){ Edge E = {u, v, cost}; edge[edgenum++] = E; } ll in[MAXN]; ll zhuliu(int root,int n,int m,Edge edge[], int c)//树根(注意是有向树,树根不能任意) 点数 边数 edge { int u,v; ll res=0; while(1) { for(int i = 0;i < n;i++) in[i] = INF; for(int i = 0;i < m;i++) if(edge[i].u != edge[i].v && edge[i].cost < in[edge[i].v]) { pre[edge[i].v] = edge[i].u; in[edge[i].v] = edge[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(visit,-1,sizeof(visit)); in[root] = 0; for(int i = 0;i < n;i++) { res += in[i]; if(res>c)return -1; v = i; while( visit[v] != i && id[v] == -1 && v != root) { visit[v] = i; v = pre[v]; } if( v != root && id[v] == -1 ) { 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;) { v = edge[i].v; edge[i].u = id[edge[i].u]; edge[i].v = id[edge[i].v]; if(edge[i].u != edge[i].v) edge[i++].cost -= in[v]; else swap(edge[i],edge[--m]); } n = tn; root = id[root]; } return res; //-1为不存在最小树形图 } void init(){ edgenum = 0; } struct node{ ll u,v,bit,cost; }E[MAXM]; int n, m, c; bool ok(int x){ init(); for(int i = 0; i < m; i++)if(E[i].bit>=x) addedge(E[i].u,E[i].v,E[i].cost); int ans = zhuliu(0,n,edgenum,edge,c); return ans<=c && ans!=-1; } int main(){ int T,i;scanf("%d",&T); while(T--){ scanf("%d %d %d",&n,&m,&c); for(i = 0; i < m; i++)scanf("%d %d %d %d",&E[i].u,&E[i].v,&E[i].bit,&E[i].cost); int l = 1, r = 1000000; int ans = 0; while(l <= r){ int mid = (l+r)>>1; if(ok(mid)) l = mid+1, ans = max(ans, mid); else r = mid-1; } ans==0 ? puts("streaming not possible."):printf("%d kbps\n",ans); } return 0; } /* 3 3 4 300 0 1 128 100 1 2 256 200 2 1 256 200 0 2 512 300 3 4 500 0 1 128 100 1 2 256 200 2 1 256 200 0 2 512 300 3 4 100 0 1 128 100 1 2 256 200 2 1 256 200 0 2 512 300 */
原文:http://blog.csdn.net/acmmmm/article/details/19835721