10594 - Data Flow

[..]

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.

[Adrian Kuegel]

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.

[..]

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.

[..]

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

[Per]

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

[..]

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.

[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.

[..]

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

[Per]

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.

[..]

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

[InOutMoTo]

[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

ps: I pass the test case in previous page.

[wook]

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?

[windows2k]

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
Hope someone give some descriptions, thx

[hank]

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]

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;
}