题面 https://codeforces.com/gym/100920/attachments
题意: 给你 n(20) 个点, m(40 条边), 让你给每条边染一种颜色, 白色 0 元, 红色 2 元, 蓝色 1 元, 现在要保证每一条白边相邻的有一条红边, 问至少花多少
题解: 刚开始想的时候, 好像觉得只用染红色和白色就够了? 乱搞一通就发现不对了
例如: 5 个点, 5 条边: 1 2, 2 3 , 3 4 , 4 5 , 5 2 . 如果只用红白, 则答案为 2 条红边, 2*2=4 但实际上, 如果 2 5 染红, 3 4 染蓝, 答案为 3
所以我们重新思考: 什么时候染蓝色?
我们假设一条边, 如果染了红色, 则他的 2 个端点, 就标记为红色, 如果我们枚举每个点是否红色 (2^20), 然后再看这个图
我们发现, 此时如果存在一条边的两个端点都没被染红, 那么把这条边染蓝更优.
所以我们利用状压, 枚举每个点染红的状态 (注意这个状态其实也是由边统计来的)
dp[i] 表示 i 集合为红的最小花费 dp[i+t]=dp[i]+2; t=i | (1<<u) | (1<<v) (其实 u,v 都要减一, 不过在读入的时候处理掉了)
然后再枚举每个状态, 看蓝色的花费, 统计出最小的答案
- #include<bits/stdc++.h>
- using namespace std;
- int n,m,a[45],b[45],f[1024*1024+10];
- int main()
- {
- scanf("%d%d",&n,&m);
- for (int i=1;i<=m;i++) scanf("%d%d",&a[i],&b[i]),a[i]--,b[i]--;
- int nn=1<<n;
- for (int i=0;i<nn;i++) f[i]=(int)1e8;
- f[0]=0;
- for (int i=0;i<nn;i++)
- {
- if (f[i]!=(int)(1e8))
- {
- for (int j=1;j<=m;j++)
- {
- int t=i|(1<<a[j])|(1<<b[j]);
- f[t]=min(f[t],f[i]+2);
- }
- }
- }
- int ans=(int)(1e8);
- for (int i=0;i<nn;i++)
- {
- int qq=f[i];
- for (int j=1;j<=m;j++)
- {
- if ((i>>a[j])%2==0 && (i>>b[j])%2==0) qq++;
- }
- ans=min(ans,qq);
- }
- cout<<ans<<endl;
- }
来源: http://www.bubuko.com/infodetail-3006703.html