UVA 11865 Stream My Contest(最小树形图)

题意：N台机器，M条有向边，总资金C，现要到搭建一个以0号机（服务器）为跟的网路，已知每条网线可以把数据从u传递到v，其带宽为d，花费为c，且d越大，传输速度越快，问能够搭建的传输速度最快的网络d值是多少？（即：在C的支持下，网络中d的最小值最大是多少？）

一开始把问题想简单了，以为网线可以随便接，其实是确定了u->v的= =

最小树形图，概念蛮好理解的，要学习的话

理论：http://hi.baidu.com/bin183/item/5d93ef69ceb541176895e682

代码标注的很详细：http://blog.csdn.net/hehedounima/article/details/9320173

其实，实质就是不断地缩点。需要注意的是选取以每个点为终点的最小边，以及重建图。

因为看人家缩点部分的代码写得略挫，于是我就写了个更挫的T^T——基于强连通缩点的。。细节在代码里已经标明

  1 #include<cstdio>
  2 #include<cmath>
  3 #include<cstring>
  4 #include<vector>
  5 #include<queue>
  6 #include<stack>
  7 #include<algorithm>
  8 #define clr(a,m) memset(a,m,sizeof(a))
  9 #define rep(i,a,b) for(int i=a;i<=b;i++)
 10 using namespace std;
 11 
 12 const int MAXN=66;
 13 const int MAXM=11111;
 14 const int INF =1e9;
 15 
 16 struct Edge{
 17     int u,v,d,c;
 18 };
 19 
 20 int _n,m,w;
 21 int root,u[MAXM],v[MAXM],d[MAXM],c[MAXM];
 22 
 23 int head[MAXN],tol;
 24 
 25 int pre[MAXN],low[MAXN],sccno[MAXN],scc_cnt,dfs_clock;
 26 int stk[MAXN],top;
 27 
 28 bool mark[MAXN];
 29 Edge into[MAXN];
 30 
 31 vector<Edge>edge;
 32 vector<int>G[MAXN];
 33 
 34 void init()
 35 {
 36     edge.clear();
 37     rep(i,0,_n-1)//!!写成m-1，RE的泪啊
 38         G[i].clear();
 39 }
 40 
 41 void add(int u,int v,int d,int c)
 42 {
 43     edge.push_back((Edge){u,v,d,c});
 44     int m=edge.size();
 45     G[u].push_back(m-1);
 46 }
 47 
 48 void build()
 49 {
 50     rep(i,0,m-1)
 51         add(u[i],v[i],d[i],c[i]);
 52 }
 53 
 54 void rebuild()
 55 {
 56     rep(i,0,m-1){
 57         int v=edge[i].v;
 58         edge[i].u=sccno[edge[i].u];//自环会在处理into[]时省略
 59         edge[i].v=sccno[edge[i].v];
 60         if(edge[i].u!=edge[i].v)
 61             edge[i].c-=into[v].c;
 62     }
 63     root=sccno[root];//更新root、n的值
 64     _n=scc_cnt;
 65 }
 66 
 67 void dfs(int v)//因为into[]里是以终点v记录，所以反向缩点
 68 {
 69     int u;
 70     low[v]=pre[v]=dfs_clock++;
 71     stk[top++]=v;
 72 
 73     u=into[v].u;
 74     if(u!=root)//!!必不可少
 75         if(!pre[u]){
 76             dfs(u);
 77             low[v]=min(low[v],low[u]);
 78         }else if(!sccno[u])
 79             low[v]=min(low[v],pre[u]);
 80 
 81     if(low[v]==pre[v]){
 82         scc_cnt++;
 83         do{
 84             u=stk[--top];
 85             sccno[u]=scc_cnt;
 86         }while(u!=v);
 87     }
 88 }
 89 
 90 int find_scc()
 91 {
 92     scc_cnt=dfs_clock=0;
 93     clr(pre,0);
 94     clr(sccno,0);
 95 
 96     top=0;
 97     rep(i,1,_n)
 98         if(!pre[i])
 99             dfs(i);
100     return scc_cnt;
101 }
102 
103 bool DMST(int lim,int n)
104 {
105     _n=n;
106 
107     init();
108     build();
109     
110     int cnt=0;
111     while(1)
112     {
113         clr(mark,0);
114         rep(i,0,m-1){
115             if(edge[i].d<lim||edge[i].u==edge[i].v)//注意自环
116                 continue;
117             if(!mark[edge[i].v]){
118                 into[edge[i].v]=(Edge){edge[i].u,edge[i].v,edge[i].d,edge[i].c};
119                 mark[edge[i].v]=true;
120             }else if(into[edge[i].v].c>edge[i].c)
121                 into[edge[i].v]=(Edge){edge[i].u,edge[i].v,edge[i].d,edge[i].c};
122         }
123         into[root]=(Edge){root,root,0,0};//处理根
124 
125         rep(i,1,_n){//root的序号随缩点改变
126             if(i==root)
127                 continue;
128             if(!mark[i]){
129                 return false;
130             }
131             cnt+=into[i].c;
132         }
133         if(cnt>w)
134             return false;
135 
136         if(find_scc()==_n)//若不成环
137             return true;
138         else
139             rebuild();
140     }
141 }
142 
143 int main()
144 {
145     int T,n;
146     scanf("%d",&T);
147     while(T--)
148     {
149         int up=0,down=INF;
150         scanf("%d%d%d",&n,&m,&w);
151         root=1;
152 
153         rep(i,0,m-1){
154             scanf("%d%d%d%d",&u[i],&v[i],&d[i],&c[i]);
155             u[i]++;v[i]++;//注意scc_cnt是从1开始的，意味着所有的点都是1~n
156             up=max(up,d[i]);
157             down=min(down,d[i]);
158         }
159 
160         if(!DMST(down,n)){
161             printf("streaming not possible.
");
162             continue;
163         }
164 
165         int l=down,r=up;
166         while(l<r)
167         {
168             int x=l+(r-l+1)/2;
169             if(DMST(x,n))
170                 l=x;
171             else
172                 r=x-1;
173         }
174         printf("%d kbps
",l);
175     }
176     return 0;
177 }
178 /*
179 3
180 7 15 29
181 0 1 1 9
182 0 4 1 5
183 1 3 1 9
184 1 2 1 3
185 2 1 1 7
186 2 6 1 6
187 2 5 1 9
188 3 0 1 3
189 3 2 1 8
190 3 5 1 5
191 4 3 1 4
192 5 4 1 3
193 5 6 1 4
194 6 2 1 4
195 6 5 1 8
196 */

View Code