生成树与路径

NC248198. 生成树与路径

描述

给定 $n,m$ ，请构造一个 $n$ 点 $m$ 边的无向带权连通图，没有自环和重边，满足该图的最小生成树大小（生成树的边权和）等于节点 $1$ 到节点 $n$ 的最短路长度（路径的边权和）。

并限定所有边权是 $1\to m$ 的排列。（即分配边权时 $1\to m$ 中的每个数字只能用一次）

可以证明，对于任意满足本题数据范围的 $n,m$ ，均存在解。

输入描述

多组数据，第一行输入一个正整数 ，表示数据的组数。

对于每组数据，一行输入两个整数 ，以空格相隔。

对于  组数据，保证 。

输出描述

对于每组数据：输出  行，第  行输出三个正整数  以空格相隔，表示节点  与节点  存在一条边权为  的连边。

若有多组方案，输出任意一组方案均可。

示例1

输入:

2
3 2
3 3

输出:

说明:

样例的两组测试数据的输出对应的图如下图所示。

原站题解

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

pypy3 解法, 执行用时: 476ms, 内存消耗: 33040K, 提交时间: 2023-02-11 10:21:09

T=int(input())
def solve():
    n,m=map(int,input().split())
    s=0
    count=1
    while s<=m:
        for i in range(1,n+1-count):
            s+=1
            # print(s)
            if s>m:
                return
            print(i,i+count,s)
        if s==m:
            return
        count+=1
while T:
    solve()
    T-=1

C++(clang++ 11.0.1) 解法, 执行用时: 720ms, 内存消耗: 6136K, 提交时间: 2023-02-10 22:19:03

#include<iostream>
using namespace std;

int main(){
	int T;
	cin>>T;
	while(T--){
		int n,m;
		cin>>n>>m;
		for(int j=1,i=1;j<=n-1;j++){
			for(int k=1;k+j<=n&&i<=m;k++,i++){
				cout<<k<<' '<<k+j<<' '<<i<<endl;
			}
		}
	}
	return 0;
}

上一题

下一题

详情