10330 - Power Transmission

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

Moderator: Board moderators

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

10330 - Power Transmission

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
New poster
Posts: 14
Joined: Sat Oct 26, 2002 5:59 am
Location: Sweden

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
New poster
Posts: 23
Joined: Sun Jun 22, 2003 11:24 pm
Location: Natal-Brazil
Contact:

10330 - WA

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
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

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

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:

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
New poster
Posts: 3
Joined: Tue Nov 04, 2003 7:11 am

10330 - Power Transmission TLE Plz HELP

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
New poster
Posts: 3
Joined: Tue Nov 04, 2003 7:11 am

Post by bestyt » Thu Nov 06, 2003 3:04 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

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
New poster
Posts: 2
Joined: Sun Apr 17, 2005 12:58 am

10330 WA

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
New poster
Posts: 2
Joined: Sun Apr 17, 2005 12:58 am

10330 Power Transmission Please help!

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

what's wrong in my code?
I really really don't know. :cry:
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:

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

User avatar
CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm
Location: AIUB, Bangladesh

10330

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

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

Hi

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

Hi Jalal,
My accepted program gives -->

Code: Select all

10
34
7
30
Good Luck for AIPC :D
something .....

User avatar
CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm
Location: AIUB, Bangladesh

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

ok thanks dip
Jalal : AIUB SPARKS

User avatar
CodeMaker
Experienced poster
Posts: 183
Joined: Thu Nov 11, 2004 12:35 pm
Location: AIUB, Bangladesh

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

Post Reply

Return to “Volume 103 (10300-10399)”