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":" "); }