この問題名、AYBABTUと関係あるのかな。ちょっと離れてるかな。
https://yukicoder.me/problems/no/1571
問題
正整数N・整数Tが与えられる。
N頂点の完全無向グラフにおいて、各辺に非負整数のコストを割り当てる。
全頂点を1回ずつたどる閉路において、常にコストの総和がTとなるものを構築せよ。
解法
N,Tの値で分類する。
- Tが偶数の場合
- 頂点1から延びる辺のコストをT/2にすればよい。
- Tが奇数の場合
- Nが3の時、どこか1辺をコストTにすればよい。
- Nが偶数の時解なし。
- 以下、Nが5,7の例を考える。
- T=1の時解なし。
- Tが3以上の場合、T=3のケースを解いたうえで、頂点1から延びる辺のコストに(T-3)/2を追加すればよい。
- T=3の場合は総当たりしてよい。
int N,T; int Q; void solve() { int i,j,k,l,r,x,y; string s; cin>>Q; while(Q--) { cin>>N>>T; if(N==3) { cout<<"Yes"<<endl; for(x=1;x<=N;x++) { for(y=x+1;y<=N;y++) { if(x==1&&y==2) cout<<x<<" "<<y<<" "<<T<<endl; else cout<<x<<" "<<y<<" "<<0<<endl; } } } else if(T%2==0) { cout<<"Yes"<<endl; for(x=1;x<=N;x++) { for(y=x+1;y<=N;y++) { if(x==1) cout<<x<<" "<<y<<" "<<T/2<<endl; else cout<<x<<" "<<y<<" "<<0<<endl; } } } else if(N%2==0 || T==1) { cout<<"No"<<endl; } else if(T>=5) { cout<<"Yes"<<endl; for(x=1;x<=N;x++) { for(y=x+1;y<=N;y++) { if(x==1) cout<<x<<" "<<y<<" "<<(T-N+2)/2<<endl; else cout<<x<<" "<<y<<" "<<1<<endl; } } } else if(N==5) { cout<<"Yes"<<endl; for(x=1;x<=N;x++) { for(y=x+1;y<=N;y++) { if(x==1) cout<<x<<" "<<y<<" "<<0<<endl; else cout<<x<<" "<<y<<" "<<1<<endl; } } } else { cout<<"No"<<endl; } } }
まとめ
短い時間で詰め切るのしんどそう。