NC205490. 一章
描述
也许是由于过于疲惫,不幸追尾了一辆黑色高级轿车。为了保护后备而担下所有责任的三浦,车主,暴力团员谷冈所提出的和解条件是...
输入描述
输入两个整数 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)); } }