AtCoder Regular Contest 176 C. Max Permutation（计数 分类讨论）

题目

思路来源

乱搞ac

题解

1. 如果有边的权值是1，意味着有两个点的权值都是1，无解

2. 如果一个点i被多个max条件控制，它的值不能超过这些max里最小的那个，记做up[i]

3. 如果同一个权值w对应的边不少于2条，这些边应该有一个公共点i，否则无解，如果up[i]<w也无解，否则给这个点i赋初值w

4. 从大到小考虑权值w，类似拓扑排序，把度为0的点加到队列里，初始没有被边覆盖的点是度为0的点，后续删掉max边之后且没有填值的点是度为0的点，当前度为0的点是自由点

检查所有权值w的边，对于当前边两个端点u，v

（1）如果w这个值已经被点i用了，u、v两个点中得有一个是i，否则无解

（2）如果没有用，考虑up[u]和up[v]，如果都小于w，说明无解；如果正好有一个等于w，说明就该是那个点填w；否则有两个点等于w，说明都可以，把其中一个填w，剩下一个当自由点

从大到小考虑权值w的过程中，对于没有限制的，乘上当前自由点的个数，并令当前自由点数减1

其实就是在一个不断删除边的过程中统计数量

代码

//#include <bits/stdc++.h>
#include<iostream>
#include<cstdio>
#include<vector>
#include<map>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<int,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
const int N=2e5+10,mod=998244353;
int n,m,a[N],b[N],c[N],up[N],res[N],to[N],deg[N];
vector<P>col[N];
map<int,int>mp;
bool used[N];
int main(){
    sci(n),sci(m);
    rep(i,1,n)up[i]=n+1;
    rep(i,1,m){
        sci(a[i]),sci(b[i]),sci(c[i]);
        deg[a[i]]++;deg[b[i]]++;
        up[a[i]]=min(up[a[i]],c[i]);
        up[b[i]]=min(up[b[i]],c[i]);
        col[c[i]].pb(P(a[i],b[i]));
    }
    if(!col[1].empty()){
        puts("0");
        return 0;
    }
    rep(i,2,n){
        if(!SZ(col[i]))continue;
        mp.clear();
        int mx=0;
        for(auto &x:col[i]){
            mp[x.fi]++;
            mp[x.se]++;
            mx=max(mx,mp[x.fi]);
            mx=max(mx,mp[x.se]);
        }
        int sz=SZ(col[i]);
        if(sz>=2){
            for(auto &x:mp){
                int pos=x.fi,cnt=x.se;
                if(cnt!=mx)continue;
                if(cnt!=sz){
                    puts("0");
                    return 0;
                }
                else{
                    if(up[pos]<i){
                        puts("0");
                        return 0;
                    }
                    res[pos]=i;
                    used[i]=1;
                    to[i]=pos;
                }
            }
        }
    }
    ll ans=1,cnt=0;
    rep(i,1,n){
        if(!deg[i])cnt++;
    }
    per(i,n,1){
        if(!SZ(col[i])){
            ans=1ll*ans*cnt%mod;
            cnt--;
            continue;
        }
        for(auto &x:col[i]){
            int u=x.fi,v=x.se;
            if(up[u]<i && up[v]<i){
                puts("0");
                return 0;
            }
            if(used[i]){
                if(res[u]!=i && res[v]!=i){
                    puts("0");
                    return 0;
                }
                deg[u]--;deg[v]--;
                if(!deg[u] && res[u]!=i)cnt++;
                if(!deg[v] && res[v]!=i)cnt++;
                continue;
            }
            if(up[u]==i && up[v]<i){
                res[u]=i;
                used[i]=1;
                deg[v]--;
                if(!deg[v])cnt++;
                continue;
            }
            if(up[v]==i && up[u]<i){
                res[v]=i;
                used[i]=1;
                deg[u]--;
                if(!deg[u])cnt++;
                continue;
            }
            ans=2ll*ans%mod;
            cnt++;
        }
    }
    printf("%lld\n",ans);
    return 0;
}