http://acm.hdu.edu.cn/showproblem.php?pid=1317

题意:

给出一个有向图,每到达一个点,都会加上或减去一些能量,我们要做的就是判断从1出发是否能到达n。初始能量有100,行走的途中能量不能小于等于0。

思路:

首先我们用floyd来判断一下1和n之间是否有通路。

其次就是bellman_ford算法来判正环了。

 #include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <cmath>
using namespace std; const int maxn = + ;
const int INF = 0x3f3f3f3f; int n, m;
int power[];
int d[][];
int en[];
int cnt; struct node
{
int s, e;
}edge[maxn]; void floyd()
{
for (int k = ; k <= n; k++)
for (int i = ; i <= n; i++)
for (int j = ; j <= n; j++)
{
d[i][j] = d[i][j] || (d[i][k] && d[k][j]);
}
} bool bellman_ford()
{
for (int i = ; i <= n; i++) en[i] = -INF;
en[] = ;
for (int i = ; i < n; i++)
{
bool flag = false;
for (int j = ; j <cnt; j++)
{
if (en[edge[j].e] < en[edge[j].s] + power[edge[j].e] && en[edge[j].s]+power[edge[j].e]>)
{
en[edge[j].e] = en[edge[j].s] + power[edge[j].e];
flag = true;
}
}
if (!flag) break;
}
for (int j = ; j < cnt; j++)
{
//这儿需要注意一下,判断正环的时候,这个正环必须能到达终点
if (en[edge[j].e] < en[edge[j].s] + power[edge[j].e] && en[edge[j].s] + power[edge[j].e]> && d[edge[j].e][n]) return true;
}
if (en[n] <= ) return false;
else return true;
} int main()
{
//freopen("D:\\input.txt", "r", stdin);
int v;
while (cin >> n && n != -)
{
memset(d, , sizeof(d));
cnt = ; for (int i = ; i <= n; i++)
{
scanf("%d%d", &power[i], &m);
while (m--)
{
scanf("%d", &v);
edge[cnt].s = i;
edge[cnt].e = v;
d[i][v] = ;
cnt++;
}
}
floyd(); //首先判断1到n是否连通
if (!d[][n])
{
printf("hopeless\n");
continue;
}
if (bellman_ford())
printf("winnable\n");
else
printf("hopeless\n");
}
}

最新文章

  1. Ubuntu 14.04 软件源服务器列表
  2. SQL调用存储过程
  3. windows直接安装
  4. Sky number
  5. android学习——环境搭建之HelloWorld
  6. oracle包概述(一)【weber出品】
  7. [week2]每周总结与工作计划
  8. 【HTTP 2】HTTP/2 协议概述(HTTP/2 Protocol Overview)
  9. WebView使用详解
  10. PHP图像处理:3D图纸、缩放、回转、剪下、水印(三)
  11. Ionic start 创建项目报错 Error with start undefined
  12. ASP.NET Core MVC上传、导入、导出知多少
  13. 前端DES加密
  14. dedecms 5.7 采集目标文章的发布时间 采集后变成当前本地时间
  15. linux权限管理之文件属性
  16. elasticssearch+kibanna入门(撰写中)
  17. Linux下创建可执行bin安装文件
  18. #define SIG_DFL ((void(*)(int))0)
  19. nodejs与Promise的思想碰撞
  20. MySQL(存储过程,支持事务操作)

热门文章

  1. select标签的onchange事件
  2. 部署软件RDMA的步骤
  3. 微信小游戏5.2.2 在子项目中使用EUI制作排行榜报错 wx.getFileSystemManager not function
  4. C# Global.asax文件里实现通用防SQL注入漏洞程序(适应于post/get请求)
  5. Android 动态设置控件高度
  6. SpringBoot系列教程起步
  7. Spring.Net的使用
  8. vue报错 vue-cli 引入 stylus 失败
  9. UIWebView中加载的网页尺寸太大,如何让网页适应屏幕大小 WebView加载HTML图片大小自适应与文章自动换行
  10. 代码处理 iOS 的横竖屏旋转