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
/**//*************************************************************************2
Author: WHU_GCC3
Created Time: 2007-9-17 17:52:254
File Name: hit2543.cpp5
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 _adj17
{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
]]>