uva 11865（二分+最小树形图）

  1 /**************************************************
  2  * Author     : xiaohao Z
  3  * Blog     : http://www.cnblogs.com/shu-xiaohao/
  4  * Last modified : 2014-02-07 13:53
  5  * Filename     : uva_11865.cpp
  6  * Description     : 
  7  * ************************************************/
  8 
  9 #include <iostream>
 10 #include <cstdio>
 11 #include <cstring>
 12 #include <cstdlib>
 13 #include <cmath>
 14 #include <algorithm>
 15 #include <queue>
 16 #include <stack>
 17 #include <vector>
 18 #include <set>
 19 #include <map>
 20 #define MP(a, b) make_pair(a, b)
 21 #define PB(a) push_back(a)
 22 
 23 using namespace std;
 24 typedef long long ll;
 25 typedef pair<int, int> pii;
 26 typedef pair<unsigned int,unsigned int> puu;
 27 typedef pair<int, double> pid;
 28 typedef pair<ll, int> pli;
 29 typedef pair<int, ll> pil;
 30 
 31 const int INF = 0x3f3f3f3f;
 32 const ll LINF = 0x3f3f3f3f3f3f3f3fLL;
 33 const double eps = 1E-6;
 34 const int LEN = 201;
 35 int pre[LEN], id[LEN], vis[LEN];
 36 ll in[LEN];
 37 struct E{ int fr, to, bmp;ll val;};
 38 E te[LEN*LEN];
 39 
 40 ll zhuliu(int root, int n, int m, E edge[]){
 41     ll ret = 0;
 42        int    u, v;
 43     while(1){
 44         for(int i=0; i<n; i++) in[i] = LINF;
 45         for(int i=0; i<m; i++)
 46             if(edge[i].fr != edge[i].to && edge[i].val < in[edge[i].to]){
 47                 pre[edge[i].to] = edge[i].fr;
 48                 in[edge[i].to] = edge[i].val;
 49             }
 50         for(int i=0; i<n; i++)
 51             if(i != root && in[i] == LINF) return LINF;
 52         int tn = 0;
 53         memset(id, -1, sizeof id);
 54         memset(vis, -1, sizeof vis);
 55         in[root] = 0;
 56         for(int i=0; i<n; i++){
 57             ret += in[i];
 58             v = i;
 59             while(vis[v] != i && id[v] == -1 && v != root){
 60                 vis[v] = i;
 61                 v = pre[v];
 62             }
 63             if(v != root && id[v] == -1){
 64                 for(int u=pre[v]; u!=v; u=pre[u])id[u] = tn;
 65                 id[v] = tn++;
 66             }
 67         }
 68         if(tn == 0) break;
 69         for(int i=0; i<n; i++) if(id[i] == -1)id[i] = tn++;
 70         for(int i=0; i<m; ){
 71             v = edge[i].to;
 72             edge[i].fr = id[edge[i].fr];
 73             edge[i].to = id[edge[i].to];
 74             if(edge[i].fr != edge[i].to) edge[i++].val -= in[v];
 75             else swap(edge[i], edge[--m]);
 76         }
 77         n = tn;
 78         root = id[root];
 79     }
 80     return ret;
 81 }
 82 
 83 int Makedge(int tbad, E edge[], int m){
 84     int top = 0;
 85     for(int i=0; i<m; i++)
 86        if(te[i].bmp >= tbad){
 87               edge[top].fr = te[i].fr;
 88            edge[top].to = te[i].to;
 89            edge[top++].val = te[i].val;
 90            }
 91     return top;
 92 }
 93 
 94 int main()
 95 {
 96 //    freopen("in.txt", "r", stdin);
 97     
 98     int T, n, m, cost;
 99     E edge[LEN*LEN];
100     scanf("%d", &T);
101     while(T--){
102         int l = INF, r = 0;
103         scanf("%d%d%d", &n, &m, &cost);
104         for(int i=0; i<m; i++){
105             scanf("%d%d%d%lld", &te[i].fr, &te[i].to, &te[i].bmp, &te[i].val);
106             l = min(l, te[i].bmp);
107             r = max(r, te[i].bmp);
108         }
109         Makedge(0, edge, m);
110         if(zhuliu(0, n, m, edge) > cost) printf("streaming not possible.\n");
111         else {
112             while(l < r){
113                 int mid = (l+r+1)/2, tm = Makedge(mid, edge, m);
114                 ll tans = zhuliu(0, n, tm, edge);
115                 if(tans <= cost) l = mid;
116                 else r = mid-1;
117             }
118             printf("%d kbps\n", l);
119         }
120     }
121     return 0;
122 }