AOJ2033

AOJ2033

まず強連結成分分解する。
その後、連結成分を圧縮した森でルートとなっている頂点を探す。
その頂点に含まれる本来の頂点のどれかをそれ単体で作成する。

強連結成分分解のコードを描いたのがだいぶ昔なので、描き直したい衝動に駈られている。

#include <algorithm>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <vector>
#include <sstream>

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cassert>

#define REP(i, n) for(int i=0; i<(int)n; ++i)
#define FOR(i, c) for(__typeof((c).begin())i=(c).begin();i!=(c).end();++i)
#define ALL(c) (c).begin(),(c).end()
#define each(i, c) FOR(i, c)

#define VAR(a) cout << #a << " : " << a << endl;

typedef long long int lli;

using namespace std;

const int inf = 1 << 29;

struct Edge{
  int src, dst, cost;
  Edge(int s, int d) : src(s), dst(d), cost(inf) {}
  Edge(int s, int d, int c) : src(s), dst(d), cost(c) {}
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

void visit(const Graph &G, int n, int order[], int &time, bool visited[])
{
  visited[n] = true;
  FOR(e, G[n]){
    if(!visited[e->dst])
      visit(G, e->dst, order, time, visited);
  }
  order[--time] = n;
  return ;
}

vector< vector<int> > detectSCC(const Graph &G)
{
  const int size = G.size();
  bool visited[size];
  int order[size], scc[size], time, prev = size - 1;
  vector< vector<int> > S;
  Graph H(size);
  fill(order, order + size, -1);
  fill(scc, scc + size, -1);
  REP(i, size){
    FOR(e, G[i])
      H[e->dst].push_back(Edge(e->dst, e->src));
  }
  time = size;
  fill(visited, visited + size, false);
  REP(i, size){
    if(!visited[i])
      visit(G, i, order, time, visited);
  }
  time = size;
  fill(visited, visited + size, false);
  REP(i, size){
    if(!visited[order[i]]){
      visit(H, order[i], scc, time, visited);
      int j = prev;
      vector<int> T;
      for(j=prev; 0 <= j && scc[j] != -1; --j)
        T.push_back(scc[j]);
      prev = j;
      S.push_back(T);
    }
  }
  return S;
}

int main(int argc, char *argv[])
{
  int node;
  while (cin >> node && node) {
    map<string, int> name;

    Graph g(node);
    int cost[node];

    for (int i = 0, cnt = 0; i < (int)node; ++i) {
      string s, t;
      int a, b;
      cin >> s >> a >> t >> b;
      if (name.count(s)) ; else name[s] = cnt++;
      if (name.count(t)) ; else name[t] = cnt++;
      int dst = name[s];
      int src = name[t];
      g[src].push_back(Edge(src, dst, b));
      cost[dst] = a;
    }

    vector< vector<int> > scc = detectSCC(g);
    map<int, int> rename;
    for (int i = 0; i < (int)scc.size(); ++i) {
      for (int j = 0; j < (int)scc[i].size(); ++j) {
        rename[scc[i][j]] = i;
      }
    }

    int sum = 0;

    int mn[scc.size()];
    fill(mn, mn + scc.size(), inf);

    bool root[scc.size()];
    fill(root, root + scc.size(), true);

    for (int i = 0; i < (int)node; ++i) {
      each (e, g[i]) {
        int src = rename[e->src];
        int dst = rename[e->dst];
        if (src == dst) {
          mn[dst] = min(mn[dst], cost[e->dst] - e->cost);
        } else {
          root[dst] = false;
        }
        sum += e->cost;
      }
    }

    for (int i = 0; i < (int)scc.size(); ++i) {
      if (root[i]) sum += mn[i];
    }

    cout << sum << endl;
  }
  return 0;
}