10594 - Data Flow

All about problems in Volume 105. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. » Sat Sep 11, 2004 4:59 am

My term "Successive Shortest Path" is the name of an algorithm that is for solving mincost flow, it will adjusted the edge cost after removing a shortest path, it is not simply the greedy method...... And my code can solve that case.
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Sat Sep 11, 2004 5:24 am

Well, I get same output for your test cases with my accepted program.
Do you also augment first in steps of k? Then be careful with the last amount of d%k; I made a wrong assumption first when I tried to solve the problem during the online contest.

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. » Sat Sep 11, 2004 5:43 am

Given the input graph, I will add a source vertex 0 with an edge (0, 1) has the capacity D and cost 0, so that should not be the problem.... Thanks
Do you have any special handling for large number? As the answer may be 10^15. I used long long to store any input, augmenting path and cost.
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. » Mon Sep 27, 2004 6:58 am

Oh. at last I found my bug.
As the given graph is undirected, I need to split each vertex into 2 new vertices, one for in-flow, one for out-flow. And there is an edge joining them with zero cost and capacity >= D, but at first I set the capacity to K :(
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per » Mon Sep 27, 2004 8:24 am

Hmm, do you really need to split the vertices? My solution doesn't, but perhaps we use different algorithms.

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. » Mon Sep 27, 2004 8:34 am

I get the pseudo code of "Successive Shortest Path Algorithm" from a paper,
it has an assumption that if arc(i, j) in the graph G, arc(j, i) doesn't not.
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per » Mon Sep 27, 2004 8:42 am

Ah OK, then I see why you need it. I just used Ford-Fulkerson, but augment paths using Bellman-Ford instead of DFS/BFS (not sure what Successive Shortest Path Algorithm is, but it sounds like something similar). It wasn't fast, but it worked. :)

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. » Mon Sep 27, 2004 8:57 am

The "Successive shortest" works in this way:
It keeps solving shortest path for source to sink and augment it. As the residual network may have negative cycle, the algorithm will use some label on vertex to modify the edge cost so that all the edge has cost >= 0.

It sounds that your algorithm is like the "negative cycle removing algorithm".
This algorithm needs detect to any negative cycle in the graph and augment along it. I tried to implement it, but it is too slow to detect a negative cycle...

I searched many website, papers and books for this problem.
I think the following book is an excelllent reference:
http://www.amazon.com/exec/obidos/tg/de ... s&n=507846
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per » Mon Sep 27, 2004 9:17 am

It is true that I can get edges with negative cost, but if the initial costs are nonnegative, I will never get negative cycles (unless I have a bug in my program :)).

It sounds like the algorithms are quite similar: augment along a shortest path. The difference seems to be that your algorithm has some special trick for handling the negative costs, whereas mine simply uses a standard negative-cost-handling algorithm for that (which, understandably, is slower). Did I understand correctly?

Yeah, I've been interested in that book for a while, but alas, so much to do and so little time. :(

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. » Mon Sep 27, 2004 4:31 pm

Per wrote: It sounds like the algorithms are quite similar: augment along a shortest path. The difference seems to be that your algorithm has some special trick for handling the negative costs, whereas mine simply uses a standard negative-cost-handling algorithm for that (which, understandably, is slower). Did I understand correctly?
Yes :D
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

InOutMoTo
New poster
Posts: 18
Joined: Sun Aug 10, 2003 12:47 pm

Post by InOutMoTo » Tue Nov 02, 2004 10:11 am

[quote="Per"]Ah OK, then I see why you need it. I just used Ford-Fulkerson, but augment paths using Bellman-Ford instead of DFS/BFS (not sure what Successive Shortest Path Algorithm is, but it sounds like something similar). It wasn't fast, but it worked. :)[/quote]

I also use Ford-Fulkerson implemented with Bellman-Ford method.
However, I got TLE.

Since there won't be negative egdes,
I turn Bellman-Ford into Dijkstra method.

This time I got WA.
Can someone help :o

ps: I pass the test case in previous page.

wook
Learning poster
Posts: 76
Joined: Fri Oct 01, 2004 11:34 am
Location: Korea, Republic Of

10594 Data Flow - My algorithm is too slow

Post by wook » Wed Mar 09, 2005 12:52 pm

Hello.

Please Help Me :(



The minimum cost flow problem (10594 - Data Flow)

I wrote the code by getting augumenting path, using Bellman-Ford,

but I know it's too slow (Sure, TLE on Judge)

where can i get some informations about minimum cost flow?

or.. please tell me how i can reduce the time.



my algorithm makes correct answer for many inputs,

and i think it would be AC if there isn't time Limit!


How can i do it?
Sorry For My Poor English.. :)

windows2k
Experienced poster
Posts: 136
Joined: Sat Apr 05, 2003 3:29 pm
Location: Taiwan

Post by windows2k » Sun Jun 19, 2005 10:31 am

Sorry,I have one question.
I know how to solve with directed graph.
I don't know how to do with undirected graph.
I found an article from google
http://answers.google.com/answers/threadview?id=496389
I don't know what is the meaning?

Code: Select all

It is probably worth noting that the reduction can already be made at
the "outer" level of the graph formulation itself at a cost of
introducing one additional node per edge.

That is, for each undirected edge E of the original graph, we create a
synthetic node C(E) through with all flow in one direction
("backflow") is redirected:
To make this work the original "backflow" capacity of is assigned to
both new edges, and the per unit cost for this can be split
arbitrarily between the two edges.
I got confused :o
Hope someone give some descriptions, thx :D

User avatar
hank
Experienced poster
Posts: 146
Joined: Mon Feb 04, 2002 2:00 am
Location: VCORE.

Post by hank » Wed Oct 19, 2005 11:57 am

.. wrote:My term "Successive Shortest Path" is the name of an algorithm that is for solving mincost flow, it will adjusted the edge cost after removing a shortest path, it is not simply the greedy method...... And my code can solve that case.
Hi

Did you use Bellman-Ford algorithm in this problem ?
However,I use Bellman-Ford algo to find the argumenting paths
but still got TLE!!

Is there any good algorithm for finding argumenting paths ?

Thanks!

kane116
New poster
Posts: 8
Joined: Sun Aug 07, 2005 5:35 am

10594 WA

Post by kane116 » Wed Jan 18, 2006 12:11 pm

Would someone give me some test case?
I think my algo is correct, I solve it as Min Cost Max Flow problem.
Here is the idea:
- The time is the cost of flowing on that edge.
- Capicity of the edge is set to K.
- While there exist an shortest augmenting path
(Use Dijkstra to find the shorest augmenting path)
* Update the flow of edge on the path
* Add the cost of flowing on this path to the total
It is basically a Ford-Fulkerson method, and use Dijkstra to find the augmenting path.

Here is the code.

Code: Select all

#include <cstdio>
#include <string>
#include <climits>
#define min(A, B) (A < B ? A : B)
#define ARR 200

long long int n, D, K;
long long int weg[ARR][ARR], cap[ARR][ARR], flw[ARR][ARR];
long long int cost;

bool dijk(long long int s, long long int t) {
        long long int dis[ARR], pre[ARR], vis[ARR];
        memset(dis, 0, sizeof(dis));
        memset(pre, 0, sizeof(pre));
        memset(vis, 0, sizeof(vis));
        for (long long int i = 0; i < n; i++) {
                dis[i] = INT_MAX;
                pre[i] = -1;
                vis[i] = false;
        }
        dis[s] = 0;
        for (long long int i = 0; i < n; i++) {
                long long int mn = INT_MAX, u = -1;
                for (long long int j = 0; j < n; j++)
                        if (! vis[j] && dis[j] < mn) {
                                mn = dis[j];
                                u = j;
                        }
                if (u != -1) {
                        vis[u] = true;
                        for (long long int v = 0; v < n; v++)
                                if (weg[u][v] && dis[v] > dis[u] + weg[u][v] && cap[u][v] - flw[u][v]) {
                                        dis[v] = dis[u] + weg[u][v];
                                        pre[v] = u;
                                }
                }
        }
        if (pre[t] == -1)       return false;
        long long int flow = INT_MAX;
        for (long long int u = t; u != s; u = pre[u])
                flow = min(flow, cap[pre[u]][u] - flw[pre[u]][u]);
        for (long long int u = t; u != s; u = pre[u]) {
                flw[pre[u]][u] += flow;
                flw[u][pre[u]] -= flow;
        }
        cost += dis[t] * min(D, flow);
        D -= min(D, flow);
        return true;
}

int main() {
        long long int t;
        while (scanf("%lld%lld", &n, &t) != EOF) {
                memset(weg, 0, sizeof(weg));
                memset(cap, 0, sizeof(cap));
                memset(flw, 0, sizeof(flw));
                for (long long int i = 0; i < t; i++) {
                        long long int a, b, c;
                        scanf("%lld%lld%lld", &a, &b, &c);      a--;    b--;
                        cap[a][b] = cap[b][a] = 1;
                        weg[a][b] = weg[b][a] = c;
                }
                scanf("%lld%lld", &D, &K);
                for (long long int i = 0; i < n; i++)
                        for (long long int j = 0; j < n; j++)
                                if (cap[i][j])  cap[i][j] = K;
                cost = 0;
                while (D && dijk(0, n - 1));
                if (! D)        printf("%lld\n", cost);
                else printf("Impossible.\n");
        }
        return 0;
}

Post Reply

Return to “Volume 105 (10500-10599)”