SRM 328 Div1 Medium BlockEnemy

問題

都市がいくつかあり、都市間の道の情報とその道を壊すコストが与えられる。任意の都市間で往来ができるように道路が敷かれており、そのパスは必ず1つだけである（要は閉路がない）。敵に征圧された街の番号が与えられるので、道路をいくつか壊して、征圧された都市同士で往来ができないようにしたい。道路を壊すコストを最小化せよ。

やりかた

単純な深さ優先探索で通る。ある征圧された都市から始めて、つながっている都市を見ていき、別の征圧された都市に辿り着いた時、そこまでの道路の中で最もコストの低い道路を壊す。壊した時点でその道路はもう使用できないフラグをたて、探索をいったんすべて打ち切る。そうするとこの2都市間はもう寸断されたことになるので、また次の征圧された都市を起点に探索を始める、ということをすべての征圧都市に対して行えばよい。

しかし、単に一回ずつ征圧都市から探索をかけるだけだと以下の様なケースで問題が発生する。

オレンジの色が征圧都市だとして、若番から探索を始めていったとする。するとまず都市0からの探索では0-1の道路が壊され、次の都市1からの探索はすでに寸断されているのでなにもしないで終わり、次の都市3からの探索では2-4の道路が壊され、都市4からの探索ではすでに寸断されているため何も壊さず終わる。しかしこのとき0-3の都市はつながったままなのでこのままでは間違い。
なので対策で何回か探索をループしてみて道路破壊が起きなくなった時点で探索終了ってことにする。

以下ソース。

using namespace std;
class BlockEnemy {
public:
  vector<vector<int>> d;
  vector<int> oc;
  bool stop; //探索を打ち切るフラグ
  int ans;
  
  void dfs(int cur, int prev, int f, int t){// f,t : 最小コスト道路の両端の都市
    if(count(ALL(oc), cur) && prev != -1){
      if(stop) return;//探索がすでに打ち切られていたら終わる
      stop = true;
      ans += d[f][t];
      d[f][t] = d[t][f] = INF; //壊した道路は渡れないようにする
      return;
    }
    for(int i = 0; i < (int)d.size(); i++){
      if(i == prev) continue;
      if(d[cur][i] == INF) continue;
      if(d[cur][i] < d[f][t]) dfs(i, cur, cur, i);
      else dfs(i, cur, f, t);
    }
    return;
  }
  int minEffort(int N, vector <string> roads, vector <int> occupiedTowns){
    d.assign(N + 1, vector<int>(N + 1, INF));
    oc = occupiedTowns;
    for(int i = 0; i < (int)roads.size(); i++){
      stringstream ss(roads[i]);
      int a, b, c; ss >> a >> b >> c;
      d[a][b] = d[b][a] = c;
    }

    ans = 0;
    for(int i = 0; i < 1000; i++){//何回かループしてみる
      for(int j = 0; j < (int)oc.size(); j++){
	stop = false;
	dfs(oc[j], -1, N, N);
      }
    }
    
    return ans;
  }
};

できてよかった。