Página Principal

MC521-1s2014

MC621-2s2014

MC521-1s2015

MC621-2s2015

MC521-1s2016

Conteúdo

Área Reservada

edit sidebar

UVA 10480

Autor: Mateus Bellomo

Código:

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <iostream>
#include <cmath>
#include <cstdlib>
#include <cassert>
#include <time.h>
#include <ctime>

using namespace std;

#define INF 0x3f3f3f3f
#define MAX 60

typedef long long ll;

ll C[MAX][MAX]; //capacity matrix
ll F[MAX][MAX]; //the flow with maximum value
ll M[MAX];
ll ADJ[MAX][MAX];
int P[MAX]; //parent
ll Cf;
int n, m;
queue<int> q;

bool v[MAX];
set<int> reachedv;
set<int>::iterator it;

ll bfs(int s, int t){

  for(int i = 1; i <= n; i++)
    P[i] = -1;
  P[s] = -2;

  M[s] = INF;
  while(!q.empty()) q.pop();

  q.push(s);
  while(!q.empty()){
    int u = q.front(); q.pop();

    for(int i = 1; i <= n; i++)
      if(C[u][i])
        //There's a positive edge and the node has not been visited
        if(C[u][i] - F[u][i] > 0 && P[i] == -1){
          P[i] = u;
          M[i] = min(M[u], C[u][i] - F[u][i]);
          if(i != t)
            q.push(i);
          else
            return M[i];
        }
  }

  return 0;
}


void edmonds_karp(int s, int t){

  for(int i = 1; i <= n; i++)
    for(int j = 1; j <= n; j++)
      F[i][j] = 0;

  Cf = bfs(s, t);
  while(Cf != 0){

    int v = t;
    while(v != s){
      int u = P[v];
      if(C[u][v]) F[u][v] += Cf;
      else F[v][u] -= Cf;
      v = u;
    }

    Cf = bfs(s,t);
  }

}

void dfs_visit(int u){
  v[u] = true;
  reachedv.insert(u);

  for(int i = 1; i <= n; i++)
    if(ADJ[u][i] > 0 && !v[i])
      dfs_visit(i);
}

void dfs(int s){
  for(int i = 1; i <= n; i++)
    v[i] = false;
  reachedv.clear();

  dfs_visit(s);
}

void getmincut(int s){
  dfs(s);

  for(it = reachedv.begin(); it != reachedv.end(); it++)
    for(int j = 1; j <= n; j++)
      if(*it != j && C[*it][j] && !reachedv.count(j) && ADJ[*it][j] <= 0)
        printf("%d %d\n", *it, j);

}

void clear(){
  for(int i = 0; i < MAX; i++)
    for(int j = 0; j < MAX; j++)
      C[i][j] = F[i][j] = 0;
}

int main(){

  scanf(" %d %d", &n, &m);
  while(n != 0 || m != 0){
    for(int i = 0; i < m; i++){
      int a, b, p;
      scanf(" %d %d %d", &a, &b, &p);
      C[a][b] = p;
      C[b][a] = p;
    }

    edmonds_karp(1, 2);

    for(int i = 1; i <= n; i++)
      for(int j = 1; j <= n; j++)
        ADJ[i][j] = C[i][j] - F[i][j];


    getmincut(1);
    printf("\n");
    scanf(" %d %d", &n, &m);
    clear();
  }

  return 0;
}