题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4284
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std; const int maxn = ;
const int maxm = ;
const int INF = 0x3f3f3f3f; int dp[maxm][<<maxm]; //dp[i][S],当前在i,访问完S中的点还剩的最大money数。最后判断是不是大于等于0.
int dist[maxn][maxn]; //dist[i][j] 表示从i到j,所需的最小花费。
int N,M,Money,H;
int C[maxm],D[maxm];
int Must[maxm]; int main()
{
//freopen("E:\\acm\\input.txt","r",stdin);
int T;
cin>>T;
while(T--){
cin>>N>>M>>Money; for(int i=;i<=N;i++)
for(int j=;j<=N;j++)
dist[i][j] = INF;
for(int i=;i<=N;i++) dist[i][i] = ;
for(int i=;i<=M;i++){
int u,v,w;
scanf("%d %d %d",&u,&v,&w);
if(dist[u][v] > w)
dist[u][v] = dist[v][u] = w; //这个地方没考虑。
} cin>>H;
for(int i=;i<H;i++)
scanf("%d %d %d",&Must[i],&C[i],&D[i]); for(int k=;k<=N;k++)
for(int i=;i<=N;i++)
if(dist[i][k] < INF){
for(int j=;j<=N;j++){
if(dist[k][j] < INF){
dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j]);
}
}
} memset(dp,-0x3f,sizeof(dp));
for(int i=;i<H;i++){
if(Money -dist[][Must[i]]- D[i]>=)
dp[i][<<i] = Money - dist[][Must[i]] - D[i] + C[i];
} int All = (<<H) - ; //这个地方WA
for(int S=;S<=All;S++){ //理解偏差;
for(int i=;i<H;i++){
if(!((<<i)&S) || dp[i][S] < ) continue; for(int j=;j<H;j++){
if(((<<j)&S) || i == j ) continue;
if(dp[i][S] - dist[Must[i]][Must[j]]- D[j] >= ){
dp[j][<<j|S] = max(dp[j][<<j|S] , dp[i][S] - dist[Must[i]][Must[j]] - D[j] + C[j]);
}
}
}
} bool flag = false;
for(int i=;i<H;i++){
if(dp[i][All] - dist[Must[i]][] >= ){
flag = true; break;
}
} if(flag) printf("YES\n");
else printf("NO\n");
}
}
hdu 4284 状态压缩的更多相关文章
-
hdu 4284 状态压缩dp
题意: 有N 个点的无向图,要去其中 h个地点做事,做事需要先办理护照,之后可以挣一定数量的钱,知道了一开始有的总钱数,和 一些城市之间 道路的花费,问可不可以在 指定的 h 个城 ...
-
HDU 1074 (状态压缩DP)
题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=1074 题目大意:有N个作业(N<=15),每个作业需耗时,有一个截止期限.超期多少天就要扣多少 ...
-
hdu 4739(状态压缩)
题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=4739 思路:状态压缩. #include<iostream> #include<cs ...
-
HDU 3341 状态压缩DP+AC自动机
题目大意: 调整基因的顺序,希望使得最后得到的基因包含有最多的匹配串基因,使得所能达到的智商最高 这里很明显要用状态压缩当前AC自动机上点使用了基因的情况所能达到的最优状态 我最开始对于状态的保存是, ...
-
hdu 2167(状态压缩基础题)
题意:给你一个矩阵,让你在矩阵中找一些元素使它们加起来和最大,但是当你使用某一个元素时,那么这个元素周围的其它八个元素都不能取! 分析:这是一道比较基础的状态压缩题,也是我做的第三道状态压缩的题,但是 ...
-
hdu 1565(状态压缩基础题)
题意:容易理解. 分析:这是我做的状态压缩第二题,一开始超内存了,因为数组开大了,后来超时了,因为能够成立的状态就那么多,所以你应该先把它抽出来!!总的来说还是比较简单的!! 代码实现: #inclu ...
-
HDU 2553 状态压缩
N皇后问题 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submi ...
-
hdu 3006(状态压缩)
The Number of set Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others ...
-
hdu 2489(状态压缩+最小生成树)
Minimal Ratio Tree Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Other ...
随机推荐
-
IEnumerable和IQueryable和Linq的查询
IEnumerable和IEnumerable 1.IEnumerable查询必须在本地执行.并且执行查询前我们必须把所有的数据加载到本地.而且更多的时候.加载的数据有大量的数据是我们不需要的无效数据 ...
-
SVN迁项目
next -> 做为新项目检出,finish -> next -> finish -> 否,是
-
Linked List Start!
(1)Delete Node in a Linked List 题意简单明了,用后一个节点来替换要删除的节点即可.代码如下: /** * Definition for singly-linked li ...
-
python实现简单随机模拟——抛呀抛硬币
还是在上次提到的数据之魅那本书,看到模拟这章,有个python模拟脚本,但书上不全,就自己简单写了下. 流程:在不同的平衡参数p(为0.5时为均匀的)下,模拟60次实验,每次投硬币8次,统计正面朝上的 ...
-
【BZOJ】【1202】【HNOI2005】狡猾的商人
Orz iwtwiioi http://www.cnblogs.com/iwtwiioi/p/3887617.html 并查集+前缀和 啊……这题应该是水题吧?但是我这个大沙茶居然一天都没想出来…… ...
-
【网络流24题】 No.2 太空飞行计划问题 (最大闭合权图 最大流 )
原题: W教授正在为国家航天中心计划一系列的太空飞行.每次太空飞行可进行一系列商业性实验而获取利润.现已确定了一个可供选择的实验集合 E={E1,E2,...,Em},和进行这些实验需 ...
-
WORLD OPERATS
word文章设置无法复制 通常我们会采用设置密码的方式,规定某个文档的使用范围. 但这种方法是有一个局限,那就是可以观看文档的人未必靠谱,万一复制了文档的重要内容怎么办? 因此,不妨考虑加上禁 ...
-
Sublime Text 3下C/C++开发环境搭建
Sublime Text 3下C/C++开发环境搭建 之前在Linux Mint 17一周使用体验中简单介绍过Sublime Text. 1.Sublime Text 3安装 Ubuntu.Linux ...
-
PHP循环语句深度理解分析——while, for, foreach, do while
循环结构 一.while循环 while(表达式) { 循环体;//反复执行,直到表达式为假 } 代码: $index = 1; while ($index<5) { ...
-
Python——开发一个自动化微信投票器【附代码实例方法】
一个研究Python实践,最近研究一个投票的东东,主要是想测试利用Python实现刷微信投票. 本文纯粹为了记录一下 webdriver直接操作页面按钮的方法: #!/usr/bin/python # ...