专栏文章

题解：P12041 [USTCPC 2025] 图上交互题2 / Con...tive Minimum Mex Path

EELECTRODE_kaf
P12041题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mipnzsa2
此快照首次捕获于
2025/12/03 15:07
3 个月前
此快照最后确认于
2025/12/03 15:07
3 个月前
查看原文
注意到 uiu_i 和 viv_i 之间存在一条长度为 11 的直接连边，所以这个路径的贡献为 00 或 11，故 ∀f(x)≤1\forall f(x)\le 1，否则无解。
若 f(x)=1f(x)=1，则 a=0a=0，且 uiu_i 和 viv_i 之间任意其他路径上至少存在一个边权为 00。将所有边权为 00 的边删除，若这两点连通则无解，跑 DFS 检验连通性。否则令 a=1a=1，可构造一组合法方案。
CPP
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)<<' ';
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...