差亿点 AK, 只怪没学过状态压缩动态规划, 呀嘞呀嘞 dazei
枚举一个图的子图:
- for(int i=n;i;i=(i-1)&n)
- {
- //i 就是 n 的子图
- }
- AtCoder Beginner Contest 187 F - Close Group https://atcoder.jp/contests/abc187/tasks/abc187_f
题意: 给一个 n(n<=18) 节点 m 条边的图, 删除几个边后, 使它变成几个连通子图, 求最少能够变成几个子图, 并且全是完全图
题解: 首先枚举所有子图, 如果是完全图, 标记 dp[i]=1, 然后从小到大枚举, 对一个非完全子图, 再枚举其子图更新答案, 由于是从小到大枚举, 因此当前子图的子图肯定已经更新完了, 所以可放心 dp
- #include<bits/stdc++.h>
- using namespace std;
- #define f(i,a,b) for(register int i=a;i<=b;++i)
- #define ll long long
- #define pb push_back
- inline int read(){int x;scanf("%d",&x);return x;}
- int eg[20][20],dp[1<<N];
- void solve()
- {
- int n=read(),m=read();
- f(i,1,m){
- int x=read(),y=read();
- eg[x][y]=eg[y][x]=1;
- }
- int sum=(1<<n)-1;
- dp[0]=999999;
- for(int i=1;i<=sum;++i)
- {
- vector<int>edge;
- for(int j=0;j<n;j++) if(i&(1<<j)) edge.pb(j+1);
- int flag=1;
- for(int j=0;flag&&j<edge.size();++j)
- for(int k=j+1;flag&&k<edge.size();++k)
- if(!eg[edge[j]][edge[k]]) flag=0;
- if(flag) dp[i]=1;
- else dp[i]=999999;
- }
- for(int i=1;i<=sum;++i)
- {
- if(dp[i]==1) continue;
- for(int j=i;j;j=(j-1)&i)
- {
- dp[i]=min(dp[i],dp[j]+dp[j^i]);
- }
- }
- cout<<dp[sum]<<endl;
- }
- int main()
- {
- int T=1;
- while(T--) solve();
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3711925.html