AOJ 1065 - The House of Huge Family -

問題文

重み付き有向グラフが与えられる。
頂点を２つのグループに分け、お互いの頂点間を移動できないようにしたい。
そのために、辺を取り除いていくことができる。
取り除いた辺の重みの最小値は？
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1065

解法

有向グラフの任意の２頂点間に共通して到達できる/到達されることができる頂点があることは、その有向グラフを無向グラフして考えた時グラフが連結であることの必要十分条件である（ほんとか？）。

つまり与えられた有向グラフを無向グラフとしたとき、そのグラフが非連結になるように辺をとったときの最小値を求めればいい。
また、頂点数Nの無向グラフが連結であるために必要な辺の最小はN-1であることと、この問題では辺は高々N本しか与えられないことから削除する辺は２本以下になることが分かる。
あと、負の重みを持つ辺は最初から削除しておいた方がお得なのは自明なので、その総和をとっておいて後から足すことにする。

削除する必要のある辺が０、１、２それぞれの場合について考える。
0 : 与えられたグラフが非連結な場合のみなので、最初にグラフの連結判定をして確かめる。
1 : 辺が橋（取り除くとグラフが非連結になる辺）の場合である。lowlinkを用いた橋の列挙を行う。
2 : どの２本の辺を取り除いてもグラフは非連結になる。

0の場合は例外として、 1と2のminをとった値に負の辺の重みを足したものが最終的な答えとなる。

ソースコード

vector<Pii> G[101];
int min_bridge = INF;
int ord[101], low[101];
bool vis[101];

void dfs(int v, int p, int &k) {
  vis[v] = true;

  ord[v] = k++;
  low[v] = ord[v];

  Rep(i, G[v].size()) {
    if ( !vis[G[v][i].fr] ) {
      dfs(G[v][i].fr, v, k);
      low[v] = min(low[v], low[G[v][i].fr]);      
      if ( ord[v] < low[G[v][i].fr] ) min_bridge = min(min_bridge, G[v][i].sc);
    } else if ( G[v][i].fr != p ) {
      low[v] = min(low[v], ord[G[v][i].fr]);
    }        
  }
  
}

void dfs2(int v) {
  if ( vis[v] ) return;
  vis[v] = true;
  Rep(i, G[v].size()) {
    dfs2(G[v][i].fr);
  }  
}

signed main() {
  int n, m;
  while ( cin >> n >> m, n | m ) {
    int minus_cost = 0;
    min_bridge = INF;
    int min_1 = INF, min_2 = INF;
    Rep(i, 101) {
      G[i].clear();
      vis[i] = false;
    }
    
    Rep(i, m) {
      int a, b, c;
      cin >> a >> b >> c;
      if ( c <= 0 ) minus_cost += c;
      else {
    if ( min_1 > c ) min_2 = min_1, min_1 = c;
    else if ( min_2 > c ) min_2 = c;
    G[a].pb(Pii(b, c));
    G[b].pb(Pii(a, c));
      }
    }

    dfs2(0);
    bool is_connected = true;
    Rep(i, n) {
      if ( !vis[i] ) {
    is_connected = false;
    break;
      }
    }

    if ( !is_connected ) {
      cout << minus_cost << endl;
      continue;
    }
    
    Rep(i, n) vis[i] = false;
    int k = 0;
    Rep(i, n) {
      if ( !vis[i] ) dfs(i, -1, k);
    }

    if ( min_bridge == INF ) cout << minus_cost << endl;
    else cout << min(min_bridge, min_1+min_2) + minus_cost << endl;
  }

  return 0;
}

参考
橋の列挙　http://kagamiz.hatenablog.com/entry/2013/10/05/005213

反省とか

最初なにも考えずに全点間の最小カットを求めて…みたいなことをしていたが明らかにTLE。