CF191D Metro Scheme 题解

画图制胜!!!

Statement

给定一个仙人掌图,求至少用多少条简单路径或者简单环可以恰好覆盖所有边

\(n\le 10^5\)

Solution

主要参考了 https://www.cnblogs.com/pealfrog/p/15228596.html

有这样三种简单环:

CF191D Metro Scheme 题解CF191D Metro Scheme 题解CF191D Metro Scheme 题解

第一种我们显然只需要用一个简单环覆盖就好了,第二种我们无论如何需要使用两条,第三种我们也需要两条

我们不妨称那些环外边的数量为 环的度数

我们还可以像这样来理解:

第二种,我们在覆盖那条环外边的时候顺便覆盖了环内的一些边,但可惜此时还差一条边

第三种,我们可以在覆盖两条环外边的时候顺手就把整个环给覆盖掉,所以可以认为是说这个环不存在贡献了,这个环被我们删掉了

也就是说,只要一个环的度数 \(\ge 2\) ,那么它就可以被删除

在度数为 \(0/1\) 的时候,需要额外的一费

现在我们假装把所有环都干掉了,变成了一个无向无环图

考虑这样几种情况:

CF191D Metro Scheme 题解CF191D Metro Scheme 题解CF191D Metro Scheme 题解CF191D Metro Scheme 题解

考虑每个点的贡献,即为了覆盖于这个点有关联的边所付出费用

图一中,每个点贡献 \(1\) ,一条边两个端点,除 \(2\)​

图二中,度数为 \(2\) 的点贡献为 \(0\)

图三中,每个点贡献 \(1\) ,可以看做隔离左侧三个点,先做一次图二操作,把左上点和下点缩到了中心点上,然后变成了图一情况,此时中心点有贡献 \(1\)。一条边两个端点,除 \(2\)。

图四中,中心点无贡献

我们于是得到这样的一个规律:

偶度数点贡献 \(0\) ,奇度数点贡献 \(1\),最后将总贡献除 \(2\) 即可

我们可以使用 tarjan 找环(边双),所以它是 \(O(n)\) 的???

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5+5;

int read(){
	int s=0,w=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
	while(isdigit(ch))s=s*10+(ch^48),ch=getchar();
	return s*w;
}

struct Edge{
	int nex,to;
}edge[N<<1];
int head[N],dfn[N],low[N],deg[N];
bool vis[N],bd[N<<1];
vector<int>cir[N];
int n,m,elen=1,tim,cnt,ans;//

void addedge(int u,int v){
	edge[++elen]={head[u],v},head[u]=elen;
	edge[++elen]={head[v],u},head[v]=elen;
	deg[u]++,deg[v]++;
}
void tarjan(int u,int fath){
	dfn[u]=low[u]=++tim;
	for(int e=head[u],v;v=edge[e].to,e;e=edge[e].nex)
		if(!dfn[v]){
			tarjan(v,u),low[u]=min(low[u],low[v]);
			if(low[v]>dfn[u])bd[e]=bd[e^1]=true;
		}else if(v^fath)low[u]=min(low[u],dfn[v]);
}
void dfs(int u){
	vis[u]=true,cir[cnt].push_back(u);
	for(int e=head[u],v;v=edge[e].to,e;e=edge[e].nex)
		if(!bd[e]&&!vis[v])dfs(v);
}

signed main(){
	n=read(),m=read();
	for(int i=1,u,v;i<=m;++i)
		u=read(),v=read(),addedge(u,v);
	if(!m)return puts("0 0"),0;
	for(int i=1;i<=n;++i)tarjan(i,0); 
	for(int i=1;i<=n;++i)if(!vis[i])cnt++,dfs(i);
	if(cnt==1)return printf("1 %d\n",m),0;
	for(int i=1;i<=n;++i)ans+=deg[i]&1;
	ans>>=1;
	for(int i=1,t;t=0,i<=cnt;++i)
		if(cir[i].size()!=1){
			for(int j=0;j<(int)cir[i].size();++j)
				t+=deg[cir[i][j]]>=3;
			ans+=t<=1; 
		}
	printf("%d %d\n",ans,m);
	return 0;
}
上一篇:[NOIP2015 提高组] 运输计划


下一篇:acwing352.闇の連鎖 树上差分