10983  Buy one, get the rest free
Moderator: Board moderators
10983  Buy one, get the rest free
please suppose some useful I/O
I've tried to generate some but no use
I've tried to generate some but no use
what's the time complexity of your algorithm ?
my one is of O(lgm * (m + x)), where x is the running time of EdmonsKarp 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 RelabelToFront O(V^3) or PreflowPush algorithm O(V^2 * E) ?
since V is near 330, i think it can be slow too....
please help me.
my one is of O(lgm * (m + x)), where x is the running time of EdmonsKarp 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 RelabelToFront O(V^3) or PreflowPush algorithm O(V^2 * E) ?
since V is near 330, i think it can be slow too....
please help me.
Sorry For My Poor English..
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 relabeltofront
without bsearch
WA I'm thinking about the accuracy of my algo
If you know the actually relabeltofront algo please send me a message about websit or code about the algo
since the number of edges is very big...
mine program is O(m*(n*d)^3)
using relabeltofront
without bsearch
WA I'm thinking about the accuracy of my algo
If you know the actually relabeltofront algo please send me a message about websit or code about the algo
 Abednego
 A great helper
 Posts: 281
 Joined: Tue Sep 10, 2002 5:14 am
 Location: Mountain View, CA, USA
 Contact:
There is no need to implement the complicated pushrelabel. 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 FordFulkerson, plus 1 extra line.
I have an implementation here:
http://shygypsy.com/tools
but please, don't just copypaste it to solve this problem. ;) Understand how it works.
I have an implementation here:
http://shygypsy.com/tools
but please, don't just copypaste it to solve this problem. ;) Understand how it works.
If only I had as much free time as I did in college...
It seems very nice !Abednego wrote:There is no need to implement the complicated pushrelabel. 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 FordFulkerson, plus 1 extra line.
I have an implementation here:
http://shygypsy.com/tools
but please, don't just copypaste it to solve this problem. Understand how it works.
my implementation of pushrelabel(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.
Sorry For My Poor English..
 Abednego
 A great helper
 Posts: 281
 Joined: Tue Sep 10, 2002 5:14 am
 Location: Mountain View, CA, USA
 Contact:
Sorry, you are correct.
The longest possible augmenting path has length n1, 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 pushrelabel. Look at this paper:
Basically, they show that the only way for pushrelabel 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 pushrelabel works faster than the O(mn^2) Dinic's.
Frank Chu implemented pushrelabel, 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.
The longest possible augmenting path has length n1, 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 pushrelabel. Look at this paper:
Code: Select all
Cherkassky and Goldberg, "On implementing pushrelabel method for the maximum flow problem," Technical report. Stanford, CA, USA, 1994.
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 pushrelabel works faster than the O(mn^2) Dinic's.
Frank Chu implemented pushrelabel, 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.
If only I had as much free time as I did in college...
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?
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?
That is not the interpretation I got from their paper, they don't even use any pushrelabel methods without heuristics in their comparisons. In fact, they go so far as to say:Abednego wrote:However, in practice, Dinic's algorithm beats pushrelabel. Look at this paper:Basically, they show that the only way for pushrelabel 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.Code: Select all
Cherkassky and Goldberg, "On implementing pushrelabel method for the maximum flow problem," Technical report. Stanford, CA, USA, 1994.
And though I believe this comment is a bit exaggerated and that their earlier comment that vanilla pushrelabel has poor practical performance is closer to the truth (though that is of course also relative, it sure beats vanilla fordfulkerson 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)Cherkassy and Goldberg wrote:The pushrelabel method is superior to Dinitz' method in practice, often by a wide margin when the global and gap relabeling heuristics are used.
I was not familiar with Dinitz' (Dinitz' googlewins Dinic's so I'm presuming this is correct) algorithm before. Thanks!
Re: 10983  Buy one, get the rest free.
I keep getting WAs too. Anybody can give some of the tricky cases?
Here's my code:
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;
}

 Guru
 Posts: 5947
 Joined: Thu Sep 01, 2011 9:09 am
 Location: San Jose, CA, USA
Re: 10983  Buy one, get the rest free.
Check input and AC output for thousands of problems on uDebug!
Re: 10983  Buy one, get the rest free.
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...
Or did I miss something from there? I'll go recheck...

 Guru
 Posts: 5947
 Joined: Thu Sep 01, 2011 9:09 am
 Location: San Jose, CA, USA
Re: 10983  Buy one, get the rest free.
Input:AC output:
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
Code: Select all
Case #1: 66633
Check input and AC output for thousands of problems on uDebug!