【牛客提高训练营5B】旅游

吉老师的题时过一年还是不会做

从\(1\)号点出发经过每条边至少一次并且还要回到\(1\)号点，这跟欧拉回路的条件非常像，但是欧拉回路的实际上是"经过每一条边恰好一次并且回到出发点"

所以可以理解为将每一条边拆成多条边，使得总边权和最小，并且图中存在一条欧拉回路

而一张图存在欧拉回路的条件是不存在度数为奇数的点

换句话说，给每条边定一个经过次数\(cnt_i\)，最小化\(\sum_{i=1}^mcnt_i2^i\)，并且使得每个点的所连边的\(cnt\)的和为偶数

看起来不是很可做，但是这里的边都是\(2\)的次幂，这启示我们贪心

我们考虑对原图求出一棵最小生成树，这样对于每一条非树边，我们都能使得其被经过次数为\(1\)。这只需要去最小生成树上把这条非树边连接的两个点的路径都走一遍即可，因为这条路径上最大的二进制位都要小于这条非树边，所以形成的和也要小于这条边。

之后在最小生成树上做一些调整使得所有点度数都是偶数即可。

先默认所有的边的\(cnt=1\)，统计出每个点的度数，之后dfs最小生成树，发现有一个点度数为奇数就让它和它父亲连接的那条边的\(cnt\)加一。可以证明，所有点的度数最后一定都会变成偶数。

代码

#include<bits/stdc++.h>

#define re register

inline int read() {

	char c=getchar();int x=0;while(c<'0'||c>'9') c=getchar();

	while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;

}

const int maxn=5e5+5;

const int mod=998244353;

struct E{int v,nxt,w;}e[maxn<<1];

int n,m,num,ans,d[maxn],fa[maxn],head[maxn];

int find(int x) {return fa[x]==x?x:fa[x]=find(fa[x]);}

inline int qm(int x) {return x>=mod?x-mod:x;}

inline void add(int x,int y,int w) {

	e[++num].v=y;e[num].nxt=head[x];head[x]=num;e[num].w=w;

}

void dfs(int x,int fa,int p) {

	for(re int i=head[x];i;i=e[i].nxt)

	if(e[i].v!=fa) dfs(e[i].v,x,e[i].w);

	if(d[x]&1) d[fa]^=1,ans=qm(ans+p);

}

int main() {

	n=read(),m=read();

	for(re int i=1;i<=n;i++) fa[i]=i;

	for(re int v=1,x,y,i=1;i<=m;i++) {

		d[x=read()]^=1,d[y=read()]^=1;

		v=qm(v+v);ans=qm(ans+v);

		int xx=find(x),yy=find(y);

		if(xx==yy) continue;

		fa[xx]=yy;add(x,y,v),add(y,x,v);

	}

	dfs(1,0,0);printf("%d\n",ans);

	return 0;

}

巴特西

【牛客提高训练营5B】旅游

最新文章

热门文章