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

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Fri Aug 18, 2006 7:50 am

I've used a BFS to find augmenting paths (i.e. Edmonds-Karp), and it worked fine, 0.096 sec.

Gaolious
New poster
Posts: 28
Joined: Mon Nov 04, 2002 8:03 pm
Location: South Korea, Seoul
Contact:

10330

Post by Gaolious » Sun Aug 27, 2006 7:46 pm

I got correct answers for most of input datas in this board.

my the submissions' status is

2006-08-27 17:32:56 Wrong Answer 0.139 528

0.139 sec.


please, give me some critical input datas or ....

if you can test my code, i'll send it to you.

thanks.


addtional, following datas are founded in this board.

Code: Select all

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 
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 
and, my outputs

Code: Select all

37
50
15
7
5
40
0
24
15
4
10
34
7
30

User avatar
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Re: problem 10330, i got WA

Post by Martin Macko » Sun Aug 27, 2006 9:08 pm

The output you posted is correct.

Btw, there is already a thread on this problem. If there is a thread on a particular problem, please, use it to post your question and do not create a new one. (see http://online-judge.uva.es/board/viewtopic.php?t=2086, http://online-judge.uva.es/board/viewtopic.php?t=9914 and http://online-judge.uva.es/board/viewtopic.php?t=8509)
forum 'Volume CIII' description wrote:All about problems in Volume CIII. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

kwedeer
New poster
Posts: 44
Joined: Thu Dec 15, 2005 11:28 pm

Post by kwedeer » Sat Sep 02, 2006 4:05 pm

OK - I have now got agreement with the test case provided in tasks and also - with the largest tests case provided in this thread - but - my program is still not accepted by judge - it give WA - so - I am posting my code and may some can execute it against some other judge test cases and provide the test case against my code fails. Thanks in advance for any help!

I used max flow algorithm with breadth-first search for augmenting path, capacities and actual flow network is represented by matrix - static 2D array.

Code: Select all

program Prg10330(input, output);

{$APPTYPE CONSOLE}

uses
  SysUtils;

const infCapacity: Double=100000;

var  N,M: Integer; //number of initial vertices and
                   //          initial edges
     { 0 - source,
       1...2N - odd - vertice with incoming flow
                even - vertices with outcoming flov
       2N+1 - target         }
     nodes: array [0..201,0..201] of double; //capacities - constants
     flow: array [0..201,0..201] of double; //flow - to calculate to final flow
     i,j: Integer;
     capacity: double;
     vi,vj: Integer;
     source,target: Integer;
     pathExist: Boolean;
     //for breadth-first-search
     targetAchieved, targetDecided: boolean;
     distance: array [0..201] of Integer;
     queue: array [0..201] of Integer;
     queueLength: Integer;
     predecessors: array [0..201] of Integer;
     color: array [0..201] of byte;
     head,freeSlot: Integer;
     u: Integer;
     //--- (bfs)
     rSource,rTarget: Integer;
     //augmenting path
     minCapacity: Double;
     pathCompleted: Boolean;
     currNode: Integer;
     maxFlow: Double;
     numberBPoints,numberDPoints: Integer;
     infNode: Integer;
     numberOfCases: Integer;

  procedure enqueue(value: Integer);
  begin
    queue[freeSlot]:=value;
    inc(freeSlot);
    inc(queueLength);
  end;

  procedure dequeue;
  begin
    inc(head);
    dec(queueLength);
  end;

  function queueHead: Integer;
  begin
    if queueLength>0
      then Result:=queue[head]
      else Result:=-1;
  end;

  procedure initialiseQueue;
  begin
    head:=0;
    freeSlot:=0;
    queueLength:=0;
  end;

  {--- for debug ---}

  procedure printCapacities;
  var ii,jj: Integer;
      lvar: double;
  begin
    writeln('=== begin - capacities ===');
    for ii:=0 to target do begin
      for jj:=0 to target do begin
        lvar:=nodes[ii,jj];
        write(Format('%.2f ',[lvar]));
      end;
      writeln;
    end;
    writeln('=== end - capacities ===');
  end;

  procedure printFlow;
  var ii,jj: Integer;
  begin
    writeln('=== begin - flow ===');
    for ii:=0 to target do begin
      for jj:=0 to target do begin
        write(Format('%.2f ',[flow[ii,jj]]));
      end;
      writeln;
    end;
    writeln('=== end - flow ===');
  end;

  procedure printPath;
  var ii: Integer;
  begin
    writeln('--- path - begin ---');
    for ii:=0 to target do begin
      if predecessors[ii]>-1 then
        writeln(IntToStr(predecessors[ii])+' -> '+IntToStr(ii));
    end;
    writeln('--- path - end ---');
  end;

  {--- --- ---}



begin
{
 AssignFile(Input, 'in12__.txt');
 Reset(Input);
 AssignFile(Output, 'out12__.txt');
 Rewrite(Output);
 }
numberOfCases:=0;
while not EoF do begin
  inc(numberOfCases);
  readln(N);
  target:=2*N+1;
  for i:=0 to target do
    for j:=0 to target do
      nodes[i,j]:=0.0;
  for i:=1 to N do begin
    //nodes
    read(capacity);
    nodes[2*i-1,2*i]:=capacity;
    nodes[2*i,2*i-1]:=capacity;
  end;
  read(M);
  for i:=1 to M do begin
    readln;
    read(vi);
    read(vj);
    read(capacity);
    nodes[2*vi,2*vj-1]:=capacity;
  end;
  {each node is split into 2 nodes - one server as input to initial
   node and the ohte node serves for giving output. The source and target
   B, D is not included in nodes - they are separate vortices in grpah }
  rSource:=0;
  rTarget:=target;
  read(numberBPoints);
  read(numberDPoints);
  readln;
  for i:=1 to numberBPoints do begin
    read(infNode);
    nodes[rSource,2*infNode-1]:=infCapacity;
  end;
  for i:=1 to numberDPoints do begin
    read(infNode);
    nodes[2*infNode,rTarget]:=infCapacity;
  end;
  //assign infinite capacity to edges... - one can safely assume that
  //there is not direct connection with infinite capacity among s-t
  for i:=0 to target do
    for j:=0 to target do
      flow[i,j]:=0.0;

  //printCapacities;

  //augmenting path doesn't exist if target is not added  to predecessors array
  pathExist:=True;
  while pathExist do begin
   //bfs  - begin
    for i:=0 to 201 do
      predecessors[i]:=-1;
    initialiseQueue;
    distance[rSource]:=0;
    predecessors[rSource]:=0;
    enqueue(rSource);
    targetAchieved:=false;
    targetDecided:=false;
    for i:=0 to 201 do
      color[i]:=1;
    color[rSource]:=2;
    while ((not targetAchieved) and (not targetDecided)) do begin
      //the search is done if no more vortices are in queue
      u:=queueHead;
      if u>-1 then begin
        for i:=1 to target do begin
           if (((nodes[u,i]-flow[u,i])>0) and (color[i]=1) and (i<>u)) then begin
             color[i]:=2;
             distance[i]:=distance[u]+1;
             predecessors[i]:=u;
             enqueue(i);
             if i=target then begin
               targetAchieved:=True;
               targetDecided:=True
             end;
           end;
        end; //for i... - over all the members of adjacency list
        dequeue;
        color[u]:=3;
      end else begin
        targetDecided:=True
      end;
    end; //while not targetAchieved...
    if targetAchieved then begin

      minCapacity:=infCapacity;
      pathCompleted:=False;
      currNode:=Target;
      while not pathCompleted do begin
        if (
            ( (nodes[predecessors[currNode],currNode]-
               flow[predecessors[currNode],currNode])>0
            ) and
            ( (nodes[predecessors[currNode],currNode]-
               flow[predecessors[currNode],currNode])<minCapacity
            )
           ) then
          minCapacity:=nodes[predecessors[currNode],currNode]-
                       flow[predecessors[currNode],currNode];
        if predecessors[currNode]=rSource
          then pathCompleted:=True
          else currNode:=predecessors[currNode];
      end; //while not pathCompleted
      //update capacity values - only along augmenting path
      pathCompleted:=False;
      currNode:=Target;

      //before update
      //printCapacities;
      //printFlow;
      //printPath;

      while not pathCompleted do begin
        //update flow, there is no need to update the values
        //of residual network, because these values are computed
        //each time whne they are reuired from vertex
        {and the final flow is all the real flow into target - one should
         see thatL there is 2 different numbers: capaciy (which can be
         infinite as well) and flow (only finite values)}
        flow[predecessors[currNode],currNode]:=
          flow[predecessors[currNode],currNode]+minCapacity;
        flow[currNode,predecessors[currNode]]:=
          (-1.0)*flow[predecessors[currNode],currNode];
        if predecessors[currNode]=rSource
          then pathCompleted:=True
          else currNode:=predecessors[currNode];
      end; //while not pathCompleted

      //after update
      //printFlow;

      pathExist:=True;
    end else begin //if targetAchieved...
      //augmenting path is not found - so - matrix contains the maximum flow
      pathExist:=False;
    end; //if targetAchieved
  end;//while pathExists


    //augmenting path no more can be found - so the maximum flow network
    //construction is completed. Flow is the total flow into target e.g.
    //sum of flow[..,..] elements on target column.
    maxFlow:=0.0;
    for i:=0 to target do
      maxFlow:=maxFlow+flow[i,rTarget];
    if numberOfCases>1 then writeln;
    write(round(maxFlow));


end; //while not Eof


end.

medv
Learning poster
Posts: 85
Joined: Sun Jul 14, 2002 1:17 pm

10330 Time Limit - I used BFS - Edmonds-Karp

Post by medv » Thu Aug 23, 2007 7:18 pm

Why Time Limit?
How to improve solution?

#include <stdio.h>
#include <memory.h>
#define MAX 202
#define INF 1000000000
#define min(i,j) (i<j)?i:j

int m,n,a,b,d,cap,i;
int MaxFlow,flow;
int g[MAX][MAX],used[MAX];

int aug(int x,int t,int CurFlow)
{
if (x == t) return CurFlow;
if (used[x]++) return 0;

for (int Flow,y = 0; y <= 2*n+1; y++)
{
if (g[x][y] > 0 && (Flow = aug(y,t,min(CurFlow,g[x][y]))))
{
g[x][y] -= Flow; g[y][x] += Flow;
return Flow;
}
}
return 0;
}

void main (void)
{
while(scanf("%d",&n)==1)
{
memset(g,0,sizeof(g));
for(i=1;i<=n;i++)
scanf("%d",&cap), g[2*i-1][2*i] = cap;
scanf("%d",&m);
for(i=1;i<=m;i++)
{
scanf("%d %d %d",&a,&b,&cap);
g[2*a][2*b-1] = cap;
}
scanf("%d %d",&b,&d);
for(i=1;i<=b;i++)
scanf("%d",&a), g[0][2*a-1] = INF;
for(i=1;i<=d;i++)
scanf("%d",&a), g[2*a][2*n+1] = INF;

MaxFlow = 0;
do
{
memset(used,0,sizeof(used));
} while ((flow = aug(0,2*n+1,0x7FFFFFFF)) && (MaxFlow += flow));

printf("%d\n",MaxFlow);
}
}

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Fri Aug 24, 2007 6:22 am

medv wrote:10330 Time Limit - I used BFS - Edmonds-Karp
No, you didn't - you use DFS. There are graphs on which it's too slow.

Greus
New poster
Posts: 2
Joined: Sun Sep 16, 2007 2:01 am

Re: 10330 Power Transmission

Post by Greus » Sun Sep 16, 2007 2:07 am

could some one help me!!!
why my code receive wrong answer???
This is my code

Code: Select all

#include <stdio.h>
#include <list>
#include <algorithm>

#define MAXNODES 105
#define NULO -1
#define INFINITO 300000

using namespace std;

typedef struct{
        int flujo;
        int capacidad;
}FLUJO;

FLUJO grafo[MAXNODES][MAXNODES];
int nvert, padre[MAXNODES];

void inicia_grafo(void){
     int i, j;
     
     for(i = 0; i < nvert; i++)
           for(j = 0; j < nvert; j++){
                 grafo[i][j].capacidad = 0;
                 grafo[i][j].flujo = 0;
           }
}

void inserta_arista(int o, int d, int c){
     grafo[o][d].capacidad = c;
}

int BFS(int fuente, int sumidero){
    int visitado[MAXNODES], u, v, residual;
    list <int> cola;
    
    for(u = 0; u < nvert; u++){
          padre[u] = NULO;
          visitado[u] = 0;
    }
    
    cola.clear();
    
    visitado[fuente] = 1;
    cola.push_back(fuente);
    while(!cola.empty()){
               u = cola.front();
               cola.pop_front();
               for(v = 0; v < nvert; v++){
                     residual = grafo[u][v].capacidad - grafo[u][v].flujo;
                     if(!visitado[v] && residual > 0){
                                     cola.push_back(v);
                                     padre[v] = u;
                                     visitado[v] = 1;
                     }
               }
    }
    return visitado[sumidero];
}

int ford_fulkerson(int fuente, int sumidero){
    int i, j, u;
    int flujomax, incremento, residual;
    
    for(i = 0; i < nvert; i++)
          for(j = 0; j < nvert; j++)
                grafo[i][j].flujo = 0;
    
    flujomax = 0;
    while(BFS(fuente, sumidero) == 1){
          incremento = INFINITO;
          for(u = sumidero; padre[u] != NULO; u = padre[u]){
                residual = grafo[padre[u]][u].capacidad - grafo[padre[u]][u].flujo;
                incremento = min(incremento, residual);
          }
          for(u = sumidero; padre[u] != NULO; u = padre[u]){
                grafo[padre[u]][u].flujo+=incremento;
                grafo[u][padre[u]].flujo-=incremento;
          }
          flujomax+=incremento;
    }
    return flujomax;
}

int main(){
    int n, m, b, j, o, d, c, i;
    int cap[200], maxflow;
    bool primero = true;
    
    while(scanf("%d", &n) != EOF){
          if(primero)
              primero = false;
          else
              printf("\n");        
          nvert = n+2;
          memset(cap, 0, sizeof(cap));
          inicia_grafo();
          for(i = 0; i < n; i++)
                scanf("%d", &cap[i+1]);
          scanf("%d", &m);
          for(i = 0; i < m; i++){
                scanf("%d %d %d", &o, &d, &c);
                if(c > cap[o])
                     inserta_arista(o, d, cap[o]);
                else
                     inserta_arista(o, d, c);
          }
          scanf("%d %d", &b, &j);
          for(i = 0; i < b; i++){
                scanf("%d", &d);
                inserta_arista(0, d, INFINITO);
          }
          for(i = 0; i < j; i++){
                scanf("%d", &o);
                inserta_arista(o, n+1, cap[o]);
          }      
          maxflow = ford_fulkerson(0, n+1);
          printf("%d", maxflow);
    }
    return 0;
}
[Edited by Jan] : Next time use code tags.

Obaida
A great helper
Posts: 380
Joined: Wed Jan 16, 2008 6:51 am
Location: (BUBT) Dhaka,Bagladesh.

Re: 10330 - Power Transmission

Post by Obaida » Thu Feb 05, 2009 6:41 am

Some 1 help me. I got RTE...

Code: Select all

#include<stdio.h>
int main()
{
	int n,regulator[101],link[500],left[501],right[501],m,barishal[101],dhaka[101],b,d,max,sum,i,j,k;
	while(scanf("%d",&n)==1)
	{
		for(i=0;i<n;i++)
			scanf("%d",&regulator[i]);
		scanf("%d",&m);
		for(i=0;i<m;i++)
			scanf("%d %d %d",&left[i],&right[i],&link[i]);
		scanf("%d %d",&b,&d);
		for(i=0;i<b;i++)scanf("%d",&barishal[i]);
		for(i=b;i<b+d;i++)scanf("%d",&dhaka[i]);
		sum=0;
		for(i=0;i<b;i++)
		{
			max=0;
			for(j=b;j<b+d;j++)
			{
				for(k=0;k<m;k++)
				{
					if(left[k]-1==i&&right[k]==dhaka[j])break;
				}
				if(regulator[barishal[i]-1]<=link[k])
				{
					if(regulator[barishal[i]-1]>max)max=regulator[barishal[i]-1];
				}
				else
				{
					if(link[k]>max)max=link[k];
				}
			}
			sum+=max;
		}
		printf("%d\n",sum);
	}
	return 0;
}
try_try_try_try_&&&_try@try.com
This may be the address of success.

AKJ88
New poster
Posts: 20
Joined: Wed Feb 13, 2013 10:48 am

Re: 10330 - Power Transmission

Post by AKJ88 » Wed Mar 06, 2013 10:23 pm

Hi.
Can anyone tell me what is wrong with my code, please?
I've pass all test cases in the forum and got the correct answer, but still WA.
Thanks.

Code: Select all

#include <cstdio>
#include <queue>
#include <cstring>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;
typedef long long lLong;

int N, parents[102];  //src:0 dst:N+1
lLong adjMat[102][102], regCapacity[102], maxFlow, f;
bool visited[102];

void findMinFlow(int u, lLong minFlow){
	if(u==0){ //source node
		f = minFlow;
		return;
	}else if(parents[u]!=-1){
		findMinFlow(parents[u], min(minFlow, min(regCapacity[ parents[u] ], adjMat[ parents[u] ][u]) ));
		adjMat[ parents[u] ][u] -= f;
		regCapacity[ parents[u] ] -= f;
		adjMat[u][ parents[u] ] += f;
	}
}

int main(){
#ifndef ONLINE_JUDGE
	freopen("J:\\acm\\powerst.in", "r", stdin);
#endif // !ONLINE_JUDGE
	int I, M, u, v, c, srcRegC, dstRegC, dst;

	while( scanf("%d", &N)==1 ){
		memset(adjMat, 0, sizeof(adjMat));

		for(I=1; I<=N; I++)
			scanf("%d", &regCapacity[I]);
		scanf("%d", &M);
		while( M-- ){
			scanf("%d %d %d", &u, &v, &c);
			adjMat[u][v] = c;
		}

		scanf("%d %d", &srcRegC, &dstRegC);
		regCapacity[0] = regCapacity[N+1] = INT_MAX;
		while( srcRegC-- ){
			scanf("%d", &v);
			adjMat[0][v] = INT_MAX; 
		}
		while( dstRegC-- ){
			scanf("%d", &u);
			adjMat[u][N+1] = INT_MAX; 
		}

		maxFlow = 0; dst = N+1;
		while(true){
			memset(visited, 0, sizeof(visited));
			memset(parents, -1, sizeof(parents));
			queue<int> q; q.push(0);//source
			visited[0] = true;

			while( !q.empty() ){
				u = q.front(); q.pop();
				if(u==dst)
					break;
				if(regCapacity[u]<=0)
					continue;

				for(v = 1; v<=dst; v++){ // here I use dst becuase is greater than all other nodes.
					if(!visited[v] && adjMat[u][v]>0){
						visited[v] = true;
						parents[v] = u;
						q.push(v);
					}
				}
			}

			f = 0;
			findMinFlow(dst, INT_MAX);
			if(f == 0)
				break;
			maxFlow += f;
		}

		printf("%lld\n", maxFlow);
	}

	return 0;
}


lbv
Experienced poster
Posts: 128
Joined: Tue Nov 29, 2011 8:40 am

Re: 10330 - Power Transmission

Post by lbv » Thu Mar 07, 2013 12:06 am

AKJ88 wrote:Hi.
Can anyone tell me what is wrong with my code, please?
I've pass all test cases in the forum and got the correct answer, but still WA.
In this line:

Code: Select all

scanf("%d", &regCapacity[I]);
you're using the %d format specifier with a "long long" variable. Use %lld instead. Try to configure your compiler to show you all warnings; that can help you catch this type of bugs.

Other than that, you may try these cases:

Input

Code: Select all

4
26 103 114 200
6
4 2 110
2 3 153
1 2 143
3 4 181
4 1 154
1 3 185
2 2
4 1 2 3

6
133 46 47 21 121 182
14
6 2 41
4 5 132
3 2 19
2 1 98
5 3 40
3 4 52
5 2 200
5 1 113
4 2 191
1 4 9
6 5 47
3 1 177
6 4 102
3 6 191
3 3
6 4 3 1 2 5

10
271 876 905 472 468 258 531 933 235 845
24
9 3 676
5 3 467
9 8 400
6 10 718
4 5 580
3 2 869
4 7 125
7 6 734
7 9 968
4 9 956
6 4 182
9 2 607
4 1 824
5 8 784
3 1 360
2 5 61
2 8 990
5 9 585
5 6 628
4 3 336
1 9 625
4 10 616
9 10 952
1 10 941
2 8
7 5 3 1 8 9 10 4 2 6

12
228 73 777 35 285 392 874 602 505 892 208 898
44
5 1 21
11 7 510
3 8 689
8 6 950
3 5 223
2 3 944
11 12 800
9 8 727
10 8 22
4 3 710
6 5 634
12 2 856
2 10 465
9 6 299
8 5 673
3 6 812
1 2 324
2 9 346
6 11 407
12 5 603
1 8 515
5 10 528
4 2 109
1 12 516
9 7 607
7 6 745
12 3 313
6 12 618
4 10 727
2 7 558
4 11 235
5 11 987
2 5 234
11 8 419
8 2 581
7 3 391
9 10 378
12 4 220
6 10 50
4 7 157
1 4 112
2 11 999
10 12 910
7 8 584
3 9
2 12 8 3 4 10 11 6 5 9 7 1
Output

Code: Select all

129
156
961
1098

AKJ88
New poster
Posts: 20
Joined: Wed Feb 13, 2013 10:48 am

Re: 10330 - Power Transmission

Post by AKJ88 » Thu Mar 07, 2013 1:02 pm

Thanks lbv.
I'd constructed the graph in a wrong way, after reconstructing it got AC.
But can you tell me why constructing the graph in the way I did (like problem stated regulators (nodes) and links have their own capacity and we calculate min flow by getting min(parent, link between u and parent)) is wrong?

lbv
Experienced poster
Posts: 128
Joined: Tue Nov 29, 2011 8:40 am

Re: 10330 - Power Transmission

Post by lbv » Thu Mar 07, 2013 11:47 pm

AKJ88 wrote:can you tell me why constructing the graph in the way I did (like problem stated regulators (nodes) and links have their own capacity and we calculate min flow by getting min(parent, link between u and parent)) is wrong?

I'm not entirely sure about this, but consider this example:

Code: Select all

4
41 73 2 81
4
1 3 64
2 1 78
2 3 60
1 4 85
2 2
1 2 3 4
The graph from this case would look something like this:
Image

If you analyse it for a moment, you'll see that the answer for this case should be 43, by pumping power through the paths B->1->4->D and B->2->3->D. However, your old code prints 41. I don't fully understand that code, but my guess is that something like this happens:

You try to find the first augmenting path, and you find B->1->3->D, with cost 2. At this point, you subtract 2 from all the edges, and nodes along that path, so the graph becomes:

Image

By this point, node 3 has become a dead-end, no more energy can go through it, so it's easy to see that the max flow now is only 39, making a total of 2+39=41.

If you build the graph using two nodes per regulator, and using an edge to represent the capacity of each generator, then the graph could initially look like this:

Image

And then if the first augmenting path you find is B->1->3->D, the situation would look like this:

Image

As you can see, the difference here is that regulator #3 doesn't become a dead end now, and you can still add 41 more power to the total flow at this point, which makes for a total of 2+41=43.

AKJ88
New poster
Posts: 20
Joined: Wed Feb 13, 2013 10:48 am

Re: 10330 - Power Transmission

Post by AKJ88 » Tue Mar 12, 2013 10:40 am

@lbv
Thanks a million for your reply.
Now I understand why it doesn't work.
Thanks.

kien_coi_1997
New poster
Posts: 3
Joined: Tue Jan 08, 2013 4:27 pm

Re: 10330 - Power Transmission

Post by kien_coi_1997 » Mon Sep 02, 2013 5:38 pm

@lbv, @AKJ88, Thank you so much, I understood why I got Wrong Answer.

Post Reply

Return to “Volume 103 (10300-10399)”