AOJ 1055 Huge Family

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1055&lang=jp

最初意味を把握するのに手間取りました。

サンプルを書き下して察するに、無向で環状になったグラフがいくつか出来る。それぞれのグラフで連絡網を全体の費用が最小になるように構成するとき、費用が最大の枝を1つ削れば良い。ここで、それぞれのグラフについて費用が最大の枝の個数通り削り方があるので、それを全てかけてmodをとれば良い。

すんなり書けたのでそれなりに満足。

int un[100000];

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

int unit(int a,int b){
  un[find(a)]=un[find(b)]=find(a);
}

int b[100000][2];

main(){
  int n;
  while(cin>>n,n){
    rep(i,n)un[i]=i;
    rep(i,n){
      rep(j,2){
	int k;
	cin>>k>>b[i][j];
	unit(i,k);
      }
    }
    map<int,set<int> > group;
    rep(i,n)group[find(i)].insert(i);
    int ans=1;
    FOR(miter,group){
      map<int,int> app;
      FOR(siter,miter->S){
	app[-b[*siter][0]]++;
	app[-b[*siter][1]]++;
      }
      ans=ans*(app.begin()->S/2)%10007;
    }
    cout<<ans<<endl;
  }
}