自动搬运

查看原文

来自洛谷，原作者为

	ELECTRODE_kaf 我是一只可爱滴猫娘 ~ ^_^|AFO

搬运于2025-08-24 23:12:23，当前版本为作者最后更新于2025-04-10 12:10:57，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

注意到 $u_i$ 和 $v_i$ 之间存在一条长度为 $1$ 的直接连边，所以这个路径的贡献为 $0$ 或 $1$，故 $\forall f(x)\le 1$，否则无解。

若 $f(x)=1$，则 $a=0$，且 $u_i$ 和 $v_i$ 之间任意其他路径上至少存在一个边权为 $0$。将所有边权为 $0$ 的边删除，若这两点连通则无解，跑 DFS 检验连通性。否则令 $a=1$，可构造一组合法方案。

const ll N=1e5+10;
ll n,m,f[N],bl[N],bcnt;
vector<ll> e0[N],e1[N];

void dfs(ll p){
	bl[p]=bcnt;
	
	for(ll i:e1[p]){
		if(bl[i]) ctn;
		
		dfs(i);
	}
}

int main(){
	cin>>n>>m;
	
	rep(i,1,m){
		ll u,v;
		cin>>u>>v>>f[i];
		
		if(f[i]>1){
			cout<<"no";
			return 0;
		}else if(f[i]==1){
			e0[u].pb(v);
			e0[v].pb(u);
		}else{
			e1[u].pb(v);
			e1[v].pb(u);
		}
	}

	rep(i,1,n){
		if(bl[i]==0){
			bcnt++;
			dfs(i);
		}
	}
	
	rep(i,1,n){
		for(ll j:e0[i]){
			if(bl[i]==bl[j]){
				cout<<"no";
				return 0;
			}
		}
	}
		
	cout<<"yes\n";
	
	rep(i,1,m) cout<<(f[i]^1)<<' ';
}