题解 P7816 「Stoi2032」以父之名
Konnyaku_LXZ
2021-08-18 20:41:45
考虑通过**欧拉回路**来构造答案。
我们**建立一个虚点,向所有度数为奇数的点连权值为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;
}
```