题解 P7816 「Stoi2032」以父之名

考虑通过**欧拉回路**来构造答案。 我们**建立一个虚点，向所有度数为奇数的点连权值为1的虚边**，而度数为奇数的点必然有偶数个（考虑初始时所有点都是孤立的，度数均为 $0$，然后我们把边逐条加入图，一条边为它连接的两个点分别提供了 $1$ 的度数，即同时改变了它连接的两点度数的奇偶性），所以此时新图中的所有点度数都为偶数，即新图存在欧拉回路。 在跑欧拉回路时，假设我们通过边权为 $w$ 的边**进入**了点 $u$，那么我们现在要为 $u$ **选择一条出边**，我们**优先选择边权为 $w$ 的边，后选择边权不为 $w$ 的边**。 为什么要这么选呢？因为对于每个点 $i$，与它相连的所有边的边权和为奇数，所以每个点都应该有**奇数条权值为 $1$ 的边**与它相连，而权值为 $2$ 的边可以是奇数条也可以是偶数条。又因为**一个点有虚边当且仅当与这个点相连的权值为 $2$ 的边有偶数条**，所以按照上述策略选择出边，**不会**出现入边权值为 $2$，而不存在权值为 $2$ 的出边，我们选了虚边，导致该点入边与出边权值和之差的绝对值不为 $1$ 的情况。所以我们的构造方法是正确的。 总结一下，我们整道题的思路就是：**建立一个虚点，向所有度数为奇数的点连权值为 $1$ 的虚边，然后跑欧拉回路。在这个过程中，我们优先选择边权与入边相同的出边，后选择边权与入边不同的出边**。 最后吐槽一下，这题有亿点点卡常。 Code: ```cpp #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; } ```