1 /**//************************************************************************* 2 Author: WHU_GCC 3 Created Time: 2007-9-17 17:52:25 4 File Name: hit2543.cpp 5 Description: 6 ************************************************************************/ 7 #include <iostream> 8 using namespace std; 9 #define out(x) (cout<<#x<<": "<<x<<endl) 10 const int maxint=0xFFFFFFF; 11 typedef long long int64; 12 const int64 maxint64 = 0xFFFFFFFFFFFFFFFLL; 13 template<class T>void show(T a, int n) {for(int i=0; i<n; ++i) cout<<a[i]<<' '; cout<<endl;} 14 template<class T>void show(T a, int r, int l) {for(int i=0; i<r; ++i)show(a[i],l);cout<<endl;} 15 const int maxn = 1100; 16 struct _adj 17  { 18 int v, c, f, w; 19 _adj *next, *dup; 20 int getw() 21 { 22 if (f < -c) 23 return -w; 24 if (f < c) 25 return 0; 26 return w; 27 } 28 int getc() 29 { 30 if (f < -c) 31 return -c - f; 32 if (f < c) 33 return c - f; 34 return maxint; 35 } 36 } *adj[maxn], *st[maxn]; 37 int stt, trm, n, c, p; 38 int d[maxn]; 39 int cost; 40 int bell() 41  { 42 int bfs[maxn]; 43 bool hash[maxn]; 44 fill (hash + 1, hash + 1 + n, 0); 45 fill (d + 1, d + 1 + n, maxint); 46 _adj*pt; 47 hash[stt] = 1; 48 d[stt] = 0; 49 bfs[0] = stt; 50 int v; 51 for (int s = 0, t = 1; s != t;s = (s + 1) % n, hash[v] = 0) 52 for (pt = adj[v = bfs[s]]; pt; pt = pt->next) 53 if (d[v] + pt->getw() < d[pt->v]) 54 { 55 // out(pt->getw()); 56 // out(v); 57 // out(pt->v); 58 d[pt->v] = d[v] + pt->getw(); 59 // out(d[pt->v]); 60 st[pt->v] = pt; 61 if (hash[pt->v] == 0) 62 { 63 hash[pt->v] = 1; 64 bfs[t++] = pt->v; 65 t %= n; 66 } 67 // system ("pause"); 68 } 69 // out(1); 70 if (d[trm] == maxint) 71 return 0; 72 int ans = maxint; 73 for (v = trm; v != stt; v = st[v]->dup->v) 74 { 75 ans <?= st[v]->getc(); 76 } 77 // out(ans); 78 return ans; 79 } 80 81 void insert(int u, int v, int c, int w) 82  { 83 // printf ("%d %d %d %d\n", u, v, c, w); 84 _adj* pt; 85 pt = new _adj; 86 pt->v = v; pt->c = c; pt->f = 0; pt->w = w; pt->next = adj[u]; 87 adj[u] = pt; 88 pt->dup = new _adj; 89 _adj *qt = pt->dup; 90 qt->v = u; qt->c = c; qt->f = 0; qt->w = w; qt->next = adj[v]; qt->dup = pt; 91 adj[v] = qt; 92 } 93 int mincostmaxflow () 94  { 95 int flow = 0; 96 cost = 0; 97 int f; 98 while ((f = bell())) 99 { 100 // out(f); 101 if (f == maxint || f * (p + d[trm]) >= c) 102 { 103 return flow + c / (p + ::d[trm]); 104 } 105 flow += f; 106 c -= f * p + ::d[trm] * f; 107 for (int x = trm; x != stt; x = st[x]->dup->v) 108 { 109 st[x]->f += f; 110 st[x]->dup->f -= f; 111 } 112 } 113 return flow; 114 } 115 116 int work () 117  { 118 return mincostmaxflow (); 119 } 120 121 void init () 122  { 123 int n, m, c, p; 124 scanf ("%d %d %d %d", &n, &m, &c, &p); 125 memset (adj, 0, sizeof (adj)); 126 while (m--) 127 { 128 int u, v, cc, w; 129 scanf ("%d %d %d %d", &u, &v, &cc, &w); 130 ++u; 131 ++v; 132 insert (u, v, cc, w); 133 } 134 ::n = n; 135 ::c = c; 136 ::p = p; 137 stt = 1; 138 trm = 2; 139 } 140 141 int main() 142  { 143 int T; 144 scanf ("%d", &T); 145 while (T--) 146 { 147 init (); 148 printf ("%d\n", work ()); 149 } 150 return 0; 151 } 152 153
|
|
| 日 | 一 | 二 | 三 | 四 | 五 | 六 |
---|
26 | 27 | 28 | 29 | 30 | 31 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|
常用链接
留言簿(1)
随笔档案
文章档案
搜索
最新评论

阅读排行榜
评论排行榜
|
|