UVa 11506

From Algorithmist
Jump to navigation Jump to search

11506 - Angry Programmer[edit]

Summary[edit]

Given a simple undirected graph with N (<=50) vertices. Each vertex (except vertex #1 and vertex #N) can be removed with a cost. Similarly, each edge can be removed with a cost. You want to make vertex #1 to be disjoint with vertex #N by removing some vertices or edges and you want to do it with minimal total cost.

Explanation[edit]

A slight modification to the graph can reduce this problem into the minimum-cut problem, which is the dual of the maximum-flow problem. That is by splitting each vertex into two vertices and connect them with an edge with a removal cost equal to the vertex's removal cost.

Gotchas[edit]

  • The flow graph has to be directed.

Implementations[edit]

A simple implementation based on Ford-Fulkerson method to find the maximum-flow of the graph can be used to find the minimum-cut of the graph.

#include <stdio.h>

#define REP(i,n) for (int i=0,_n=n; i<_n; i++)
#define INF 1000000000
#define MAXN 100

int res[MAXN][MAXN], vis[MAXN], n;

int augpath(int so, int si, int mf){
  vis[so] = true;
  if (so==si) return mf;
  REP(i,n) if (!vis[i] && res[so][i]>0){
    int flow = augpath(i,si,mf <? res[so][i]);
    if (flow>0){
      res[so][i] -= flow;
      res[i][so] += flow;
      return flow;
    }
  }
  return 0;
}

int maxflow(int so, int si){
  int ret = 0;
  while (true){
    REP(i,n) vis[i] = 0;
    int flow = augpath(so,si,INF);
    if (flow == 0) return ret;
    ret += flow;
  }
}

int main(){
  for (int N,E,a,b,c; scanf("%d %d",&N,&E)!=EOF && (N||E); ){
    n = 2*N;  // split each vertex into 2 vertices
    REP(i,n) REP(j,n) res[i][j] = 0;  // initialize residue
    res[0][N] = res[N-1][N+N-1] = INF;  // server and boss
    REP(i,N-2){
      scanf("%d %d",&a,&c); a--;
      res[a][N+a] = c;
    }
    REP(i,E){
      scanf("%d %d %d",&a,&b,&c); a--; b--;
      res[N+a][b] = res[N+b][a] = c;
    }
    printf("%d\n",maxflow(0,N+N-1));
  }
}

Optimizations[edit]

Storing the flow network using adjacency list can be faster, however it is slightly harder to implement.