【XSY2774】学习 带花树

时间:2022-06-01 19:33:28

题目描述

  给你一个图,求最大匹配。

  边的描述方式很特殊,就是一次告诉你\(c_i\)个点:\(d_1,d_2,\ldots,d_{c_i}\),表示这些点两两之间都有连边,也就是说,这是一个团。总共有\(m\)个团。

  记\(s=\sum_{i=1}^mc_i\)。

  \(n,m,s\leq 3000\)

题解

  直接跑带花树的话时间复杂度是\(O(ns^2\alpha(n))\)的,显然会TLE。

  假设每个\(c_i\)都是偶数(如果是奇数就让最后一个点像前面的点连边,然后把这个点去掉)。

  对于每一个团,添加\(k=c_i\)个辅助点,按以下方式连边(红色的为原来的店,蓝色的为辅助点):

  【XSY2774】学习 带花树

  易证有\(x\)个红色点和蓝色点匹配时,最大匹配是\(\lfloor\frac{x+k}{2}\rfloor\)。

  (可以先选一个红色点匹配,然后顺时针确定其他红色点,对这个红色点相邻的蓝色点到上一个红色点相邻的蓝色点之间蓝色点个数分类讨论来决定这个红色点连向那个蓝色点。)

  对于每个团,令\(k\)为偶数,然后在跑完带花树后把答案减掉\(\sum k/2\)。

  这样建图的边的个数是\(O(s)\)的。

  时间复杂度:\(O(ns\alpha(n))\)

  (显然\(O(n\alpha(n))\)的并查集常数很大会被卡常。)

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<utility>
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
int rd()
{
int s=0,c;
while((c=getchar())<'0'||c>'9');
s=c-'0';
while((c=getchar())>='0'&&c<='9')
s=s*10+c-'0';
return s;
}
void open(const char *s)
{
#ifndef ONLINE_JUDGE
char str[100];
sprintf(str,"%s.in",s);
freopen(str,"r",stdin);
sprintf(str,"%s.out",s);
freopen(str,"w",stdout);
#endif
}
struct graph
{
int h[6010];
int v[10000010];
int t[10000010];
int n;
void clear()
{
memset(h,0,sizeof h);
n=0;
}
void add(int x,int y)
{
n++;
v[n]=y;
t[n]=h[x];
h[x]=n;
}
};
graph g;
int n,m;
int ans;
int c[6010];
int f[6010];
int find(int x)
{
return f[x]==x?x:f[x]=find(f[x]);
}
int link[6010];
int d[6010];
int b[6010];
int q[6010];
int pre[6010];
int head,tail;
void aug(int x)
{
for(int y=pre[x];x;x=pre[y],y=pre[x])
{
link[x]=y;
pre[y]=link[y];
link[y]=x;
}
}
int vis[6010];
int ti=0;
int getlca(int x,int y)
{
ti++;
for(x=find(x),y=find(y);;swap(x,y))
if(x)
{
if(vis[x]==ti)
return x;
vis[x]=ti;
x=find(pre[link[x]]);
}
return 0;
}
void gao(int x,int y,int lca)
{
for(;find(x)!=lca;x=pre[y])
{
pre[x]=y;
y=link[x];
f[x]=lca;
f[y]=lca;
if(d[y])
{
d[y]=0;
q[++tail]=y;
}
}
}
int num;
int bfs(int x)
{
memset(b,0,sizeof b);
for(int i=1;i<=num;i++)
f[i]=i;
head=1,tail=0;
d[x]=0;
b[x]=1;
q[++tail]=x;
int v;
while(tail>=head)
{
x=q[head++];
for(int i=g.h[x];i;i=g.t[i])
if(find(v=g.v[i])==find(x))
continue;
else
{
if(!b[v])
{
pre[v]=x;
b[v]=1;
if(!link[v])
{
aug(v);
return 1;
}
else
{
b[link[v]]=1;
d[v]=1;
d[link[v]]=0;
q[++tail]=link[v];
}
}
else
{
if(!d[v])
{
int lca=getlca(x,v);
gao(x,v,lca);
gao(v,x,lca);
}
}
}
}
return 0;
}
void solve()
{
num=n;
g.clear();
int x,y;
ans=0;
for(int i=1;i<=m;i++)
{
scanf("%d",&x);
for(int j=1;j<=x;j++)
scanf("%d",&c[j]);
sort(c+1,c+x+1);
x=unique(c+1,c+x+1)-c-1;
if(x&1)
{
for(int j=1;j<x;j++)
{
g.add(c[j],c[x]);
g.add(c[x],c[j]);
}
x--;
}
for(int j=1;j<=x;j++)
{
g.add(num+j,num+j%x+1);
g.add(num+j%x+1,num+j);
}
for(int j=1;j<=x;j++)
{
g.add(c[j],num+j);
g.add(num+j,c[j]);
g.add(c[j],num+j%x+1);
g.add(num+j%x+1,c[j]);
}
ans-=x/2;
num+=x;
}
memset(link,0,sizeof link);
for(int i=1;i<=num;i++)
if(!link[i])
{
if(bfs(i))
ans++;
}
printf("%d\n",ans);
}
int main()
{
open("c");
while(~scanf("%d%d",&n,&m)&&(n||m))
solve();
return 0;
}

【XSY2774】学习 带花树的更多相关文章

  1. URAL 1099&period; Work Scheduling (一般图匹配带花树)

    1099. Work Scheduling Time limit: 0.5 secondMemory limit: 64 MB There is certain amount of night gua ...

  2. HDU 4687 Boke and Tsukkomi (一般图匹配带花树)

    Boke and Tsukkomi Time Limit: 3000/3000 MS (Java/Others)    Memory Limit: 102400/102400 K (Java/Othe ...

  3. P6113-&lbrack;模板&rsqb;一般图最大匹配【带花树】

    正题 题目链接:https://www.luogu.com.cn/problem/P6113 题目大意 给出一张无向图,求最大匹配. \(1\leq n\leq 10^3,1\leq m\leq 5\ ...

  4. &lbrack;转&rsqb;带花树&comma;Edmonds&&num;39&semi;s matching algorithm&comma;一般图最大匹配

    看了两篇博客,觉得写得不错,便收藏之.. 首先是第一篇,转自某Final牛 带花树……其实这个算法很容易理解,但是实现起来非常奇葩(至少对我而言). 除了wiki和amber的程序我找到的资料看着都不 ...

  5. HDOJ 4687 Boke and Tsukkomi 一般图最大匹配带花树&plus;暴力

    一般图最大匹配带花树+暴力: 先算最大匹配 C1 在枚举每一条边,去掉和这条边两个端点有关的边.....再跑Edmonds得到匹配C2 假设C2+2==C1则这条边再某个最大匹配中 Boke and ...

  6. 【Learning】带花树——一般图最大匹配

    一般图最大匹配--带花树 问题 ​ 给定一个图,求该图的最大匹配.即找到最多的边,使得每个点至多属于一条边. ​ 这个问题的退化版本就是二分图最大匹配. ​ 由于二分图中不存在奇环,偶环对最大匹配并无 ...

  7. 【learning】一般图最大匹配——带花树

    问题描述 ​ 对于一个图\(G(V,E)\),当点对集\(S\)满足任意\((u,v)\in S\),均有\(u,v\in V,(u,v)\in E\),且\(S\)中没有点重复出现,我们称\(S\) ...

  8. &lbrack;BZOJ&rsqb;4405&colon; &lbrack;wc2016&rsqb;挑战NPC(带花树)

    带花树模板 #include<cstdio> #include<cstring> #include<algorithm> using namespace std; ...

  9. HDU 4687 Boke and Tsukkomi &lpar;一般图最大匹配&rpar;【带花树】

    <题目链接> 题目大意: 给你n个点和m条边,每条边代表两点具有匹配关系,问你有多少对匹配是冗余的. 解题分析: 所谓不冗余,自然就是这对匹配关系处于最大匹配中,即该匹配关系有意义.那怎样 ...

随机推荐

  1. HTML5学习之拖放(十)

    l元素可以用于拖拽必须设置draggable="true"属性,img和a标签除外,她们两个默认就可以被拖拽 想做拖拽处理,就需要在Dom元素上监听拖放的事件:dragstart, ...

  2. &lbrack;设计模式&rsqb; javascript 之 工厂方法模式

    1. 简单工厂模式 说明:就是创建一个工厂类,里面实现了所对同一个接口的实现类的创建. 但是好像JavaScript 好像没有 接口 这号东西,所以我们去掉接口这个层; 当然,我们这里的 实现类 下的 ...

  3. 免费的HTML5连载来了《HTML5网页开发实例详解》连载(三)DOCTYPE和字符集

    在2.1.2节中通过新老DOCTYPE的对比,读者可以清晰地看到HTML 5在精简旧有结构上做出的努力.DOCTYPE在出现之初主要用于XML中,用作描述XML允许使用的元素.属性和排列方式.起初HT ...

  4. 做10年Windows程序员与做10年Linux程序员的区别(附无数评论)(开源软件相当于熟读唐诗三百首,不会作诗也会吟)

    如果一个程序员从来没有在linux,unix下开发过程序,一直在windows下面开发程序, 同样是工作10年, 大部分情况下与在linux,unix下面开发10年的程序员水平会差别很大.我写这篇文章 ...

  5. angular&period;run和angular&period;config的区别

    ng的运行机制: config阶段是给了ng上下文一个针对constant与provider修改其内部属性的一个阶段 而run阶段是在config之后的在运行独立的代码块,通常写法runBlock 简 ...

  6. sqlmap Windows 安装教程

    第一步:下载 python :https://www.python.org/downloads/    (这里有python各种版本,但是一般建议安装3和2.7) sqlmap:https://git ...

  7. JGit 切换分支

    //gitDir是git仓库的根目录,这个仓库必须是已clone好了 File file = new File(gitDir); Git git = Git.open(file); //切换分支, i ...

  8. org&period;apache&period;ibatis&period;reflection&period;ReflectionException&colon; There is no getter for property named 'list' in 'c

     org.apache.ibatis.reflection.ReflectionException: There is no getter for property named 'list' in ' ...

  9. IDA修改游戏

    用GM找到机器码 基址   400000 偏移是401940-400000 = 0x1940 UE去到D40位置修改

  10. MFC学习单选框Radio使用

    创建单选框Radio ,ID号IDC_RADIO_NAME 1.获取单选框内容 int RadioState = ((CButton *)GetDlgItem(IDC_RADIO_NAME))-&gt ...