10330 - Power Transmission

[Jucovschi Constantin]

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]

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]

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]

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

[sergio]

Thank's. My output now is 24, but still WA
Can somebody give me some test cases or test my program??

[bestyt]

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]

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

[liulike]

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]

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]

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]

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]

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]

Hi Jalal,
My accepted program gives -->

Code: Select all

10
34
7
30

Good Luck for AIPC

[CodeMaker]

ok thanks dip

[CodeMaker]

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