[ABC352F] Estimate Order 讲解

· · 题解

题目

考察：爆搜状压 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;
}