欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

NOIP2017 Day2 T2 宝藏

程序员文章站 2024-03-20 12:55:40
...

1)状压DP写法

#include<bits/stdc++.h>
using namespace std;
const int INF=1e7;
const int N=13;
int sval[1<<N][1<<N];
int pval[N][1<<N];
int f[N][1<<N];
int ans=1e7;
int g[N][N];
int n,m,U;
void work(int root)
{
    for(int i=0;i<=n;i++)
    for(int j=1;j<=U;j++)
    f[i][j]=INF;
    f[0][1<<(root-1)] = 0;
}

void init()
{
	scanf("%d%d",&n,&m);
    U=(1<<n)-1;
    for(int i=0;i<=n;i++)
    for(int j=0;j<=n;j++)
    g[i][j]=INF;
    for(int i=1;i<=n;i++)
    for(int j=0;j<=U;j++)
    pval[i][j]=INF;
    for(int i=0;i<=U;i++)
    for(int j=0;j<=U;j++)
    sval[i][j]=INF; 
	for(int i=1;i<=m;i++)
	{
		int x,y,v;
        scanf("%d%d%d", &x,&y,&v);
        g[x][y]=g[y][x]=min(g[x][y],v);
    }
}
int main()
{
	init();
    for(int i=1;i<=n;i++)
    for(int j=1;j<=U;j++)
    for(int k=1;k<=n;k++)
    if(j&(1<<(k-1)))
    pval[i][j]=min(pval[i][j],g[i][k]);
    
    for(int i=1;i<=U;i++)
	{           
        int C=i^U;
        for(int s=C;s;s=(s-1)&C)
		{
    	    long long temp=0;
    	    for(int j=1;j<=n;j++)
    		if(s&(1<<(j-1)))
     	    temp+=pval[j][i];
     	    sval[s][i]=(temp>=INF)?INF:temp;
        }
    }
    
    for(int root=1;root<=n;root++)
	{  
        work(root);
        for(int i=0;i<=n;i++)
        for(int S=1;S<=U;S++)
        if(f[i][S]!=INF)
		{
            int C=S^U;
            for(int s=C;s;s=(s-1)&C)//枚举补集中的子集 
            f[i+1][S|s]=min(f[i+1][S|s],f[i][S]+(i+1)*sval[s][S]);
        }
        for(int i=0;i<n;i++)  
		ans=min(ans,f[i][U]);
    }
    printf("%d", ans);
    return 0;
}

2)状压+DFS写法

#include<bits/stdc++.h>
using namespace std;
int f[1<<13],dis[13],w[13][13];
int n,m,ans=9999999;
bool b[13][13];
inline void read(int x,int y,int v)
{
    w[x][y]=w[y][x]=v;
    b[x][y]=b[y][x]=1;
}
void init()
{
    memset(w,0x3f,sizeof(w));
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {
        int x,y,v;
        scanf("%d%d%d",&x,&y,&v);
        if(v<w[x][y]) read(x,y,v);
    }
}

void dfs(int x)
{
    for(int i=1;i<=n;i++)
    {
        if((1<<(i-1))&x)
        for(int j=1;j<=n;j++)
        {
            if(!(1<<(j-1)&x)&&1==b[i][j])
            if(f[(1<<(j-1))|x]>f[x]+dis[i]*w[i][j])
            {
                int temp=dis[j];
                dis[j]=dis[i]+1;
                f[(1<<(j-1))|x]=f[x]+dis[i]*w[i][j];
                dfs((1<<(j-1))|x);
                dis[j]=temp;
            }
        }
    }
}
int main()
{
    init();
    for(int i=1;i<=n;i++)
    {
        memset(dis,0x3f,sizeof(dis));
        memset(f,0x3f,sizeof(f));
        dis[i]=1;
        f[1<<(i-1)]=0;
        dfs(1<<(i-1));
        ans=min(ans,f[(1<<n)-1]);
    }
    printf("%d",ans);
    return 0;
}