题解：P11844 [USACO25FEB] Friendship Editing G

· · 题解

考虑在满足条件的图上，如果 a 和 b 不是朋友，它们和其它奶牛的关系：

那么，考虑满足条件的图的补图，不难发现它是由若干个团组成的。

这样，先把刚开始的图变成其补图，原问题就可以转化成：给定一个图，每次可以加边或删边，求将其变为若干个团的并的最少操作次数。

数据范围提示我们状压 DP。首先可以想到一个大致的思路：

设 f_{S} 表示选择 S 中的奶牛，它们内部合法（即形成若干个团）的最少操作次数。为了帮助转移，再设一个 g_{S} 表示选择 S 的奶牛，它们内部要连成一个团的最少操作次数（这个可以 O(n^22^n) 预处理）。那么有：

f_{S}=\min\limits_{T\subset S}(f_{T}+g_{S\backslash T})

涉及枚举子集，dp 时间复杂度 O(3^n)，总时间复杂度 O(n^22^n+3^n)。

但是需要注意实现细节：仔细想想，会发现直接这样转移，不管 f_S 和 g_S 是否需要包括内部的点连到外面的点的状态，总是会有一些边要么被重复算了，要么没有被计算进来。其实这不难解决，因为每条边就算要算，也最多被两个端点各算一次，所以只要保证在计算 g_S 时，把集合内部的点之间的连边也算两次，最后把答案除以二就可以了。

#include<bits/stdc++.h>
using namespace std;
const int N=18;
bool a[N][N];
int f[1<<N],g[1<<N];
int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    int n,m;cin>>n>>m;
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)a[i][j]=1;
    while(m--){
        int x,y;cin>>x>>y;
        a[x][y]=a[y][x]=0;//补图
    }
    for(int S=0;S<(1<<n);S++){
        for(int i=1;i<=n;i++)if((S>>(i-1))&1){
            for(int j=1;j<=n;j++){
                if(i!=j)g[S]+=(((S>>(j-1))&1)/*是否需要有边*/?(!a[i][j]):a[i][j]);
            }
        }
    }
    for(int S=0;S<(1<<n);S++){
        f[S]=g[S];
        for(int s=S;s;s=S&(s-1)){
            f[S]=min(f[S],f[S^s]+g[s]);
        }
    }
    cout<<f[(1<<n)-1]/2;
    return 0;
}