题解 P7816 「Stoi2032」以父之名

· · 题解

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

我们建立一个虚点，向所有度数为奇数的点连权值为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;
}