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

ELECTRODE_kaf · 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)<<' ';
}