Problem 1055 : Huge Family

問題概要

日本語なので本文参照……
なのだがUAPC本番中は本文を読んでもよくわからなかった。

全ての頂点の次数が2の、重み付き単純グラフGが与えられる。

このグラフの部分グラフSで以下のようなものを考える。

• Gで連結だった部分はSでも連結
• そのようなグラフの中でSの重みの和は最小

Sの場合の数をmod10007で求めよ。

解法

条件から元のグラフは小さいループが何個かできたものしかありえない。

Sは、一つのループにつき重みが最大の辺を除去してできるグラフであるから、
ループごとに重さ最大の辺が（1位タイの辺）が何個あるかを数えて、かければよい。

ソースコード

int mod=10007;
int n,e[100000][2],w[100000][2];
bool v[100000];

int mx,mxn;
void rec(int c)
{
	v[c]=1;
	rep(i,2)
	{
		if(mx<w[c][i])mx=w[c][i],mxn=0;
		if(mx==w[c][i])mxn++;
		
		if(!v[e[c][i]])rec(e[c][i]);
	}
}
int main()
{
	while(scanf("%d",&n),n)
	{
		rep(i,n)rep(j,2)scanf("%d%d",e[i]+j,w[i]+j);
		int ans=1;
		rep(i,n)v[i]=0;
		rep(i,n)if(!v[i])
		{
			mx=0; mxn=1;
			rec(i);
			ans=(ans*mxn/2)%mod;
		}
		printf("%d\n",ans);
	}
	return 0;
}