# UVa 11506

## Contents

## 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.