1  /**//*************************************************************************
2 Author: WHU_GCC
3Created Time: 2007-9-17 17:52:25
4File Name: hit2543.cpp
5Description:
6 ************************************************************************/
7 #include <iostream>
8using namespace std;
9#define out(x) (cout<<#x<<": "<<x<<endl)
10const int maxint=0xFFFFFFF;
11typedef long long int64;
12const int64 maxint64 = 0xFFFFFFFFFFFFFFFLL;
13template<class T>void show(T a, int n) {for(int i=0; i<n; ++i) cout<<a[i]<<' '; cout<<endl;}
14template<class T>void show(T a, int r, int l){for(int i=0; i<r; ++i)show(a[i],l);cout<<endl;}
15const int maxn = 1100;
16struct _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];
37int stt, trm, n, c, p;
38int d[maxn];
39int cost;
40int 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
81void 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}
93int 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
116int work ()
117{
118 return mincostmaxflow ();
119}
120
121void 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
141int 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
|
|
| | 日 | 一 | 二 | 三 | 四 | 五 | 六 |
|---|
| 30 | 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 | 29 | 30 | 31 | 1 | 2 | 3 | | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|
常用鏈接
留言簿(1)
隨筆檔案
文章檔案
搜索
最新評論
閱讀排行榜
評論排行榜
|
|