牛客竞赛题目讲解_宝藏(noip)
// https://ac.nowcoder.com/acm/problem/16418
#include "stdafx.h"
//#include <bits/stdc++.h>
#include <algorithm>
#include <iostream>
using namespace std;
const int maxn=12;
int d[maxn+5][maxn+5];
int f[maxn+5][(1<<maxn)+5];
int dis[(1<<maxn)+5][(1<<maxn)+5];
int lg[(1<<maxn)+5];//预处理，求对数
int q[(1<<maxn)+5],cnt;
int edge[32][3]={
1, 2, 1,
1, 3, 3,
1 ,4, 1,
2, 3, 4,
3, 4, 2,
3,5,1,
5,6,5
};
int main()
{
memset(f,1,sizeof f);
//ios::sync_with_stdio(0);
//cin.tie(0),cout.tie(0);
int n,m;
n=6,m=7;
//cin>>n>>m;
for(int i=0;i<n;++i)
lg[1<<i]=i;//预处理，求对数
for(int i=0;i<12;++i)
for(int j=0;j<12;++j)
d[i][j]=1000000;//赋最大值
for(int i=1;i<=m;++i)
{
int a,b,c;
//cin>>a>>b>>c;
a=edge[i-1][0];
b=edge[i-1][1];
c=edge[i-1][2];
--a,--b,d[a][b]=d[b][a]=min(d[a][b],c);
}
/*
T={1,2,3,4,5}
21= 10101 表示子集 {1，3，5}
*/
int S=(1<<n)-1;//全集定义
for(int i=1;i<=S;++i)
{
cnt=0;
for(int j=S^i;j;j=(j-1)&(S^i)) q[++cnt]=j;//由于这样做子集的顺序是从大到小的，不符合DP的顺序，所以要逆序
for(int j=cnt;j>=1;--j)
{
int u=lg[q[j]&-q[j]],e=1000000;
for(int v=0;v<n;++v)
if(1<<v&i) e=min(d[u][v],e);// 集合i包含顶点v
dis[i][q[j]]=dis[i][q[j]^(q[j]&-q[j])]+e;// 集合i到其补集合的子集的距离
}
}
for(int i=0;i<n;++i) f[1][1<<i]=0;//初始状态
for(int i=2;i<=n;++i)
for(int j=(1<<i)-1;j<=S;++j)
{
/*
新开发一条道路的代价是： L × K
L 代表这条道路的长度，K 代表从赞助商帮你打通的宝藏屋到这条道路起点的宝藏屋所经过的 宝藏屋的数量
（包括赞助商帮你打通的宝藏屋和这条道路起点的宝藏屋） 。
*/
for(int k=j;k;k=(k-1)&j)// 遍历所有 集合j的子 集合
{// j^k 与 k 合起来就是集合j
f[i][j]=min(f[i][j],f[i-1][j^k]+dis[j^k][k]*(i-1));
if(i==5 && j==S&& f[i-1][j^k]==13)
{
cout<<"j="<<j<<", k="<<k<<", j^k="<<(j^k);
cout<<",,,f[i][j]="<<f[i][j]<<", f[i-1][j^k]="<<f[i-1][j^k]<<", dis[j^k][k]="<<dis[j^k][k]<<endl;
}
}
}
int ans=(1<<30);
for(int i=1;i<=n;++i)
{
ans=min(ans,f[i][S]);//取最小值
cout<<",,"<<f[i][S]<<endl;
}
cout<<ans<<endl;
return 0;
}
