11506: Angry Programmer

問題文
http://uva.onlinejudge.org/external/115/11506.html

コンピュータを頂点、ケーブルを辺とした無向グラフが与えられる。
コンピュータとケーブルを破壊して番号1のコンピュータから
番号Mのコンピュータへのパスをなくしたい。
コンピュータとケーブルを破壊するのにはコストがかかる。
そのような最小のコストを求めよ。

最小カットを求める。ただし頂点にもコストがあるので
頂点を入頂点と出頂点の2つに分ける。
今回は頂点aを入頂点aと出頂点a+mに分けた。

無向グラフなので、2つの頂点a,bを
a+m -> b , b+m -> a
と辺を張って最小カットを求めた。

#include<iostream>
#include<algorithm>
#include<vector>
 
#define INF 1000000000
#define MAX_V 5000
 
using namespace std;
 
struct edge{int to,cap,rev;};
 
vector<edge>G[MAX_V];
bool used[MAX_V];
 
void add_edge(int from,int to,int cap){
  G[from].push_back((edge){to,cap,G[to].size()});
  G[to].push_back((edge){from,0,G[from].size()-1});
}
 
int dfs(int v,int t,int f){
  if(v==t)return f;
  used[v]=true;
  for(int i=0;i<G[v].size();i++){
    edge &e=G[v][i];
    if(!used[e.to] && e.cap>0){
      int d=dfs(e.to,t,min(f,e.cap));
      if(d>0){
        e.cap-=d;
        G[e.to][e.rev].cap+=d;
        return d;
      }
    } 
  }
  return 0;
}
 
int max_flow(int s,int t){
  int flow=0;
  for(;;){
    fill(used,used+MAX_V,0);
    int f=dfs(s,t,INF);
    if(f==0)return flow;
    flow+=f;
  }
}
 
int main(void){
 
  int m,w,a,b,c;
 
  while(cin >> m >> w,m|w){
 
    for(int i=0;i<5000;i++)G[i].clear();
 
    add_edge(1,1+m,INF);
    add_edge(m,m+m,INF);
 
    for(int i=0;i<m-2;i++){
      cin >> a >> c;
      add_edge(a,a+m,c);
    }
    for(int i=0;i<w;i++){
      cin >> a >> b >> c;
      add_edge(a+m,b,c);
      add_edge(b+m,a,c);
    }
    cout << max_flow(1,m+m) << endl;
  }
 
  return 0;
}