列表

详情

NC202122. Spanning Tree Removal

描述

Bob has recently learned algorithms on finding spanning trees and wanted to give you a quiz.

To recap, a spanning tree is a subset of graph , which has all the vertices covered with minimum possible number of edges. Hence, a spanning tree does not have cycles and it cannot be disconnected. Given an arbitrary undirected simple graph (without multiple edges and loops), a spanning tree removal is defined as: retrieve one spanning tree of the graph, and remove all the edges selected by the spanning tree from the original graph, obtaining a new graph.

Bob found "spanning tree removal'' so fun that he wanted to do it over and over again. In particular, he began with a complete graph, i.e., a graph with every pair of distinct vertices connected by a unique edge. Your goal, is to smartly choose spanning trees to remove so that you can repeat as many times as possible until there is no longer a spanning tree in the graph.

输入描述

The input file starts with an integer  (), denoting the number of test cases.
Each test case is one line:  (), which the number of vertices of the graph to begin with.
The sum of  over all test cases in a single input does not exceed .

输出描述

For each test case, output one line containing "Case #x: y", where x is the test case number starting from 1, and y is how many times at most you can do the removal.
Then follows  lines. From line  to line , you should print a spanning tree you decided to remove at i-th time, in the format that everyone should be familiar with. Namely, each line contains two numbers u and v (, ). (u, v) should be valid tree edge, and does not coincide with edges that have been removed before. If there are several solutions, output any of them.

示例1

输入: 

3
2
3
4

输出: 

Case #1: 1
1 2
Case #2: 1
3 1
1 2
Case #3: 2
1 3
3 4
2 4
3 2
1 4
2 1

原站题解

上次编辑到这里，代码来自缓存 点击恢复默认模板

C++14(g++5.4) 解法, 执行用时: 91ms, 内存消耗: 4320K, 提交时间: 2020-03-04 21:15:00 

#include <bits/stdc++.h>
using namespace std;

int main() {
	int t;
	cin >> t;
	for (int cas = 1; cas <= t; ++cas) {
		int n; 
		cin >> n;
		printf("Case #%d: %d\n", cas, n / 2);
		for (int i = 0; i < n / 2; ++i) {
			for (int j = 1, f = 1, x = i; j <= n - 1; ++j, f = -f) {
				int y = (x + j * f + n) % n;
				cout << x + 1 << " " << y + 1 << "\n";
				x = y;
			}
		}
	}
	return 0;
}

C++(g++ 7.5.0) 解法, 执行用时: 109ms, 内存消耗: 4200K, 提交时间: 2023-01-12 14:42:18 

#include<bits/stdc++.h>
using namespace std;
int t;
int n;
bool vis[1005][1005];
int main(){
	ios::sync_with_stdio(0);
	cin>>t;
	int cnt=0;
	while(t--){
		cin>>n;
		cout<<"Case #"<<++cnt<<": "<<n/2<<'\n';
		for(int i=1;i<=n/2;++i){
			int k=i;
			int flg=1;
			for(int j=1;j<n;++j){
				cout<<(k+1)<<' '<<(k+flg*j+n)%n+1<<'\n';
				k=(k+flg*j+n)%n;
				flg*=-1;
			}
		}
	}
}

C++(clang++11) 解法, 执行用时: 64ms, 内存消耗: 4116K, 提交时间: 2020-11-24 17:02:22 

#include<bits/stdc++.h>
using namespace std;
int main(){
	int t,n,x,y,f;
	scanf("%d",&t);
	for(int k=1;k<=t;++k){
		scanf("%d",&n);
		int en=n/2;
		printf("Case #%d: %d\n",k,en);
		for(int i=1;i<=en;++i){
			x=i,f=1;
			for(int j=1;j<=n-1;++j){
				y=(x+f*j+n)%n;
				y=y?y:n;
				printf("%d %d\n",x,y);
				x=y,f=-f;
			}
		}
	}
}

上一题

© 2024 nowcoder.com