自动搬运

查看原文

来自洛谷，原作者为

	Konnyaku_LXZ 我好菜啊 QAQ

搬运于2025-08-24 22:33:21，当前版本为作者最后更新于2021-08-18 20:41:45，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

考虑通过欧拉回路来构造答案。

我们建立一个虚点，向所有度数为奇数的点连权值为1的虚边，而度数为奇数的点必然有偶数个（考虑初始时所有点都是孤立的，度数均为 $0$，然后我们把边逐条加入图，一条边为它连接的两个点分别提供了 $1$ 的度数，即同时改变了它连接的两点度数的奇偶性），所以此时新图中的所有点度数都为偶数，即新图存在欧拉回路。

在跑欧拉回路时，假设我们通过边权为 $w$ 的边进入了点 $u$，那么我们现在要为 $u$ 选择一条出边，我们优先选择边权为 $w$ 的边，后选择边权不为 $w$ 的边。

为什么要这么选呢？因为对于每个点 $i$，与它相连的所有边的边权和为奇数，所以每个点都应该有奇数条权值为 $1$ 的边与它相连，而权值为 $2$ 的边可以是奇数条也可以是偶数条。又因为一个点有虚边当且仅当与这个点相连的权值为 $2$ 的边有偶数条，所以按照上述策略选择出边，不会出现入边权值为 $2$，而不存在权值为 $2$ 的出边，我们选了虚边，导致该点入边与出边权值和之差的绝对值不为 $1$ 的情况。所以我们的构造方法是正确的。

总结一下，我们整道题的思路就是：建立一个虚点，向所有度数为奇数的点连权值为 $1$ 的虚边，然后跑欧拉回路。在这个过程中，我们优先选择边权与入边相同的出边，后选择边权与入边不同的出边。

最后吐槽一下，这题有亿点点卡常。

Code:

#include<bits/stdc++.h>
#define rg register
using namespace std;

const int MAXN=1e6+50,MAXM=1e7+50;
typedef long long LL;

int read(){int cnt=0;char c=getchar();while(c<'0'||c>'9') c=getchar();while(c>='0'&&c<='9'){cnt=(cnt<<1)+(cnt<<3)+(c^48);c=getchar();}return cnt;}
void write(int x){if(x==0) putchar('0');else putchar('1');}

struct edge{int nxt,to,val,ans;};

edge e[MAXM];//e[i].nxt为不区分权值的下一条边 
int head[MAXN],Cnte=1;//head[i]表示与i相连的第一条边（不区分权值） 
int nxt[MAXM],now[MAXN][3];//nxt[i]表示权值和当前边相同的下一条边（即区分权值），now[i][j]表示第一条与i相连的权值为j的边 
int N,M,deg[MAXN];

void adde(int u,int v,int w){
	++Cnte;
	e[Cnte]=(edge){head[u],v,w,-1};
	nxt[Cnte]=now[u][w];
	now[u][w]=head[u]=Cnte;
}

void dfs(int u,int pre){
	while(now[u][pre]&&e[now[u][pre]].ans!=-1) now[u][pre]=nxt[now[u][pre]];//优先选权值相同的边 
	if(!now[u][pre]){pre=(pre==1?2:1);while(now[u][pre]&&e[now[u][pre]].ans!=-1) now[u][pre]=nxt[now[u][pre]];}//后选择权值不同的边 
	if(!now[u][pre]) return;
	e[now[u][pre]].ans=0;e[now[u][pre]^1].ans=1; 
	int t=now[u][pre];
	now[u][pre]=nxt[now[u][pre]];
	dfs(e[t].to,pre);
	for(rg int i=head[u];i;i=e[i].nxt){
		head[u]=e[i].nxt;
		if(e[i].ans==-1){e[i].ans=0;e[i^1].ans=1;dfs(e[i].to,e[i].val);}
	}
}

void Init(){
	N=read();M=read();
	for(rg int i=1;i<=M;++i){
		int u=read(),v=read(),w=read();
		adde(u,v,w);adde(v,u,w);
		++deg[u];++deg[v];
	}
}

void Solve(){
	for(rg int i=1;i<=N;++i) if(deg[i]&1){adde(N+1,i,1);adde(i,N+1,1);}//度数为奇数的点向虚点连一条虚边 
	dfs(1,1);
}

void Print(){
	for(rg int i=1;i<=M;++i) write(e[i<<1].ans);
}

int main()
{
	Init();
	Solve();
	Print();
	return 0;
}