题解：P11844 [USACO25FEB] Friendship Editing G

· · 题解

国庆的时候，凯撒大人 bluewindde 推荐做的题，今天联考考了这个题的子问题，所以写篇题解。

首先发现这个图没啥性质啊，套路地考虑建补图，会发现整个原图会形成多个团。那其实就是把图变成多个团的答案。这个就是联考题了。

注意到 N=16，肯定是状压来做了。设 f_S 表示只保留集合 S 内的点，对应导出子图的答案。只有一个 f_S 可能不好直接做，考虑设 g_S 表示把 S 内集合搞成一个团，且把 S 中的点与其他点的连边断开的答案。有 f_S=f_{S-T}+g_T。

至于为什么 g_S 要这样定义？因为 f 的转移过程，相当于在 S-T 答案的基础上，新开一个点集 T 的团，那么这个新的团肯定不能与其他点连边。

时间复杂度 \Theta(2^nn^2+3^n)。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define fr first
#define sc second
#define pii pair<int,int>
#define yes cout<<"Yes\n"
#define no cout<<"No\n"
#define fo(i,l,r) for(int i=l;i<=r;i++)
#define ro(i,r,l) for(int i=r;i>=l;i--)
#define couts(x) cout<<setprecision(x)<<fixed
void Ios(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}
const int N=18;
int n,m,a[N][N],f[1ll<<N],g[1ll<<N];
vector<int>e[N];
void solve(){
    cin>>n>>m;
    fo(i,1,m){
        int u,v;
        cin>>u>>v;
        a[u][v]=a[v][u]=1;
    }
    fo(x,0,(1ll<<n)-1){
        fo(i,1,n)
            if (((x>>(i-1))&1))
                fo(j,i+1,n)
                    g[x]+=(((x>>(j-1))&1)^a[i][j]^1);
        f[x]=g[x];
    }
    fo(x,0,(1ll<<n)-1)
        for (int y=x;y;y=(y-1)&x)
            f[x]=min(f[x],g[y]+f[x^y]);
    cout<<f[(1ll<<n)-1]<<'\n';
}
signed main(){
    Ios();
    int T=1;
    //cin>>T;
    while (T--)
        solve();
    return 0;
}