hdu 4640(状压dp）

时间：2022-06-13 21:27:44

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

思路：f[i][j]表示一个人状态i下走到j的最小花费，dp[i][j]表示i个人在状态j下的最下花费。首先我们可以一遍bfs求出f[i][j],然后通过f[i][j]得到dp[1][i],最后就是更新dp[i][j]了。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<queue>

 using namespace std;

 #define inf 1<<30

 typedef pair<int,int>PP;

 int map[][];

 int f[<<][];//派一个人去，在某状态下到达点v的最小花费

 int dp[][<<];//派i个人去，在某状态的最小花费

 bool mark[<<][];

 int n,m,S,ans;

 void bfs()

 {

     queue<PP>que;

     que.push(make_pair(,));

     memset(mark,false,sizeof(mark));

     for(int i=;i<(<<n);i++)

         for(int j=;j<n;j++)f[i][j]=inf;

     f[][]=;

     while(!que.empty()){

         PP p=que.front();

         que.pop();

         int s=p.first,u=p.second;

         mark[s][u]=false;

         for(int i=;i<n;i++){

             if(map[u][i]<inf&&f[s|(<<i)][i]>f[s][u]+map[u][i]){

                 f[s|(<<i)][i]=f[s][u]+map[u][i];

                 if(!mark[s|(<<i)][i]){

                     mark[s|(<<i)][i]=true;

                     que.push(make_pair(s|(<<i),i));

                 }

             }

         }

     }

 }

 void Solve()

 {

     for(int i=;i<=;i++)

         for(int j=;j<(<<n);j++)dp[i][j]=inf;

     for(int i=;i<(<<n);i++)

         for(int j=;j<n;j++)dp[][i]=min(dp[][i],f[i][j]);

     for(int i=;i<=;i++){

         for(int j=;j<(<<n);j++){

             //枚举子集

             for(int k=j;k;k=(k-)&j){

                 dp[i][j]=min(dp[i][j],max(dp[][k|],dp[i-][(j^k)|]));

             }

         }

     }

     ans=inf;

     for(int i=;i<=;i++)

         for(int j=;j<(<<n);j++)if((j&S)==S)ans=min(ans,dp[i][j]);

     if(ans==inf)ans=-;

     printf("%d\n",ans);

 }

 int main()

 {

     int _case,u,v,w,k,t=;

     scanf("%d",&_case);

     while(_case--){

         scanf("%d%d",&n,&m);

         for(int i=;i<=n;i++)

             for(int j=;j<=n;j++)map[i][j]=(i==j?:inf);

         while(m--){

             scanf("%d%d%d",&u,&v,&w);

             u--,v--;

             map[u][v]=map[v][u]=min(map[u][v],w);

         }

         S=;

         scanf("%d",&k);

         while(k--){

             scanf("%d",&u);

             u--;

             S|=(<<u);

         }

         bfs();

         printf("Case %d: ",t++);

         Solve();

     }

     return ;

 }

相关文章