P11844 [USACO25FEB] Friendship Editing G

· · 题解

思路：

考虑其补图，必为若干个互不相交的团。

故直接状压 dp_S 表示使得 S 的最小操作数，先预处理出 f_S 表示使得 S 为一个团的操作数，有状态转移：

dp_S = \min\limits_{T \subset S} dp_T + f_{S - T}

中间可能有算重的，但是这是操作次数的最小值，所以不必理会，时间复杂度为 O(3^n)。

完整代码：

#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
#define Add(x, y) (x + y >= mod) ? (x + y - mod) : (x + y)
#define lowbit(x) x & (-x)
#define pi pair<ll, ll>
#define pii pair<ll, pair<ll, ll>>
#define iip pair<pair<ll, ll>, ll>
#define ppii pair<pair<ll, ll>, pair<ll, ll>>
#define ls(k) k << 1
#define rs(k) k << 1 | 1
#define fi first
#define se second
#define full(l, r, x) for(auto it = l; it != r; ++it) (*it) = x
#define Full(a) memset(a, 0, sizeof(a))
#define open(s1, s2) freopen(s1, "r", stdin), freopen(s2, "w", stdout);
#define For(i, l, r) for(register int i = l; i <= r; ++i)
#define _For(i, l, r) for(register int i = r; i >= l; --i)
using namespace std;
using namespace __gnu_pbds;
typedef double db;
typedef unsigned long long ull;
typedef long long ll;
bool Begin;
const int N = 17, M = 1 << N;
inline ll read(){
    ll x = 0, f = 1;
    char c = getchar();
    while(c < '0' || c > '9'){
        if(c == '-')
          f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9'){
        x = (x << 1) + (x << 3) + (c ^ 48);
        c = getchar();
    }
    return x * f;
}
inline void write(ll x){
    if(x < 0){
        putchar('-');
        x = -x;
    }
    if(x > 9)
      write(x / 10);
    putchar(x % 10 + '0');
}
int n, m, u, v;
int f[M], g[M];
bool vis[N][N];
bool End;
int main(){
    n = read(), m = read();
    while(m--){
        u = read(), v = read();
        vis[u][v] = 1;
    }
    for(int S = 0; S < (1 << n); ++S)
      for(int i = 1; i <= n; ++i)
        if((S >> (i - 1)) & 1)
          for(int j = i + 1; j <= n; ++j)
            f[S] += ((S >> (j - 1)) & 1) ? vis[i][j] : (vis[i][j] ^ 1);
    for(int S = 0; S < (1 << n); ++S){
        g[S] = f[S];
        for(int T = S; T; T = (T - 1) & S)
          g[S] = min(g[S], g[T] + f[S ^ T]);
    }
    write(g[(1 << n) - 1]);
    cerr << '\n' << abs(&Begin - &End) / 1048576 << "MB";
    return 0;
}