10983 - Buy one, get the rest free

[polone]

please suppose some useful I/O

I've tried to generate some but no use

[FAQ]

I really need some I/O too
Crazy with WAs...

[wook]

what's the time complexity of your algorithm ?

my one is of O(lgm * (m + x)), where x is the running time of Edmons-Karp Algorithm.
That is to say, I runned a maxflow algorithm O(lgm) times.

I got TLE.
should I use more fast maxflow algorithm, like a Relabel-To-Front O(V^3) or Preflow-Push algorithm O(V^2 * E) ?
since V is near 330, i think it can be slow too....

please help me.

[polone]

yes I agree that you shoule implent O(v^3) algo

since the number of edges is very big...

mine program is O(m*(n*d)^3)

using relabel-to-front

without bsearch

WA I'm thinking about the accuracy of my algo

If you know the actually relabel-to-front algo please send me a message about websit or code about the algo

[Abednego]

There is no need to implement the complicated push-relabel. There is another algorithm that is also O(n^3), but is much, much, MUCH simpler to code. It's called Dinic's algorithm, and consists of Ford-Fulkerson, plus 1 extra line.

I have an implementation here:
http://shygypsy.com/tools
but please, don't just copy-paste it to solve this problem. ;-) Understand how it works.

[wook]

There is no need to implement the complicated push-relabel. There is another algorithm that is also O(n^3), but is much, much, MUCH simpler to code. It's called Dinic's algorithm, and consists of Ford-Fulkerson, plus 1 extra line.

I have an implementation here:
http://shygypsy.com/tools
but please, don't just copy-paste it to solve this problem. Understand how it works.

It seems very nice !

my implementation of push-relabel(or, relabel to front method) is very very very long and complicated !!
Your source code looks very fascinating, but I can't understand why it works in O(n^3) time.

As I searched some related informations in google,
some results say that the Dinic's Algorithm is of O(mn^2) time complexity, and that it's can be made in O(nm lgn) using another special data structures.

can you explain more detail for me, please?

Thanks.

[Abednego]

Sorry, you are correct.

The longest possible augmenting path has length n-1, where n is the number of vertices. Dinic's algorithm proceeds as follows:
1. BFS from S until we reach T at depth D (depth is measured in the number of edges).
2. If we cannot reach T, return.
3. Find a maximal set of augmenting paths of length D.
4. Goto step 1.
The total running time is O(mn^2).

However, in practice, Dinic's algorithm beats push-relabel. Look at this paper:

Code: Select all

Cherkassky and Goldberg, "On implementing push-relabel method for the maximum flow problem," Technical report. Stanford, CA, USA, 1994.

Basically, they show that the only way for push-relabel to beat Dinic's algorithm is when they use "gap relabelling" or "global relabelling", which are two heuristics, and even in that case, it wins by a small margin even on huge graphs with n=100000.

For any problem that you might see in an ACM competition, there is almost no chance that you will find a test case on which push-relabel works faster than the O(mn^2) Dinic's.

Frank Chu implemented push-relabel, and it took him a long time to get the heuristics working before his code ran as fast as mine on a dense graph of 2000 vertices. At that point, reading the input was taking more time than finding the maximum flow.

[hoho]

The input description included:
Day 0 is today, and all of the participants need to be in city n in the evening of day e.

What does it mean??

I think the e should be d.

I wrote my program as it is d but always got WA.
Who could give me more input/output?? Thanks.

What is the output when only one city??
I think the output should be 0. Am I right?

[Abednego]

You are right. It should say
Day 0 is today, and all of the participants need to be in city n in the evening of day d.

When there is only one city, the answer is 0.

[FAQ]

Wow, your tools are really cool !!

I have checked my program with some special tests

1 1 0
100
output : 0

5 5 0
0 0 0 0 100
output : 0 (all passengers are already in the destination)
... But I still WA :'( ( the time running is ok )

[Per]

However, in practice, Dinic's algorithm beats push-relabel. Look at this paper:

Code: Select all

Cherkassky and Goldberg, "On implementing push-relabel method for the maximum flow problem," Technical report. Stanford, CA, USA, 1994.

Basically, they show that the only way for push-relabel to beat Dinic's algorithm is when they use "gap relabelling" or "global relabelling", which are two heuristics, and even in that case, it wins by a small margin even on huge graphs with n=100000.

That is not the interpretation I got from their paper, they don't even use any push-relabel methods without heuristics in their comparisons. In fact, they go so far as to say:

The push-relabel method is superior to Dinitz' method in practice, often by a wide margin when the global and gap relabeling heuristics are used.

And though I believe this comment is a bit exaggerated and that their earlier comment that vanilla push-relabel has poor practical performance is closer to the truth (though that is of course also relative, it sure beats vanilla ford-fulkerson most of the time), I cannot agree with your interpretation of their paper above. (Though I only browsed through the paper quickly and have not read it thoroughly - sorry if I misread something)

I was not familiar with Dinitz' (Dinitz' google-wins Dinic's so I'm presuming this is correct) algorithm before. Thanks!

[ackoroa]

I keep getting WAs too. Anybody can give some of the tricky cases?

Here's my code:

Code: Select all

#include <cstdio>
#include <vector>
#include <utility>
#include <bitset>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;
 
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;
 
#define INF 1e9
#define MAX_V 330
 
struct vertice {
        int city;
        int day;
        vertice() {
        }
        vertice(int c, int d) {
                this->city = c, this->day = d;
        }
        bool operator ==(vertice v) const {
                return city == v.city && day == v.day;
        }
        int idx() {
                return city * 10 + day;
        }
};
typedef vector<vertice> vv;
 
int res[MAX_V][MAX_V], mf, f;
vertice s, t;
vector<vv> AdjList;
vi p;
 
int n, d, m, C;
#define NFLIGHT 1010
int uf[NFLIGHT], vf[NFLIGHT], cf[NFLIGHT], pf[NFLIGHT], ef[NFLIGHT],
                sortedPF[NFLIGHT];
int pop[35];
 
void augment(int v, int minEdge) {
        if (v == s.idx()) {
                f = minEdge;
                return;
        } else if (p[v] != -1) {
                augment(p[v], min(minEdge, res[p[v]][v]));
                res[p[v]][v] -= f;
                res[v][p[v]] += f;
        }
}
 
void EdmondKarps() {
        mf = 0;
        while (1) {
                f = 0;
                bitset<MAX_V> visited;
                visited.set(s.idx());
                queue<vertice> q;
                q.push(s);
                p.assign(MAX_V, -1);
                while (!q.empty()) {
                        vertice u = q.front();
                        q.pop();
                        if (u == t)
                                break;
                        for (int i = 0; i < (int) AdjList[u.idx()].size(); i++) {
                                vertice v = AdjList[u.idx()][i];
                                if (res[u.idx()][v.idx()] > 0 && !visited.test(v.idx())) {
                                        visited.set(v.idx());
                                        q.push(v);
                                        p[v.idx()] = u.idx();
                                }
                        }
                }
                augment(t.idx(), INF);
                if (f == 0)
                        break;
                mf += f;
        }
}
 
void initGraph() {
        memset(res, 0, sizeof res);
        AdjList.assign(MAX_V, vv());
        s = vertice(0, 0);
        t = vertice(n, d);
 
        for (int i = 1; i <= n; i++) {
                vertice v(i, 0);
                res[s.idx()][v.idx()] = pop[i];
                AdjList[s.idx()].push_back(v);
                AdjList[v.idx()].push_back(s);
        }
 
        for (int i = 1; i <= n; i++) {
                for (int j = 0; j < d - 1; j++) {
                        vertice v1(i, j), v2(i, j + 1);
                        res[v1.idx()][v2.idx()] = INF;
                        AdjList[v1.idx()].push_back(v2);
                        AdjList[v2.idx()].push_back(v1);
                }
                if (i == n) {
                        vertice v1(i, d - 1);
                        res[v1.idx()][t.idx()] = INF;
                        AdjList[v1.idx()].push_back(t);
                        AdjList[t.idx()].push_back(v1);
                }
        }
 
        for (int i = 0; i < m; i++) {
                if (pf[i] <= C) {
                        vertice v1(uf[i], ef[i]), v2(vf[i], ef[i] + 1);
                        res[v1.idx()][v2.idx()] = cf[i];
                        AdjList[v1.idx()].push_back(v2);
                        AdjList[v2.idx()].push_back(v1);
                }
        }
/*
        printf("%d\n", C);
        for (int i = 0; i <= 10 * n + d; i++) {
                printf("vertice %d:", i);
                for (int j = 0; j < AdjList[i].size(); j++) {
                        printf(" (%d,%d)", AdjList[i][j].city, AdjList[i][j].day);
                }
                printf("\n");
        }
*/
}
 
int main() {
        int tc, cnt = 1;
        int lo, hi, mid, sumPpl, pplOut;
 
        scanf("%d", &tc);
        while (tc--) {
                scanf("%d %d %d", &n, &d, &m);
 
                hi = -1;
                for (int i = 0; i < m; i++) {
                        scanf("%d %d %d %d %d", &uf[i], &vf[i], &cf[i], &pf[i], &ef[i]);
                        sortedPF[i] = pf[i];
                }
                sort(sortedPF, sortedPF + m);
 
                sumPpl = 0;
                for (int i = 1; i <= n; i++) {
                        scanf("%d", &pop[i]);
                        sumPpl += pop[i];
                }
                pplOut = sumPpl - pop[n];
 
                int lo;
                for (lo = 0; lo < m; lo++) {
                        C = sortedPF[lo];
                        initGraph();
                        EdmondKarps();
                        if (mf >= sumPpl)
                                break;
                }
 
                printf("Case #%d: ", cnt++);
                if (pplOut == 0)
                        printf("0\n");
                else if (lo < m)
                        printf("%d\n", sortedPF[lo]);
                else
                        printf("Impossible\n");
        }
 
        return 0;
}

[brianfry713]

http://www.algorithmist.com/index.php/UVa_10983

[ackoroa]

Yeah, I've been following that and can solve the sample inputs there correctly :S (I do remove the debug printouts before I submit)

Or did I miss something from there? I'll go recheck...

[brianfry713]

Input:

Code: Select all

1
6 8 84
3 3 18 1158 0
3 6 13 39909 1
6 3 57 62653 1
2 3 28 3031 5
2 4 53 42589 0
6 5 36 55625 2
5 5 44 47028 3
1 4 73 19487 0
2 2 34 92291 0
5 4 61 28358 6
4 4 72 73803 3
6 6 98 69351 5
6 5 88 85837 3
5 2 92 18791 7
6 6 10 83256 4
3 5 2 50509 3
2 6 92 89175 0
5 6 56 66806 4
4 3 32 89645 0
2 5 66 78507 4
4 6 82 29358 2
6 6 8 88585 6
4 1 16 44024 6
4 5 76 4677 7
6 2 96 71995 6
1 2 87 63422 4
2 1 31 25696 7
1 3 17 85144 3
5 5 86 5906 2
2 3 49 11017 1
5 6 55 76899 1
6 5 66 66682 7
2 4 74 17277 3
3 3 24 62432 7
6 6 52 78018 1
4 6 80 66633 5
1 1 43 76724 2
4 5 32 28509 4
5 3 19 67224 1
1 2 33 5071 1
5 4 89 37674 7
4 6 92 29161 1
5 2 36 77719 1
2 5 21 40450 7
3 6 75 79575 3
3 4 57 93855 2
4 2 5 52294 5
1 2 78 63953 7
3 2 22 74433 3
4 6 84 83667 0
6 3 87 50344 5
3 1 13 72065 3
6 4 89 25631 7
3 1 6 85056 1
5 4 45 46825 3
6 3 53 86049 7
3 2 85 79112 2
1 4 98 15381 4
5 4 92 91140 1
6 3 68 77503 4
2 6 12 76781 2
3 1 21 14282 5
1 1 53 4761 1
4 5 46 52629 6
3 5 8 8467 1
4 4 65 26176 5
2 2 29 13653 3
2 2 24 27172 1
5 1 71 33000 0
4 3 21 50052 3
4 4 24 7057 0
4 6 32 79462 3
6 3 11 94877 6
6 2 11 59657 1
5 6 71 86334 2
1 4 93 49026 7
6 2 65 40501 7
2 2 24 38461 7
1 5 76 17734 2
3 5 32 72214 4
3 6 61 92481 5
1 6 39 29012 4
1 1 78 59528 3
3 4 24 46553 1
3 31 9 100 49 87

AC output:

Code: Select all

Case #1: 66633