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

WHUGCC — Mon, 17 Sep 2007 13:00:00 GMT

  1/*************************************************************************
  2Author: 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<<": "<
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

WHUGCC 2007-09-17 21:00 发表评论

C++博客-WHUGCC-最新评论

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