列表

详情


NC205490. 一章

描述

也许是由于过于疲惫,不幸追尾了一辆黑色高级轿车。为了保护后备而担下所有责任的三浦,车主,暴力团员谷冈所提出的和解条件是...

构造一张无自环、无重边的无向连通图,满足这张图有 a 个割点和 b 个桥。

割点的定义:https://baike.baidu.com/item/%E5%89%B2%E7%82%B9/9384042?fr=aladdin

桥的定义:https://baike.baidu.com/item/%E5%89%B2%E8%BE%B9/7056192?fromtitle=%E6%A1%A5&fromid=6104273#viewPageContent

输入描述

输入两个整数 a, b。

输出描述

如果无解,输出 -1;否则按照以下格式输出。
第一行两个整数 n, m。n 表示点数,m 表示边数。
接下来 m 行,输出两个整数 l, r ,表示该图中有一条连接点 l 和点 r 的边。
你的输出要满足,且
你给出的图要满足无自环、无重边、连通,且有 a 个割点和 b 个桥。

示例1

输入:

1 2

输出:

3 2
1 2
2 3

说明:

点 2 是割点,边 (1, 2)、(2, 3) 是桥。

原站题解

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

C++14(g++5.4) 解法, 执行用时: 50ms, 内存消耗: 656K, 提交时间: 2020-06-19 21:32:39

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
const int INF = 0x3f3f3f3f;
const double pi=acos(-1),eps=1e-8;
const int maxn = 1<<17;
const int mod = 1e9+7;
const int N = 1e6+10;
int main(){
	int a,b;
	cin>>a>>b;
	if(a==0&&b==1){
		cout<<2<<" "<<1<<endl;
		cout<<1<<" "<<2<<endl;
		return 0;
	}
	if(a==0&&b){
		cout<<-1<<endl;
		return 0;
	}
	
	if(b>a){
		int cnt=b-a-1,i;
		cout<<b+1<<" "<<b<<endl;
		for(i=1;i<=a+1;i++)
		cout<<i<<" "<<i+1<<endl;
		for(int j=0;j<cnt;j++){
			cout<<++i<<" "<<2<<endl;
		}
	}else{
		int cnt=a+1-b,i;
		cout<<2*a+3-b<<" "<<3*a+3-b*2<<endl;
		for(i=1;i<=a+1;i++)
		cout<<i<<" "<<i+1<<endl;
		for(int j=1;j<=cnt;j++){
			cout<<++i<<" "<<j<<endl;
			cout<<i<<" "<<j+1<<endl;
		}
	}
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 10ms, 内存消耗: 740K, 提交时间: 2020-06-19 19:35:40

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

int a,b;

int main(){
	scanf("%d %d",&a,&b);
	if(b>1 && a==0){printf("-1");return 0;}
	if(b==0){
		printf("%d %d\n",2*a+3,3*a+3);
		printf("1 2\n2 3\n1 3\n");
		for(int i=1;i<=a;i++) printf("%d %d\n%d %d\n%d %d\n",3+2*i-1,3+2*i,3+2*(i-1),3+2*i-1,3+2*(i-1),3+2*i);
	}
	else{
		printf("%d %d\n",b+1+2*a,b+3*a);
		for(int i=1;i<=b;i++) printf("%d %d\n",i,b+1);
		for(int i=1;i<=a;i++) printf("%d %d\n%d %d\n%d %d\n",b+1+2*i-1,b+1+2*i,b+1+2*i-1,b+1+2*(i-1),b+1+2*i,b+1+2*(i-1));
	}
}

上一题