山西教育学会网站建设,wordpress 换数据库,百度广告平台,米拓 wordpress传送门 文章目录题意思路#xff1a;题意 思路#xff1a;
这个题很容易就会掉到二分图匹配的坑里。。 但实际上这个是一个一般图匹配。 考虑将妹子拆点#xff0c;一个入点一个出点#xff0c;入点出点都连蝴蝶结。 我们看看最终会有三种匹配情况#xff1a; (1)(1)(1)妹…传送门
文章目录题意思路题意 思路
这个题很容易就会掉到二分图匹配的坑里。。 但实际上这个是一个一般图匹配。 考虑将妹子拆点一个入点一个出点入点出点都连蝴蝶结。 我们看看最终会有三种匹配情况 (1)(1)(1)妹子自身匹配匹配数111。 (2)(2)(2)一个妹子的出点或入点其中一个和蝴蝶结匹配匹配数111。 (3)(3)(3)一个妹子的出点和入点都和蝴蝶结匹配匹配数222。 可以发现最终有贡献的只有(3)(3)(3)所以求一个最大匹配让后减去nnn即可。
// Problem: 清楚姐姐的翅膀们
// Contest: NowCoder
// URL: https://ac.nowcoder.com/acm/contest/18962/F?headNavacm
// 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,tunenative)
//#pragma GCC optimize(2)
#includecstdio
#includeiostream
#includestring
#includecstring
#includemap
#includecmath
#includecctype
#includevector
#includeset
#includequeue
#includealgorithm
#includesstream
#includectime
#includecstdlib
#includerandom
#includechrono
#includecassert
#define X first
#define Y second
#define L (u1)
#define R (u1|1)
#define pb push_back
#define mk make_pair
#define Mid ((tr[u].ltr[u].r)1)
#define Len(u) (tr[u].r-tr[u].l1)
#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 pairint,int PII;const int N1000010,mod1e97,INF0x3f3f3f3f;
const double eps1e-6;template typename T
class graph {public:struct edge {int from;int to;T cost;};vectoredge edges;vectorvectorint 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 graphT {public:using graphT::edges;using graphT::g;using graphT::n;undirectedgraph(int _n) : graphT(_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
vectorint find_max_unweighted_matching(const undirectedgraphT g) {std::mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());vectorint match(g.n, -1); // 匹配vectorint aux(g.n, -1); // 时间戳记vectorint label(g.n); // o or ivectorint orig(g.n); // 花根vectorint parent(g.n, -1); // 父节点queueint 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]]]; // 以匹配点的父节点继续寻找}}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) { // 初始点设为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);// 初始点设为 o, 这里以0代替o, 1代替ilabel[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; // 标记 iparent[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]) {// 找到已拜访点 且标记同为o 代表找到花int a lca(orig[v], orig[u]);// 找LCA 然后缩花blossom(u, v, a);blossom(v, u, a);}}}return false;}; // bfsauto greedy []() {vectorint order(g.n);// 随机打乱 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// 一开始先随机匹配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; cinnm;undirectedgraphintg(n*2m);for(int i0;in;i) {g.add(i,in,1);int c; cinc;while(c--) {int x; cinx;x--;g.add(i,2*nx);g.add(in,2*nx);}}auto blossom_match find_max_unweighted_matching(g);int ans0;for(int i0;iblossom_match.size();i) {if(blossom_match[i]!-1) ans;}coutans/2-nendl;}
}
