牛客挑战赛41 B 一章
一章
https://ac.nowcoder.com/acm/contest/6012/B
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; }