Bigraph Extension

題意：

有2n個(gè)點(diǎn)，n為偶數(shù)，n個(gè)點(diǎn)屬于集合A，n個(gè)點(diǎn)屬于集合B。起初在途中有m個(gè)無(wú)向邊，邊的兩側(cè)端點(diǎn)分別在兩個(gè)集合里，任何兩個(gè)邊都沒(méi)有公共交點(diǎn)。
現(xiàn)在你可以執(zhí)行任意次操作：
在集合A，B中分別選一個(gè)點(diǎn)，這兩個(gè)點(diǎn)沒(méi)有直接的邊相連，現(xiàn)在給這兩個(gè)點(diǎn)相連

在操作之后，對(duì)于集合A中任意一個(gè)點(diǎn)，集合B中任意一個(gè)點(diǎn)，需要滿足：
這兩個(gè)點(diǎn)是聯(lián)通的
這兩個(gè)點(diǎn)的最長(zhǎng)簡(jiǎn)單路徑是嚴(yán)格大于n的
問(wèn)最少的加邊數(shù)量，并按照最小字典序輸出連邊方案

題解：

構(gòu)造題，不過(guò)這個(gè)題的結(jié)論其實(shí)好猜，具體證明就麻煩些
其實(shí)就是將2n個(gè)點(diǎn)構(gòu)造成環(huán)，現(xiàn)在已經(jīng)有了m個(gè)點(diǎn)，最小加邊數(shù)就是2n-m
我們先不考慮環(huán)，先考慮將所有點(diǎn)連通
然后就是考慮字典序的最小限制，那我們就從小到達(dá)枚舉集合A中的點(diǎn)，再?gòu)男〉酱竺杜eB中的點(diǎn)，通過(guò)維護(hù)并查集和度數(shù)數(shù)組來(lái)判斷兩個(gè)點(diǎn)是否連成鏈。這樣就保證前2n-m-1條邊的字典序最小。現(xiàn)在所有點(diǎn)已經(jīng)聯(lián)通了，不過(guò)還缺一個(gè)邊，我們需要再加入一個(gè)邊形成環(huán)，我們遍歷A，B中度數(shù)為1的點(diǎn)連起來(lái)，放在第2n-m條邊的位置
官方題解的詳細(xì)證明：

代碼：

#pragma GCC diagnostic error "-std=c++11" #include <algorithm> #include <cmath> #include <cstdio> #include <cstring> #include <ctime> #include <iostream> #include <map> #include <queue> #include <set> #include <stack> #include <unordered_map> #define iss ios::sync_with_stdio(false) using namespace std; typedef unsigned long long ull; typedef long long ll; typedef pair<int, int> pii; const int mod = 1e9 + 7; const int MAXN = 2e5 + 5; const int inf = 0x3f3f3f3f; int fa[MAXN]; int in[MAXN]; vector<pii> ans; priority_queue<int, vector<int>, greater<int>> q;//最小堆 void init(int n) {for (int i = 1; i <= 2 * n; i++) {fa[i] = i;in[i] = 0;} } int find(int x) {if (fa[x] == x)return x;elsereturn fa[x] = find(fa[x]); } void combine(int u, int v) {u = find(u);v = find(v);fa[u] = v; } int main() {int t;scanf("%d", &t);while (t--) {ans.clear();int n, m;scanf("%d%d", &n, &m);init(n);for (int i = 1; i <= m; i++) {int u, v;scanf("%d%d", &u, &v);v += n;combine(u, v);in[u]++;in[v]++;}for (int i = n + 1; i <= 2 * n; i++)q.push(i);for (int i = 1; i <= n; i++) {queue<int> st;while (in[i] < 2 && !q.empty()) {int j = q.top();q.pop();if (find(j) != find(i)) {combine(i, j);in[i]++;in[j]++;ans.push_back({ i, j });}st.push(j);}while (!st.empty()) {int j = st.front();st.pop();if (in[j] < 2)q.push(j);}}int flag = 0, p1 = 0, p2 = 0;for (int i = 1; i <= n; i++) {if (in[i] == 1){p1 = i;break;}}for (int i = n + 1; i <= 2 * n; i++) {if (in[i] == 1){p2 = i;break;}}if(p1!=0&&p2!=0) {ans.push_back({ p1, p2 }); // printf("組成環(huán)：p1=%d,p2=%d\n",p1,p2-n); }if (flag) {printf("-1\n");} else {printf("%d\n", ans.size());for (auto i : ans) {printf("%d %d\n", i.first, i.second - n);}}while (!q.empty())q.pop();} }

總結(jié)

以上是生活随笔為你收集整理的Bigraph Extension的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。