OJ 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 

Code: Select all

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

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.

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;
}

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;
}

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;
}

Code: Select all

scanf("%d", &regCapacity[I]);

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

Code: Select all

129
156
961
1098

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