题解：P12042 [USTCPC 2025] 图上交互题3 / Con...tive Maximum Mex Path

· · 题解

广告：USTCPC2025 题解汇总（部分）。

由于路径可以不是简单路径，所以为了使得 \operatorname{mex} 最大一定会走完整个连通块的每一条边，这样一定不劣，所以两个点的 f 等价于这两个点所在连通快的 \operatorname{mex}，只需要构造一个连通块有 0 到 f(u,v)-1 就行，然后如果连通块边数不够或者里面的边的 f 不相等则无解。

以下是线下选手 42 队提供的赛时代码，非常感谢 42 队。

#include <bits/stdc++.h>
#define il inline
#define rg register
#define cit const rg unsigned
#define open ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)//,freopen("I.in","r",stdin),freopen("I.out","w",stdout)
#define int rg unsigned
#define void il void
#define ll long long
#define ull unsigned ll
#define lll __int128
#define db double
#define vector basic_string
#define pq priority_queue
#define vint vector<unsigned>
#define vll vector<ll>
#define vull vector<ull>
#define ump unordered_map
#define ust unordered_set
#define deq deque
#define mkp make_pair
#define pii pair<unsigned,unsigned>
#define pll pair<ull,ull>
#define fi first
#define se second
#define Bool(a,n) bitset<n>a
#define sca(a) for(int $=0;$<n;cin>>a[++$])
#define cle(a) memset(a,0,sizeof a)
#define tmx(a) memset(a,0x3f,sizeof a)
#define tmn(a) memset(a,0xbf,sizeof a)
#define tif(a) memset(a,0xff,sizeof a)
//#define ge getchar_unlocked()
#define pu putchar_unlocked
#define lik(x) __builtin_expect((x),1)
#define ulk(x) __builtin_expect((x),0)
#define max(a,b) (a>b?a:b)
#define min(a,b) (a<b?a:b)
//#define abs(a,b) (a>b?a-b:b-a)
#define fls cout<<endl;
#define PP pop_back()
#define PS push
#define BK back()
#define SZ size()
//inline ll max(const rg ll a,const rg ll b){return a>b?a:b;}
//inline ll min(const rg ll a,const rg ll b){return a<b?a:b;}
inline ll abs(const rg ll a,const rg ll b){return a>b?a-b:b-a;}
using namespace std;constexpr unsigned N=1e6+1,M=4e3+2;//constexpr ll inf=1e9+7;
//unsigned p;
constexpr unsigned p=998244353;
//constexpr unsigned p=1e9+7;
//自动取模类
/**/
namespace mod{
    void add(int&a,cit b){a+=b,a>=p?a-=p:0;}
    void sub(int&a,cit b){add(a,p-b);}
    il unsigned mul(cit ll a,cit ll b){return a*b%p;}
    il unsigned pw(int ll a,int b){int ll s=1;for(;b;b>>=1,a=a*a%p)b&1?s=s*a%p:0;return s;}
    il unsigned inv(cit a){return pw(a,p-2);}
    void div(int&a,cit b){a=mul(a,inv(b));}
    il unsigned div(cit a,cit b){return mul(a,inv(b));}
}
using mod::add;
using mod::sub;
using mod::mul;
using mod::inv;
using mod::pw;
/**/
namespace IO{unsigned char b[1<<22],*l=b,*r=b;
    #define ge (ulk(l==r)?r=(l=b)+fread(b,1,1<<22,stdin):0,ulk(l==r)?'\0':*l++)
    il unsigned rd(){int char c=ge;int s=0;while(c<48||c>58)c=ge;while(lik(c<59&&c>47))s=s*10+(c&0b1111),c=ge;return s;}
    void rd(int&s){int char c=ge;s=0;while(c<48||c>58)c=ge;while(lik(c<59&&c>47))s=s*10+(c&0b1111),c=ge;}
}using IO::rd;
unsigned n,m;struct A{unsigned u,v,w;}e[N];vint a[N];
unsigned b[N],ans[N];vint c[N];
void dfs(cit u,cit rt){b[u]=rt;for(cit&v:a[u])if(!b[v])dfs(v,rt);}
void init(){rd(n),rd(m);
    for(int i=1;i<=m;++i)rd(e[i].u),rd(e[i].v),rd(e[i].w),a[e[i].u]+=e[i].v,a[e[i].v]+=e[i].u;
    for(int i=1;i<=n;++i)if(!b[i])dfs(i,i);
    for(int i=1;i<=m;++i)c[b[e[i].u]]+=i;

}void solve(){init();
    for(int i=1;i<=n;++i)if(c[i].SZ){int id=0;
        for(cit&j:c[i])if(!id)id=e[j].w;
        else if(id^e[j].w){cout<<"No\n";return;}
        if(id>c[i].SZ){cout<<"No\n";return;}
        for(int j=0;j<id;++j)ans[c[i][j]]=j;
        for(int j=id;j<c[i].SZ;++j)ans[c[i][j]]=p;
    }cout<<"Yes\n";for(int i=1;i<=m;++i)cout<<ans[i]<<' ';
}signed main(){open;int t=1;//cin>>t;
    while(t--)solve();}

删除了引用的被注释掉的 hgckythgcfhk.h 的内容，保证这部分全是注释。