hdu 4640(状压dp)
2024-08-28 00:50:53
题目链接: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 ;
}
最新文章
- repeater控件如何隐藏列?
- git超详细教程
- 108 vpn iptables
- JavaScript简易教程(转)
- [转]Android的Handler总结
- ..在lua中运用
- erlang 时间处理
- Hibernate总结--MyEclipse的小bug
- 【C++基础】 类中static private public protected
- DHTMLX 前端框架 建立你的一个应用程序 教程(十一)--添加/删除表格中的记录
- jquery插件----文件上传uploadfile
- Java中直接输出一个类的对象
- SSIS 阻塞,半阻塞和全阻塞 (Non-blocking, semi-blocking and Fully-blocking) transformations清单
- 掌握一门语言Go
- EBS 可拓展的外部信用风险导入
- (转)Java8内存模型—永久代(PermGen)和元空间(Metaspace)
- 【Sql Server】SQL SERVER 递归查询
- MyBatis笔记(二) 最简单的insert命令
- postman(十):配置jenkins自动发送邮件(邮件包含测试报告)
- 使用Pandas将多个数据表合一