首页 > 代码库 > HDU 4640 Island and study-sister（状态压缩）

HDU 4640 Island and study-sister（状态压缩）

2024-07-09 00:14:59   215人阅读

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4640

题意：给出一个无向图，边有权值。三个人初始时呆在1号点。在其余n-1个点中有些点要求被遍历到。且除了1号点之外每个点最多只能被一个人遍历。求要求被遍历的点中最后被遍历的点的最小时刻。

思路：用f[st][i]表示一个人遍历完集合st最后停在i的最小时间，之后用f[st][i]得到f1[st]，表示遍历完集合st的最小时间。然后得到dp[i][st]表示i个人遍历完st的最小时间。

 

int g[N][N],n,m,K,st;int f[1<<N][N],dp[4][1<<N];int f1[1<<N];struct node{    int st,x;        node(){}    node(int _st,int _x)    {        st=_st;        x=_x;    }};int visit[1<<N][N];void init(){    int i,j,k;    FOR0(i,(1<<n)) FOR0(j,n) f[i][j]=INF,visit[i][j]=0;    f[1][0]=0;    queue<node> Q;    Q.push(node(1,0));        while(!Q.empty())    {        node u=Q.front();        Q.pop();                visit[u.st][u.x]=0;        FOR0(i,n) if(f[u.st|(1<<i)][i]>f[u.st][u.x]+g[u.x][i])        {            f[u.st|(1<<i)][i]=f[u.st][u.x]+g[u.x][i];            if(!visit[u.st|(1<<i)][i])            {                visit[u.st|(1<<i)][i]=1;                Q.push(node(u.st|(1<<i),i));            }        }    }    FOR0(i,(1<<n)) f1[i]=INF;    FOR0(i,(1<<n)) FOR0(j,n) upMin(f1[i],f[i][j]);        FOR0(i,4) FOR0(j,(1<<n)) dp[i][j]=INF;    FOR0(i,(1<<n)) dp[1][i]=f1[i];    for(i=2;i<=3;i++) for(j=0;j<(1<<n);j++)    {        k=j;        while(k)        {            upMin(dp[i][j],max(dp[1][k|1],dp[i-1][(j^k)|1]));            k=(k-1)&j;        }    }}int main(){    int num=0;    rush()    {        RD(n,m);        int i,j,k,w;        FOR0(i,n) FOR0(j,n) g[i][j]=INF;        FOR0(i,n) g[i][i]=0;        FOR0(i,m)        {            RD(j,k,w);j--;k--;            if(g[j][k]>w) g[j][k]=g[k][j]=w;        }        st=1;        RD(K);        FOR0(i,K) RD(j),j--,st|=1<<j;        printf("Case %d: ",++num);        init();        int ans=INF;        FOR1(i,3) FOR0(j,(1<<n)) if((j&(st))==st)        {            upMin(ans,dp[i][j]);        }        if(ans==INF) ans=-1;        PR(ans);    }}

 

 

 


联系
我们