傳送門

文章目錄

• 題意
• 思路：

題意

思路：

這個題很容易就會掉到二分圖匹配的坑里。。
但實際上這個是一個一般圖匹配。
考慮將妹子拆點，一個入點一個出點，入點出點都連蝴蝶結(jié)。
我們看看最終會有三種匹配情況：
$(1)$妹子自身匹配，匹配數(shù)$+1$。
$(2)$一個妹子的出點或入點其中一個和蝴蝶結(jié)匹配，匹配數(shù)$+1$。
$(3)$一個妹子的出點和入點都和蝴蝶結(jié)匹配，匹配數(shù)$+2$。
可以發(fā)現(xiàn)，最終有貢獻(xiàn)的只有$(3)$，所以求一個最大匹配讓后減去$n$即可。

// Problem: 清楚姐姐的翅膀們 // Contest: NowCoder // URL: https://ac.nowcoder.com/acm/contest/18962/F?&headNav=acm // Memory Limit: 1048576 MB // Time Limit: 10000 ms // // Powered by CP Editor (https://cpeditor.org)//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math") //#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native") //#pragma GCC optimize(2) #include<cstdio> #include<iostream> #include<string> #include<cstring> #include<map> #include<cmath> #include<cctype> #include<vector> #include<set> #include<queue> #include<algorithm> #include<sstream> #include<ctime> #include<cstdlib> #include<random> #include<chrono> #include<cassert> #define X first #define Y second #define L (u<<1) #define R (u<<1|1) #define pb push_back #define mk make_pair #define Mid ((tr[u].l+tr[u].r)>>1) #define Len(u) (tr[u].r-tr[u].l+1) #define random(a,b) ((a)+rand()%((b)-(a)+1)) #define db puts("---") using namespace std;//void rd_cre() { freopen("d://dp//data.txt","w",stdout); srand(time(NULL)); } //void rd_ac() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//AC.txt","w",stdout); } //void rd_wa() { freopen("d://dp//data.txt","r",stdin); freopen("d://dp//WA.txt","w",stdout); }typedef long long LL; typedef unsigned long long ULL; typedef pair<int,int> PII;const int N=1000010,mod=1e9+7,INF=0x3f3f3f3f; const double eps=1e-6;template <typename T> class graph {public:struct edge {int from;int to;T cost;};vector<edge> edges;vector<vector<int> > g;int n;graph(int _n) : n(_n) { g.resize(n); }virtual int add(int from, int to, T cost) = 0; };// undirectedgraph template <typename T> class undirectedgraph : public graph<T> {public:using graph<T>::edges;using graph<T>::g;using graph<T>::n;undirectedgraph(int _n) : graph<T>(_n) {}int add(int from, int to, T cost = 1) {assert(0 <= from && from < n && 0 <= to && to < n);int id = (int)edges.size();g[from].push_back(id);g[to].push_back(id);edges.push_back({from, to, cost});return id;} };// blossom / find_max_unweighted_matching template <typename T> vector<int> find_max_unweighted_matching(const undirectedgraph<T> &g) {std::mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());vector<int> match(g.n, -1); // 匹配vector<int> aux(g.n, -1); // 時間戳記vector<int> label(g.n); // "o" or "i"vector<int> orig(g.n); // 花根vector<int> parent(g.n, -1); // 父節(jié)點queue<int> q;int aux_time = -1;auto lca = [&](int v, int u) {aux_time++;while (true) {if (v != -1) {if (aux[v] == aux_time) { // 找到拜訪過的點 也就是LCAreturn v;}aux[v] = aux_time;if (match[v] == -1) {v = -1;} else {v = orig[parent[match[v]]]; // 以匹配點的父節(jié)點繼續(xù)尋找}}swap(v, u);}}; // lcaauto blossom = [&](int v, int u, int a) {while (orig[v] != a) {parent[v] = u;u = match[v];if (label[u] == 1) { // 初始點設(shè)為"o" 找增廣路label[u] = 0;q.push(u);}orig[v] = orig[u] = a; // 縮花v = parent[u];}}; // blossomauto augment = [&](int v) {while (v != -1) {int pv = parent[v];int next_v = match[pv];match[v] = pv;match[pv] = v;v = next_v;}}; // augmentauto bfs = [&](int root) {fill(label.begin(), label.end(), -1);iota(orig.begin(), orig.end(), 0);while (!q.empty()) {q.pop();}q.push(root);// 初始點設(shè)為 "o", 這里以"0"代替"o", "1"代替"i"label[root] = 0;while (!q.empty()) {int v = q.front();q.pop();for (int id : g.g[v]) {auto &e = g.edges[id];int u = e.from ^ e.to ^ v;if (label[u] == -1) { // 找到未拜訪點label[u] = 1; // 標(biāo)記 "i"parent[u] = v;if (match[u] == -1) { // 找到未匹配點augment(u); // 尋找增廣路徑return true;}// 找到已匹配點 將與她匹配的點丟入queue 延伸交錯樹label[match[u]] = 0;q.push(match[u]);continue;} else if (label[u] == 0 && orig[v] != orig[u]) {// 找到已拜訪點 且標(biāo)記同為"o" 代表找到"花"int a = lca(orig[v], orig[u]);// 找LCA 然后縮花blossom(u, v, a);blossom(v, u, a);}}}return false;}; // bfsauto greedy = [&]() {vector<int> order(g.n);// 隨機(jī)打亂 orderiota(order.begin(), order.end(), 0);shuffle(order.begin(), order.end(), rng);// 將可以匹配的點匹配for (int i : order) {if (match[i] == -1) {for (auto id : g.g[i]) {auto &e = g.edges[id];int to = e.from ^ e.to ^ i;if (match[to] == -1) {match[i] = to;match[to] = i;break;}}}}}; // greedy// 一開始先隨機(jī)匹配greedy();// 對未匹配點找增廣路for (int i = 0; i < g.n; i++) {if (match[i] == -1) {bfs(i);}}return match; }int main() {ios::sync_with_stdio(0), cin.tie(0);int _; cin>>_;while(_--) {int n,m; cin>>n>>m;undirectedgraph<int>g(n*2+m);for(int i=0;i<n;i++) {g.add(i,i+n,1);int c; cin>>c;while(c--) {int x; cin>>x;x--;g.add(i,2*n+x);g.add(i+n,2*n+x);}}auto blossom_match = find_max_unweighted_matching(g);int ans=0;for(int i=0;i<blossom_match.size();i++) {if(blossom_match[i]!=-1) ans++;}cout<<ans/2-n<<endl;} }

總結(jié)

以上是生活随笔為你收集整理的nowcoder 清楚姐姐的翅膀们 F 一般图的最大匹配的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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