「Stoi2032」以父之名
题目大意
给一个边权为 (1) 或 (2) 的无向图，要求对每条边定向使得每个点的入度与出度之差的绝对值为 (1)。保证每个点的度数为奇数且存在一种方案。
Solution
考虑这个图只有 (1) 的边怎么做。因为每个点入度与出度之差为 (1)，所以每个点的度数必为奇数，于是考虑建立一个虚点，向每个点连一条边，此时每个点度数为偶数（因为每个点的差均为 (1)，而差值的和必为 (0)，所以肯定是偶数个点），然后跑一次欧拉回路，欧拉回路所定方向即为一种可行解。
那么，加入 (2) 的边的时候呢？
我们分别考虑度数为奇数的点和度数为偶数的点。显然，对于入度为奇数的点，我们同样建立虚点向它们连边，又因为一条边会构造出两个度数为奇数的点，所以虚点的度数也为偶数，这个图仍是一个欧拉图。因为每个点的度数为奇数，所以原本度数为奇数的点必然有偶数条 (2) 和奇数条 (1)，相对应的，原本度数为偶数的点必然有奇数条 (2) 和奇数条 (1)。
我们再考虑一个神奇的贪心算法：设之前转移过来的时候边权是 (w)，则我们优先选择边权为 (w) 的边，否则再去选另一种边权的边。这样，度数为奇数的点全部奇数边和偶数边会分别进行匹配，去掉新加的边，入度与出度差即为 (1)；度数为偶数的点，只有一组偶数和奇数边匹配，其它仍然是分别匹配。
由此，我们在 (O(V+E)) 的时间内，解决了这道题。
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int num=0;char ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();
while('0'<=ch&&ch<='9')num=num*10+ch-'0',ch=getchar();
return num;
}
const int MAXN=1e6+10;
const int MAXM=8e6+10;
struct qwq{
int v;
int w;
int nxt;
}edge[MAXM];
int cnt=-1;
int head[MAXN];
int h[MAXN][3];
int nxt[MAXM];
void adde(int u,int v,int w){
edge[++cnt].nxt=head[u];
edge[cnt].v=v;
edge[cnt].w=w;
nxt[cnt]=h[u][w];
h[u][w]=head[u]=cnt;
}
int n,m;
int deg[MAXN];
int ans[MAXM];
void dfs(int u,int pre){
while(~h[u][pre]&&ans[h[u][pre]]!=-1)h[u][pre]=nxt[h[u][pre]];
if(!(~h[u][pre])){
pre=((pre-1)^1)+1;
while(~h[u][pre]&&ans[h[u][pre]]!=-1)h[u][pre]=nxt[h[u][pre]];
}
if(!(~h[u][pre]))return;
ans[h[u][pre]]=0,ans[h[u][pre]^1]=1;
int v=edge[h[u][pre]].v;
h[u][pre]=nxt[h[u][pre]];
dfs(v,pre);
for(int i=head[u];~i;i=edge[i].nxt){
head[u]=edge[i].nxt;
if(ans[i]!=-1)continue;
int v=edge[i].v;
ans[i]=0,ans[i^1]=1;
dfs(v,edge[i].w);
}
}
int main(){
memset(h,-1,sizeof(h));
memset(nxt,-1,sizeof(nxt));
memset(ans,-1,sizeof(ans));
memset(head,-1,sizeof(head));
n=read(),m=read();
for(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]++;
}
for(int i=1;i<=n;++i){
if(deg[i]&1){
adde(n+1,i,1);
adde(i,n+1,1);
}
}
dfs(1,1);
for(int i=1;i<=m;++i){
putchar(ans[(i-1)<<1]?'1':'0');
}
putchar('
');
}