本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-05-15 17:50:41

题目

考察：爆搜状压 dp。
题目简述： 给你一个 $n$，有一个 $1$ 到 $n$ 的排列 $a$，给你 $m$ 个关系，表示 $a_x$ 比 $a_y$ 大 $z$，问每一个数是否确定，若确定，输出是多少，若不是，输出 $-1$。
数据保证有解。
数据范围：
$2\le n\le 16$
$0\le m\le \frac{n(n-1)}{2}$

首先我们像图一样建边，每条边 $u,v,w$ 表示 $a_u$ 比 $a_v$ 大 $w$（$w$ 可以是负数），然后我们再来几遍 dfs，得出每个部分中的每个元素比部分中的代表元素多了多少。设 $siz_i$ 表示第 $i$ 个部分的大小，$pos_i$ 表示第 $i$ 个元素比代表元素大多少。

然后我们很容易想到状压，一个 $n$ 位的二进制数码，第 $i$ 位表示一个部分是否拥有一个比代表元素大 $i-1$ 的数。
我们设第 $i$ 个部分的二进制数码是 $res_i$，这样，问题就变成了能否取合适的 $x$，使 $res_{i}\times 2^x$ 两两不相交（交集为空）。

我们很容易发现一个部分内的元素，要么都不确定，要么都确定。那么只要把除一个之外的部分放上去，若剩余部分是固定的，则该部分都是固定的。那么我们先把除一个部分以外的部分都塞进去，然后再塞那个部分，统计一下 $x$ 有几个即可。

总体复杂度为 $O(2^nn^3)$。
代码：

#include<bits\/stdc++.h>
#define inl inline
#define int long long
#define rep(i,x,y) for(int i=x;i<=y;++i)
#define per(i,x,y) for(int i=x;i>=y;--i)
#define fst ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define INF LLONG_MAX
using namespace std;
const int N=25,M=(1ll<<16)+5;
int n,m,a,b,c,num,pos[N],res[N],siz[N],ans[N],vis[N];
vector<pair<int,int> >g[N],d;
bool f[N][M];
set<int>st;
inl bool cmp(pair<int,int>x,pair<int,int>y){
	return x.second<y.second;
}
inl void dfs(int x,int sum){
	vis[x]=num;
	d.push_back({x,sum});
	for(auto pr:g[x])
		if(!vis[pr.first]) dfs(pr.first,sum+pr.second);
}
signed main(){
	fst;
	cin>>n>>m;
	rep(i,1,m){
		cin>>a>>b>>c;
		g[a].push_back({b,-c});
		g[b].push_back({a,c});
	}
	rep(i,1,n)
		if(!vis[i]){
			d.clear();
			++num;
			dfs(i,0);
			sort(d.begin(),d.end(),cmp);
			for(auto pr:d){
				pos[pr.first]=pr.second-d[0].second;
				res[num]|=1ll<<pos[pr.first];
			}
			siz[num]=d[d.size()-1].second-d[0].second+1;
		}
	memset(ans,-1,sizeof(ans));
	rep(i,1,num){
		memset(f,0,sizeof(f));
		f[0][0]=1;
		rep(j,1,num)
			if(j==i) memcpy(f[j],f[j-1],sizeof(f[j-1]));
			else rep(k,0,(1ll<<n))
				if(f[j-1][k])
					rep(l,0,n-siz[j])
						if((k&(res[j]<<l))==0) f[j][k|(res[j]<<l)]=1;
		st.clear();
		rep(j,0,(1ll<<n)-1)
			if(f[num][j])
				rep(k,0,n-siz[i])
					if((j&(res[i]<<k))==0) st.insert(k);
		if(st.size()==1)
			rep(j,1,n)
				if(vis[j]==i) ans[j]=(*st.begin())+pos[j]+1;
	}
	rep(i,1,n) cout<<ans[i]<<' ';
	return 0;
}