AOJ 1350 : There is No Alternative

問題リンク:There is No Alternative | Aizu Online Judge

問題概要:
重み付き無向グラフが与えられる
これに対する最小全域木は複数存在しうるが、それら全ての最小全域木に共通して存在する辺の数とそれらの総和を求めよ

解法:
Kruskal法を用いてMSTを構築する
全ての最小全域木に共通して存在するような辺は、その辺の重み以下の辺からなるグラフにおける橋となる
辺を小さい順に追加してグラフを構築しつつ追加する辺の重みが変わるタイミングで橋を求め、それらを数えれば良い

コード:

#include<bits/stdc++.h>

#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)

using namespace std;

struct Edge { 
  int src,dst,w; 
  bool operator < ( const Edge& e ) const {
    if( w != e.w ) return w < e.w;
    if( src != e.src ) return src < e.src;
    return dst < e.dst;
  }
};
const int MAX_V = 510; //
int V,E; //
vector<Edge> G[MAX_V]; // undirected graph
vector<int> dfs_num,dfs_low,dfs_parent,articulation_vertex;
int dfsNumberCounter, dfsRoot, rootChildren;
int cost[MAX_V][MAX_V];

//O(V+E)
int base_weight;
vector<Edge> bridges;
#define UNVISITED -1
void articulationPointAndBridge(int u){
  dfs_low[u] = dfs_num[u] = dfsNumberCounter++;
  rep(j,(int)G[u].size()){
    Edge &v = G[u][j];
    if( dfs_num[v.dst] == UNVISITED ) {
      dfs_parent[v.dst] = u;
      if( u == dfsRoot ) rootChildren++;

      articulationPointAndBridge(v.dst);

      if( dfs_low[v.dst] >= dfs_num[u] ) articulation_vertex[u] = true;
      if( dfs_low[v.dst] >  dfs_num[u] ) {
        if( base_weight == cost[u][v.dst] ) {
          bridges.push_back((Edge){u,v.dst,base_weight});
        }
        //printf("Edge (%d,%d) is a bridge\n",u,v.dst);
      }
      dfs_low[u] = min(dfs_low[u],dfs_low[v.dst]);
    } else if( v.dst != dfs_parent[u] ) {
      dfs_low[u] = min(dfs_low[u],dfs_num[v.dst]);
    }
  }
}

void calculateArticulationPointAndBridge(){
  dfsNumberCounter = 0;
  dfs_num.assign(V,UNVISITED);
  dfs_low.assign(V,0);
  dfs_parent.assign(V,0);
  articulation_vertex.assign(V,0);
  
  //printf("Bridges:\n");
  rep(i,V) {
    if( dfs_num[i] == UNVISITED ) {
      dfsRoot = i, rootChildren = 0;
      articulationPointAndBridge(i);
      articulation_vertex[dfsRoot] = ( rootChildren > 1 );
    }
  }
  
  //printf("Articulation Points:\n");
  //rep(i,V) if( articulation_vertex[i] ) printf("Vertex %d\n",i);
}

int par[MAX_V];

int find(int x){
  if( x == par[x] ) return x;
  return par[x] = find(par[x]);
}

void unit(int x,int y){
  x = find(x), y = find(y);
  if( x != y ) par[x] = y;
}


void compute(vector<Edge> edges){
  set<int> weights;
  rep(i,V) par[i] = i;
  sort(edges.begin(),edges.end());
  rep(i,E){
    Edge &e = edges[i];
    if( find(e.src) != find(e.dst) ) {
      unit(e.src,e.dst);
      weights.insert(e.w);
    }
  }
  int cnt=0,sum=0;
  int cur = 0;
  for(set<int>::iterator it=weights.begin();it!=weights.end();it++){
    int w = *it;
    while( cur < E && edges[cur].w < w ) ++cur;
    if( cur >= E ) break;
    if( edges[cur].w > w ) continue;
    base_weight = w;
    while( cur < E && edges[cur].w == w ) {
      Edge &e = edges[cur++];
      G[e.src].push_back((Edge){e.src,e.dst,e.w});
      G[e.dst].push_back((Edge){e.dst,e.src,e.w});
    }
    bridges.clear();
    calculateArticulationPointAndBridge();
    cnt += (int)bridges.size();
    sum += (int)bridges.size() * w;
  }
  printf("%d %d\n",cnt,sum);
}

int main(){
  memset(cost,-1,sizeof(cost));
  vector<Edge> edges;
  scanf("%d %d",&V,&E);
  {
    int s,t,w;
    rep(i,E){
      scanf(" %d %d %d",&s,&t,&w);
      --s, --t;
      edges.push_back((Edge){s,t,w});
      cost[s][t] = cost[t][s] = w;
    }
  }
  compute(edges);
  return 0;
}