UTPC 2011 F: 全域木
問題概要
ノード数Nの完全グラフから、K種類の互いに辺を共有しない全域木を構成する問題。
解法
解説を参考にして実装した。円上にノードを配置してぐるぐる回すという方法で、様々な作り方があるらしい。
#include <cstdio> using namespace std; int N, K; void solve(){ for(int st=0; st<K; st++){ int cur = 0; for(int i=0; i<N-1; i++){ int next = (cur>N/2?N-cur:N-cur-1); printf("%d %d\n", (cur+st)%N+1, (next+st)%N+1); cur = next; } puts(""); } } int main(){ scanf("%d%d",&N,&K); if(K > N/2){ puts("-1"); return 0; } solve(); return 0; }