## 10330 - Power Transmission

Moderator: Board moderators

Jucovschi Constantin
New poster
Posts: 9
Joined: Sat Oct 26, 2002 6:30 pm

### 10330 - Power Transmission

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
New poster
Posts: 14
Joined: Sat Oct 26, 2002 5:59 am
Location: Sweden
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
New poster
Posts: 23
Joined: Sun Jun 22, 2003 11:24 pm
Location: Natal-Brazil
Contact:

### 10330 - WA

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
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden
The third last test case is wrong, correct output is 24.

sergio
New poster
Posts: 23
Joined: Sun Jun 22, 2003 11:24 pm
Location: Natal-Brazil
Contact:
Thank's. My output now is 24, but still WA
Can somebody give me some test cases or test my program??

bestyt
New poster
Posts: 3
Joined: Tue Nov 04, 2003 7:11 am

### 10330 - Power Transmission TLE Plz HELP

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
New poster
Posts: 3
Joined: Tue Nov 04, 2003 7:11 am
Can anyone give me some inputs with outputs? I still got TLE...

liulike
Learning poster
Posts: 52
Joined: Wed Jul 30, 2003 10:56 am
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
New poster
Posts: 2
Joined: Sun Apr 17, 2005 12:58 am

### 10330 WA

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
New poster
Posts: 2
Joined: Sun Apr 17, 2005 12:58 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
Learning poster
Posts: 78
Joined: Sat Feb 14, 2004 3:59 pm
Location: BUET
Contact:
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
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm

### 10330

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.
Jalal : AIUB SPARKS

dip
New poster
Posts: 7
Joined: Sat Nov 20, 2004 10:20 am
Location: Dhaka
Contact:

### Hi

Hi Jalal,
My accepted program gives -->

Code: Select all

``````10
34
7
30
``````
Good Luck for AIPC
something .....

CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm
ok thanks dip
Jalal : AIUB SPARKS

CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 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
Jalal : AIUB SPARKS