牛客挑战赛41 B 一章

一章

https://ac.nowcoder.com/acm/contest/6012/B

B 一章

题目地址:

https://ac.nowcoder.com/acm/contest/6012/B

基本思路:

分情况构造,我们先想如何在不制造出割边的情况下制造出割点,和在不制造出割点的情况下制造出割边。

在不制造出割边的情况下制造出割点,我们考虑让割点出现在两个三元环之间,也就是下面这个情况。

图片说明

在不制造出割点的情况下制造出割边,我们尝试一下在割边只有一条的情况里是可以出现的,也就是两个点直接相连的情况。但是其余情况下,我们发现要出现割边,至少会生成一个割点,也就是下面的情况。
图片说明

那么在既有割点又有割边的情况里我们就能这样构造。

图片说明

然后再将上面推断中的几种特殊情况判断一下就行了。

#pragma GCC optimize(2)
#pragma GCC optimize(3)
#include <bits/stdc++.h>
using namespace std;
#define IO std::ios::sync_with_stdio(false)
#define int long long
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define per(i, l, r) for (int i = l; i >= r; i--)
#define mset(s, _) memset(s, _, sizeof(s))
#define pb push_back
#define pii pair <int, int>
#define mp(a, b) make_pair(a, b)
#define INF (int)1e18

inline int read() {
  int x = 0, neg = 1; char op = getchar();
  while (!isdigit(op)) { if (op == '-') neg = -1; op = getchar(); }
  while (isdigit(op)) { x = 10 * x + op - '0'; op = getchar(); }
  return neg * x;
}
inline void print(int x) {
  if (x < 0) { putchar('-'); x = -x; }
  if (x >= 10) print(x / 10);
  putchar(x % 10 + '0');
}

set<pii> ans;
int a,b;
signed main() {
  IO;
  cin >> a >> b;
  if(a == 0 && b == 1){//一条割边的情况能不产生割点;
    cout << 2 << ' ' << 1 << '\n';
    cout << 1 << ' ' << 2 << '\n';
    return 0;
  }
  if(b > 0) a--; //给割边在的那个位置预留一个割点;
  if(a < 0){ //两个以上割边,至少要存在一个割点;
    cout << -1 << '\n';
    return 0;
  }
  //剩下就是先构造三元环再和1点连出割边就是了;
  ans.clear();
  int now = 1;
  for (now = 2 ; now <= a + 2 ; now++) ans.insert({now-1,now});
  for(int i = 0 ; i < a + 1 ; i++) {
    ans.insert({now, now - (a + 1)});
    ans.insert({now, now - (a + 2)});
    now++;
  }
  for(int i = 0 ; i < b ; i++){
    ans.insert({1,now});
    now++;
  }
  cout << now - 1 << ' ' << ans.size() << '\n';
  for(auto it : ans){
    cout << it.first << ' ' << it.second << '\n';
  }
  return 0;
}
全部评论

相关推荐

我是小红是我:学校换成中南
点赞 评论 收藏
分享
10-24 13:36
门头沟学院 Java
Zzzzoooo:更新:今天下午有hr联系我去不去客户端,拒了
点赞 评论 收藏
分享
评论
1
收藏
分享
牛客网
牛客企业服务