Codeforces 60 C Mushroom Strife

問題

無向グラフの頂点に自然数が書かれている。
無向グラフのいくつかの頂点間のGCDおよびLCMが与えられる。


このとき、無向グラフの頂点に書かれた自然数の組を、一つ出力せよ。
存在しない場合はNOを出力せよ。

制約条件

頂点≦100
頂点に書かれている数≦10^6

方針

一つの頂点の値を決め付けて全探索。
一つの頂点の値を決めれば、連結成分については全て頂点の数字が求まるので、
求めてそれが与えられた条件に矛盾していないかチェックする。


これを全ての連結成分について行えばよい。

ソースコード

int n,m;
int g[100][100],l[100][100];
int ans[100],v[100],mark;

bool dfs(int c){
	v[c]=mark;
	rep(i,n)if(g[c][i]){
		if(l[c][i]%g[c][i])return 0;
		if(v[i]==mark){
			if((ll)l[c][i]*g[c][i]/ans[c]!=ans[i])return 0;
		}
		else{
			ans[i]=(ll)l[c][i]*g[c][i]/ans[c];
			int gcd=__gcd(ans[i],ans[c]), lcm=(ll)ans[i]*ans[c]/gcd;
			if(gcd!=g[c][i]||lcm!=l[c][i]||!dfs(i))return 0;
		}
	}
	return 1;
}

void run()
{
	memset(g,0,sizeof(g)); memset(l,0,sizeof(l));
	memset(ans,0,sizeof(ans));
	mark=0;
	
	cin>>n>>m;
	rep(i,m){
		int a,b,gcd,lcm; cin>>a>>b>>gcd>>lcm;
		a--; b--;
		g[a][b]=g[b][a]=gcd;
		l[a][b]=l[b][a]=lcm;
	}
	rep(i,n)if(!ans[i]){
		int j;
		for(j=1;j<=1000000;j++){
			mark++;
			ans[i]=j;
			if(dfs(i))break;
		}
		if(j>1000000){
			cout<<"NO"<<endl; return;
		}
	}
	cout<<"YES"<<endl;
	rep(i,n)cout<<ans[i]<<(i==n-1?"\n":" ");
}