10594 - Data Flow
Moderator: Board moderators
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.
-
- Guru
- Posts: 724
- Joined: Wed Dec 19, 2001 2:00 am
- Location: Germany
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.
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.
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![:(](./images/smilies/icon_frown.gif)
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
![:(](./images/smilies/icon_frown.gif)
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.
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.
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.
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
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.
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.![:(](./images/smilies/icon_frown.gif)
![:)](./images/smilies/icon_smile.gif)
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.
![:(](./images/smilies/icon_frown.gif)
YesPer 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?
![:D](./images/smilies/icon_biggrin.gif)
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.
[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.
![:)](./images/smilies/icon_smile.gif)
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](./images/smilies/icon_eek.gif)
ps: I pass the test case in previous page.
10594 Data Flow - My algorithm is too slow
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?
Please Help Me
![:(](./images/smilies/icon_frown.gif)
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.. ![:)](./images/smilies/icon_smile.gif)
![:)](./images/smilies/icon_smile.gif)
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?
I got confused
Hope someone give some descriptions, thx![:D](./images/smilies/icon_biggrin.gif)
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.
![:o](./images/smilies/icon_eek.gif)
Hope someone give some descriptions, thx
![:D](./images/smilies/icon_biggrin.gif)
Hi.. 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.
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!
10594 WA
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.
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;
}