10330

Jucovschi Constantin · Post by **Jucovschi Constantin** » Sun Jan 12, 2003 7:29 pm

Hi,

This problems seems to be just a maximum flow problem but I cannot make it run in Time Limit. I tried 3 algorithms 1) Using breadth search 2) using depth search 3) preflux method. Still nothing .

How to do it in time limit ?

I make a graph of max 202 vertices. I double every regulator for being able to control the maximum flow through the regulator.

Maybe something is wrong with this ?

Thanks

Nak · Post by **Nak** » Sun Mar 16, 2003 4:33 am

I build the same graph as you and use Edmonds-Karp's algorithm. It only takes 0.273 seconds, perhaps you have an infinite loop or something?

sergio · Post by **sergio** » Wed Sep 03, 2003 2:14 am

Hi!

I am trying solve the problem 10330, but I only get Wrong Anser

So, I decide to request some help.
I have this input

4
10 20 30 40
6
1 2 5
1 3 10
1 4 13
2 3 5
2 4 7
3 4 20
3 1
1 2 3 4
2
50 100
1
1 2 100
1 1
1 2
8
100 100 100 100 100 100 100 100
12
1 2 5
1 3 7
1 4 6
2 5 4
2 6 3
3 6 4
3 7 1
4 7 5
5 8 3
6 8 7
7 6 4
7 8 6
1 1
1 8
6
100 100 100 100 100 100
10
1 2 4
1 3 3
2 3 2
2 4 2
2 5 2
3 4 4
3 5 3
4 6 6
5 4 5
5 6 10
1 1
1 6
6
100 100 100 100 100 100
10
1 2 3
1 4 4
2 3 4
2 4 5
2 5 1
3 6 2
4 3 1
4 5 2
5 3 3
5 6 6
1 1
1 6
7
100 100 100 100 100 100 100
13
1 2 10
1 3 20
1 4 10
2 1 30
2 5 20
3 5 15
3 6 20
4 6 20
5 2 30
5 7 15
6 4 30
6 7 30
7 6 10
1 1
1 7
100
100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100
100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100
100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100
100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100
100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100
2
1 50 30
23 33 30
2 2
34 33 50 1
9
100 100 100 100 100 100 100 100 100
18
1 2 15
1 3 10
2 1 10
2 4 12
2 5 10
3 6 9
4 5 15
5 4 8
5 6 12
5 7 9
5 8 10
6 3 5
6 8 15
7 4 7
7 9 10
8 6 1
8 9 18
9 6 8
1 1
1 9
8
100 100 100 100 100 100 100 100
12
1 2 5
1 3 7
1 4 6
2 5 4
2 6 3
3 6 4
3 7 1
4 7 5
5 8 3
6 8 7
7 8 6
7 6 4
1 1
1 8
4
100 100 100 100
4
1 2 5
1 3 2
2 4 2
3 4 5
1 1
1 4

And this is my output

37
50
15
7
5
40
0
19
15
4

Is it right??
If it is, somebody can give me another test cases??
Thank's

Per · Post by **Per** » Wed Sep 03, 2003 7:58 am

The third last test case is wrong, correct output is 24.

sergio · Post by **sergio** » Wed Sep 03, 2003 12:57 pm

Thank's. My output now is 24, but still WA

Can somebody give me some test cases or test my program??

bestyt · Post by **bestyt** » Tue Nov 04, 2003 1:01 pm

Could anybody tell me what's wrong with my code? I don't know why I got TLE. Is the only reason too slow searching time. Because my graph data structure is adjacency matrix.

In my code I used Edmonds-Karp algorithms to search maximum flow and used bellmans-ford to get augment path.

Help Me plz. Thanks in advance.

[cpp]
#include <iostream>
#include <cstdlib>
#include <memory>

#define MAX 10000000
#define SIZE 102

using namespace std;

int flow[SIZE][SIZE], cost[SIZE][SIZE];
int parent[SIZE], shortcost[SIZE], shortcost_save[SIZE];
int capacity[SIZE], minimum;
int V_Num;
int E_Num;

int bellmanFord(int s, int t) {
int i, j, avail_flow, exist_path;

// Initialize single source
memcpy(shortcost, shortcost_save, sizeof(int)*SIZE);
memset(parent, '\0', sizeof(int)*SIZE);
minimum = MAX;
exist_path = 0;

for (i = s+1; i < V_Num-1; i++) {
for(j = 1; j < V_Num-1; j++) {
if ((avail_flow=cost[j] - flow[j]) <= 0) {
continue;
}
// Relax operation
if (shortcost[j] > shortcost + avail_flow) {
shortcost[j] = shortcost + avail_flow;
parent[j]=i;

if (minimum > avail_flow) minimum = avail_flow;

if (cost[j][t] != 0) {
parent[t] = j;
exist_path = 1;
}
}
}
}

/* for (i = 0; i < E_Num; i++) {
avail_flow = cost[E.u][E.v]-flow[E.u][E.v];
if (avail_flow > 0 && shortcost[E.v] > shortcost[E.u] + avail_flow) {
return 0;
}
}
*/
if (exist_path) return 1;
else return 0;
}

void main(void)
{
int source, sink, i;
int x, y, cap;
int amp;

while (!cin.eof() && cin >> V_Num) {
// power station? capacity? input
for (i = 1; i <= V_Num; i++) {
cin >> capacity[i];
}
capacity[0] = MAX; capacity[V_Num+1] = MAX;
V_Num = V_Num+2;

// flow? input
cin >> E_Num;
memset(cost, '\0', sizeof(int)*SIZE*SIZE);
for (i = 0; i < E_Num; i++) {
cin >> x >> y >> cap;
if (cap > capacity[x]) cap = capacity[x];

cost[x][y] = cap;
}
cin >> source >> sink;
for (i = 0; i < source; i++) {
cin >> y;
cost[0][y] = MAX;
}
for (i = 0; i < sink; i++) {
cin >> x;
cost[x][V_Num-1] = MAX;
}

// Edmonds-Karp Algorithm
source = 0; sink = V_Num -1;
memset(flow,'\0',sizeof(int)*SIZE*SIZE);
shortcost_save[0] = 0;
for (i = 1; i < V_Num; i++) {
if (cost[source][i] != 0) {
shortcost_save[i] = 0;
} else {
shortcost_save[i] = MAX;
}
}
while (1) {
if (!bellmanFord(source, sink)) break;

y = sink; x = parent[sink];
while (x != 0) {
flow[x][y] = flow[x][y] + minimum;
flow[y][x] = -flow[x][y];
y = x;
x = parent[y];
}
}
amp = 0;
for (i = 0; i < V_Num-1; i++) {
if (flow[i][V_Num-1] > 0) {
amp += flow[i][V_Num-1];
}
}
cout << amp << endl;
}
}
[/cpp]

bestyt · Post by **bestyt** » Thu Nov 06, 2003 3:04 am

Can anyone give me some inputs with outputs? I still got TLE...

liulike · Post by **liulike** » Wed Dec 10, 2003 8:36 pm

try this input:
1
10
0
1 1
1 1

the output is:10

If you WA agian,send your code to me:liulike12@sina.com

center799 · Post by **center799** » Sun Apr 17, 2005 1:06 am

this is sample input i got someone(sergio..), and output...
i really don't know what's wrong...
i think it's correct, doesn't it??
is there another sample?
plz give me...

4
10 20 30 40
6
1 2 5
1 3 10
1 4 13
2 3 5
2 4 7
3 4 20
3 1
1 2 3 4
2
50 100
1
1 2 100
1 1
1 2
8
100 100 100 100 100 100 100 100
12
1 2 5
1 3 7
1 4 6
2 5 4
2 6 3
3 6 4
3 7 1
4 7 5
5 8 3
6 8 7
7 6 4
7 8 6
1 1
1 8
6
100 100 100 100 100 100
10
1 2 4
1 3 3
2 3 2
2 4 2
2 5 2
3 4 4
3 5 3
4 6 6
5 4 5
5 6 10
1 1
1 6
6
100 100 100 100 100 100
10
1 2 3
1 4 4
2 3 4
2 4 5
2 5 1
3 6 2
4 3 1
4 5 2
5 3 3
5 6 6
1 1
1 6
7
100 100 100 100 100 100 100
13
1 2 10
1 3 20
1 4 10
2 1 30
2 5 20
3 5 15
3 6 20
4 6 20
5 2 30
5 7 15
6 4 30
6 7 30
7 6 10
1 1
1 7
100
100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100
100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100
100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100
100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100
100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100
2
1 50 30
23 33 30
2 2
34 33 50 1
9
100 100 100 100 100 100 100 100 100
18
1 2 15
1 3 10
2 1 10
2 4 12
2 5 10
3 6 9
4 5 15
5 4 8
5 6 12
5 7 9
5 8 10
6 3 5
6 8 15
7 4 7
7 9 10
8 6 1
8 9 18
9 6 8
1 1
1 9
8
100 100 100 100 100 100 100 100
12
1 2 5
1 3 7
1 4 6
2 5 4
2 6 3
3 6 4
3 7 1
4 7 5
5 8 3
6 8 7
7 8 6
7 6 4
1 1
1 8
4
100 100 100 100
4
1 2 5
1 3 2
2 4 2
3 4 5
1 1
1 4
1
10
0
1 1
1 1

-------------
output :
37
50
15
7
5
40
0
24
15
4
10

center799 · Post by **center799** » Mon Apr 18, 2005 7:57 am

what's wrong in my code?
I really really don't know.

Output is below...

//@JUDGE_ID : 40030YA C++ - 10330 Power Transmission (Maximum Flow)
//@BEGIN_OF_SOURCE_CODE
#include<iostream>
#include<algorithm>
#include<cstdio>
using namespace std;
int N; // number of node
int excess[202]; // excess flow
int edge[202][202]; // residential edge
int vertex_capa[202]; // capacity of node
int height[202]; // height

void initialize()
{
int i;
memset(height, 0, sizeof(height));
memset(excess, 0, sizeof(excess));
height[0] = N+2;

for(i=1 ; i<=N+1 ; ++i){
if(edge[0]){
edge[0] = edge[0];
excess[0] -= edge[0];
excess = edge[0];
edge[0] = 0;
}
}
}

void push(int x, int y)
{
int flow;

flow = min(excess[x], edge[x][y]);
flow = min(flow, vertex_capa[y]-excess[y]);
excess[x] -= flow;
excess[y] += flow;
edge[x][y] -= flow;
edge[y][x] += flow;
}

void push_relabel()
{
int i, j, min;
bool is_loop=1;

while(is_loop){
is_loop=0;
for(i=1 ; i<N+1&&!is_loop ; ++i){ // find push-able vertex
if(excess>0){
for(j=0 ; j<N+2 ; ++j){
if(vertex_capa[j]-excess[j] && edge[j] && height==height[j]+1){
--i;
is_loop=1;
break;
}
}
}
}
if(is_loop){ // push
push(i, j);
}else{
for(i=1 ; i<N+1 ; ++i) // find relabel-able vertex
if(excess[i]>0){
for(min=1000000,j=0 ; j<N+2 ; ++j){
if(edge[i][j] && height[j]<min)
min=height[j];
}
if(height[i]!=min+1){
height[i]=min+1;
is_loop=1;
break;
}
}
if(!is_loop)
break;
}
}
}

int main()
{
int M, i, a, b, C, B, D, t;
while(cin >> N){
/* input */
memset(vertex_capa, 0, sizeof(vertex_capa));
for(i=1 ; i<=N ; ++i)
cin >> vertex_capa[i];
cin >> M;
memset(edge, 0, sizeof(edge));
for(i=0 ; i<M ; ++i){
cin >> a >> b >> C;
edge[a] = C;
}
cin >> B >> D;
for(i=0 ; i<B ; ++i){
cin >> t;
edge[0][t] = vertex_capa[t];
}
for(i=0 ; i<D ; ++i){
cin >> t;
if(vertex_capa[N+1]<vertex_capa[t])
vertex_capa[N+1]=vertex_capa[t];
edge[t][N+1] = vertex_capa[t];
}
/* algorithm */
initialize();
push_relabel();
/* output */
cout << excess[N+1] << endl;
}

return 0;
}
//@END_OF_SOURCE_CODE

Sanny · Post by **Sanny** » Fri Apr 22, 2005 11:57 am

I can't really fully understand what u did but the general idea on flow problems with vertex capacity is to split each vertex into two where all incoming edges come to one vertex and all outgoing edges goes from the other vertex and the capacity between them is the capacity of the original vertex. And also the capacity of the links between Barisal and those which are directly connected to it should be infinite and the same as for Dhaka. Hope it helps.

Regards
Sanny

CodeMaker · Post by **CodeMaker** » Fri Jul 15, 2005 3:20 pm

hi, i m getting wrong answer in this problem.For all the data sets available in the board, my solution gives correct output. so can anyone help me with some more data. i m trying to modify the "push-relabel" flow algorithm to solve it.

what will be the output for the following input?

Code: Select all

10
30 10 14 10 5 10 14 20 10 20
10
1 4 10
1 5 10
2 6 5
3 7 20
4 8 10
5 8 13
6 9 5
6 7 5
7 9 15
7 10 20
3 1
1 2 3 9
10
30 10 14 10 5 10 14 20 10 20
10
1 4 10
1 5 10
2 6 5
3 7 20
4 8 10
5 8 13
6 9 5
6 7 5
7 9 15
7 10 20
3 3
1 2 3 8 9 10
4
20 20 20 20
4
1 2 6
1 3 10
2 4 6
3 4 1
1 1
1 4
8
20 15 17 5 10 25 20 50
10
1 4 15
1 5 5
2 5 10
2 6 10
3 6 25
6 5 10
4 7 10
5 7 15
5 8 10
6 8 15
3 2
1 2 3 7 8

my solution gives:

19
34
7
40

is it ok? please give me some I/O that i can check my programme. thank you.

dip · Post by **dip** » Fri Jul 15, 2005 9:08 pm

Hi Jalal,
My accepted program gives -->

Code: Select all

Good Luck for AIPC

CodeMaker · Post by **CodeMaker** » Sat Jul 16, 2005 4:13 pm

ok thanks dip

CodeMaker · Post by **CodeMaker** » Tue Jul 19, 2005 3:00 pm

what will be the output of this case? i m still getting wa.

Code: Select all

15
15 17 13 15 25 30 15 20 10 10 40 10 30 13 15
20
5 8 15
5 15 10
1 5 15
1 11 7
13 7 10
13 9 20
13 1 20
10 1 10
10 12 9
10 4 5
15 10 10
15 4 5
12 11 20
2 3 14
11 9 20
11 2 15
8 13 10
8 1 10
4 14 7
14 11 15
2 4
5 4 7 6 9 3

my output
32

UVa OJ Board

10330 - Power Transmission

10330 - Power Transmission

10330 - WA

10330 - Power Transmission TLE Plz HELP

10330 WA

10330 Power Transmission Please help!

Hi