专栏文章

题解：P11844 [USACO25FEB] Friendship Editing G

__2eyks
P11844题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@minalcil
此快照首次捕获于
2025/12/01 23:16
3 个月前
此快照最后确认于
2025/12/01 23:16
3 个月前
查看原文
国庆的时候，凯撒大人 bluewindde 推荐做的题，今天联考考了这个题的子问题，所以写篇题解。
首先发现这个图没啥性质啊，套路地考虑建补图，会发现整个原图会形成多个团。那其实就是把图变成多个团的答案。这个就是联考题了。
注意到 N=16N=16，肯定是状压来做了。设 fSf_S 表示只保留集合 SS 内的点，对应导出子图的答案。只有一个 fSf_S 可能不好直接做，考虑设 gSg_S 表示把 SS 内集合搞成一个团，且把 SS 中的点与其他点的连边断开的答案。有 fS=fS−T+gTf_S=f_{S-T}+g_T。
至于为什么 gSg_S 要这样定义？因为 ff 的转移过程，相当于在 S−TS-T 答案的基础上，新开一个点集 TT 的团，那么这个新的团肯定不能与其他点连边。
时间复杂度 Θ(2nn2+3n)\Theta(2^nn^2+3^n)。
CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...