本文主要是介绍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;
}这篇关于AtCoder Regular Contest 176 C. Max Permutation（计数 分类讨论）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
