BZOJ 4316: 小C的独立集 解题报告
2024-08-25 22:52:00
4316: 小C的独立集
Description
图论小王子小C经常虐菜,特别是在图论方面,经常把小D虐得很惨很惨。
这不,小C让小D去求一个无向图的最大独立集,通俗地讲就是:在无向图中选出若干个点,这些点互相没有边连接,并使取出的点尽量多。
小D虽然图论很弱,但是也知道无向图最大独立集是npc,但是小C很仁慈的给了一个很有特点的图: 图中任何一条边属于且仅属于一个简单环,图中没有重边和自环。小C说这样就会比较水了。
小D觉得这个题目很有趣,就交给你了,相信你一定可以解出来的。
Input
第一行,两个数\(n\),\(m\),表示图的点数和边数。
第\(2\sim m+1\)行,每行两个数\(x\),\(y\),表示\(x\)与\(y\)之间有一条无向边。
Output
输出这个图的最大独立集。
HINT
\(100\%\) \(n\le 50000,m\le 60000\)
不用建圆方树的仙人掌。
最大独立集:选出最大的点集,使得两两没有边连接。
对普通树边按普通的\(dp\)即可
对环上的点,把环的头拽出来,然后从它屁股dp上去就行了
Code:
#include <cstdio>
const int N=6e4+10;
int head[N],to[N<<1],Next[N<<1],cnt;
void add(int u,int v)
{
to[++cnt]=v,Next[cnt]=head[u],head[u]=cnt;
}
int min(int x,int y){return x<y?x:y;}
int max(int x,int y){return x>y?x:y;}
const int inf=0x3f3f3f3f;
int n,m,dp[N][2],dfn[N],low[N],dfsclock,fa[N];
void cal(int rt,int now)
{
int t=now,s0=0,s1=0;
while(now!=rt)
{
int tmp=s0;
s0=max(s0,s1)+dp[now][0];
s1=tmp+max(dp[now][1],dp[now][0]);
now=fa[now];
}
dp[rt][0]+=max(s0,s1);
s0=-inf,s1=0,now=t;
while(now!=rt)
{
int tmp=s0;
s0=max(s0,s1)+dp[now][0];
s1=tmp+max(dp[now][1],dp[now][0]);
now=fa[now];
}
dp[rt][1]+=s0;
}
void dfs(int now)
{
dp[now][1]=1;
dfn[now]=low[now]=++dfsclock;
for(int v,i=head[now];i;i=Next[i])
if((v=to[i])!=fa[now])
{
if(!dfn[v]) fa[v]=now,dfs(v),low[now]=min(low[now],low[v]);
else low[now]=min(low[now],dfn[v]);
if(dfn[now]<low[v])//正常树边
dp[now][0]+=max(dp[v][0],dp[v][1]),dp[now][1]+=dp[v][0];
}
for(int v,i=head[now];i;i=Next[i])
if(fa[v=to[i]]!=now&&dfn[v]>dfn[now])
cal(now,v);
}
int main()
{
scanf("%d%d",&n,&m);
for(int u,v,i=1;i<=m;i++) scanf("%d%d",&u,&v),add(u,v),add(v,u);
dfs(1);
printf("%d\n",max(dp[1][0],dp[1][1]));
return 0;
}
2018.12.24
最新文章
- private + virtual in Java/C++
- php 分页
- C# 向Http服务器送出 POST 请求
- 数据库连接报错之IO异常(The Network Adapter could not establish the connection)
- 用Winrar批量解压缩有密码文件方法,只需输入一次密码
- Nginx下支持ThinkPHP的Pathinfo和URl Rewrite模式
- LeetCode 202. Happy Number (快乐数字)
- 【技术干货】git常用命令
- 新手立体四子棋AI教程(2)——价值评估函数
- ubuntu 环境下编译 hadoop 2.6.0的简单方法
- AttributeError: &#39;list&#39; object has no attribute &#39;keys&#39;
- Python 面向对象介绍
- yum梳理
- 解决编译安装php时报错:Please reinstall the iconv library
- java实现文件的上传和下载
- vue 调用第三方接口配置
- 【Python】Java程序员学习Python(一)— 为什么学习Python
- 单元测试 java调用不同包下的类时,出现 NoClassDefFoundError 的解决方案
- css绘制常见的几何图形
- es6 class 了解