http://acm.hit.edu.cn/ojs/show.php?Proid=2543&Contestid=0

# re: http://acm.hit.edu.cn/ojs/show.php?Proid=2543&Contestid=0

/*************************************************************************
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

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

WHUGCC 评论于 2007-09-17 21:00 回复更多评论

常用链接

留言簿(1)

随笔档案

文章档案

搜索

最新评论

阅读排行榜

评论排行榜

WHUGCC
C++博客 \| 首页 \| 发新随笔 \| 发新文章 \| 联系 \| 聚合 \| 管理	随笔：3 文章：1 评论：1 引用：0