题解：AT_abc396_e [ABC396E] Min of Restricted Sum

挺有意思的一道题

把每个限制看成一条从

x_i

到

y_i

的无向边。

这样

n

个点会被分成若干个联通块，考虑对于一个块内求解。

显然结论：在一个块内，只要确定了其中一个数，别的也都唯一确定。

重要结论：对于一个存在解的块，随意确定其中一个数，仍然存在解。 因为只有环才会影响解的有无性，可以自己画几个环理解一下。

这样，我们就可以对每一个二进制位分别讨论。每条边边权只有

0

或

1

，表示边两端当前二进制位一样或不一样。

把原图删减一些边，变成森林，对于每棵树做树型 dp，

f_{i,{0/1}}

表示这个点填

0/1

时其子树的贡献。再为我们钦定的树根选择

0

或

1

，其他也就唯一确定。

然而一天后发现其实选一个点01各试一下取较优就行。

最后遍历所有边判断解的合法性即可。

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 200100;
int n,m,x[N],y[N],z[N];
int ans[N];
struct edge{
	int nxt,to,w;
}e[N*2];
int cnt,head[N];
inline void add(int u,int v,int w){
	e[++cnt].nxt=head[u];
	e[cnt].to=v;
	e[cnt].w=w;
	head[u]=cnt;
}
int fa[N];
int find(int x){
	if(fa[x]==x) return x;
	else return fa[x] = find(fa[x]);
}
inline void build(int k){
	for(int i=1;i<=n;i++) fa[i]=i;
	cnt=0;
	memset(head,0,sizeof(head));
	memset(e,0,sizeof(e));
	for(int i=1;i<=m;i++){
		int u=x[i],v=y[i],w=(z[i]>>(k-1)) & 1ll;
		int U=find(u),V=find(v);
		if(U==V) continue;
		fa[U]=V;
		add(u,v,w);
		add(v,u,w);
	}
	return;
}
int f[N][2];
inline void dfs(int u){
	f[u][0]=0,f[u][1]=1;
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].to,w=e[i].w;
		if(f[v][0]==-1){
			dfs(v);
			f[u][0]+=f[v][w];
			f[u][1]+=f[v][1^w];
		}
	}
	return;
}
bool vis[N];
inline void upd(int u,bool flag,int k){
	if(flag) ans[u]|=(1ll<<(k-1));
	vis[u]=true;
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].to,w=e[i].w;
		if(!vis[v]) upd(v,(flag^w),k);
	}
	return;
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin>>n>>m;
	for(int i=1;i<=m;i++) cin>>x[i]>>y[i]>>z[i];
	for(int i=1;i<=40;i++){
		build(i);
		memset(f,-1,sizeof(f));
		memset(vis,0,sizeof(vis));
		for(int j=1;j<=n;j++){
			if(f[j][0]==-1){
				dfs(j);
				if(f[j][0]<f[j][1]) upd(j,0,i);
				else upd(j,1,i);
			}
		}
	}
	for(int i=1;i<=m;i++){
		if((ans[x[i]]^ans[y[i]])!=z[i]){
			cout<<-1;
			return 0;
		}
	}
	for(int i=1;i<=n;i++) cout<<ans[i]<<' ';
	return 0;
}

题解：AT_abc396_e [ABC396E] Min of Restricted Sum

文章操作

相关推荐

评论

题解：AT_abc396_e [ABC396E] Min of Restricted Sum