HDU 1317 XYZZY Bellman-Ford求最长路 判断正环

2024-06-15 11:58

本文主要是介绍HDU 1317 XYZZY Bellman-Ford求最长路 判断正环,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题意:给你n个房间 开始有能量值100 判断能否从1到第n个房间

每到一个房间可以获得能量x(可能小于0)  每到一个房间总能量必须大于0 每个房间可以重复到达

思路:求一个从1到n的最长路 不过可能有正环 没有正环 直接求最长路 如果有正环 判断环中的点是否可以到达n

具体用Bellman-Ford算法 虽然复杂度是(n*m)这题应该可以了 如果迭代n-1次之后还能松弛 说明有正环 然后用floyd判断是否可达

#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
const int maxn = 110;
struct edge
{int u, v, w;
};vector <edge> G;
int dis[maxn];
bool vis[maxn];
int n, m;
int a[maxn][maxn];
void floyd()
{for(int k = 1; k <= n; k++)for(int i = 1; i <= n; i++)for(int j = 1; j <= n; j++)a[i][j] = a[i][j] || (a[i][k] && a[k][j]);}
bool Bellman_Ford()
{for(int i = 1; i <= n; i++)dis[i] = -999999999;dis[1] = 100;for(int i = 1; i < n; i++){for(int j = 0; j < G.size(); j++){edge e = G[j];if(dis[e.v] < dis[e.u] + e.w && dis[e.u] + e.w > 0)dis[e.v] = dis[e.u] + e.w;	}}//printf("%d\n", dis[n]);if(dis[n] > 0)return true;for(int i = 0; i < G.size(); i++){edge e = G[i];if(dis[e.v] < dis[e.u] + e.w && dis[e.u] + e.w > 0){//puts("sss");dis[e.v] = dis[e.u] + e.w;	if(a[e.v][n])return true;}}return false;
}
int main()
{while(scanf("%d", &n) && n != -1){//for(int i = 0; i <= n; i++)G.clear();memset(a, 0, sizeof(a));for(int i = 1; i <= n; i++){int t, v, w;scanf("%d %d", &w, &t);while(t--){scanf("%d", &v);G.push_back((edge){i, v, w});//G.push_back((edge){v, i, w});a[i][v] = 1;//a[v][i] = 1;//G[v].push_back((edge){u, w});}}floyd();if(Bellman_Ford())puts("winnable");elseputs("hopeless");}return 0;
}


 

这篇关于HDU 1317 XYZZY Bellman-Ford求最长路 判断正环的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1063390

相关文章

C++实现回文串判断的两种高效方法

《C++实现回文串判断的两种高效方法》文章介绍了两种判断回文串的方法:解法一通过创建新字符串来处理,解法二在原字符串上直接筛选判断,两种方法都使用了双指针法,文中通过代码示例讲解的非常详细,需要的朋友... 目录一、问题描述示例二、解法一:将字母数字连接到新的 string思路代码实现代码解释复杂度分析三、

Java判断多个时间段是否重合的方法小结

《Java判断多个时间段是否重合的方法小结》这篇文章主要为大家详细介绍了Java中判断多个时间段是否重合的方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录判断多个时间段是否有间隔判断时间段集合是否与某时间段重合判断多个时间段是否有间隔实体类内容public class D

最长公共子序列问题的深度分析与Java实现方式

《最长公共子序列问题的深度分析与Java实现方式》本文详细介绍了最长公共子序列(LCS)问题,包括其概念、暴力解法、动态规划解法,并提供了Java代码实现,暴力解法虽然简单,但在大数据处理中效率较低,... 目录最长公共子序列问题概述问题理解与示例分析暴力解法思路与示例代码动态规划解法DP 表的构建与意义动

关于最长递增子序列问题概述

《关于最长递增子序列问题概述》本文详细介绍了最长递增子序列问题的定义及两种优化解法:贪心+二分查找和动态规划+状态压缩,贪心+二分查找时间复杂度为O(nlogn),通过维护一个有序的“尾巴”数组来高效... 一、最长递增子序列问题概述1. 问题定义给定一个整数序列,例如 nums = [10, 9, 2

Python判断for循环最后一次的6种方法

《Python判断for循环最后一次的6种方法》在Python中,通常我们不会直接判断for循环是否正在执行最后一次迭代,因为Python的for循环是基于可迭代对象的,它不知道也不关心迭代的内部状态... 目录1.使用enuhttp://www.chinasem.cnmerate()和len()来判断for

如何测试计算机的内存是否存在问题? 判断电脑内存故障的多种方法

《如何测试计算机的内存是否存在问题?判断电脑内存故障的多种方法》内存是电脑中非常重要的组件之一,如果内存出现故障,可能会导致电脑出现各种问题,如蓝屏、死机、程序崩溃等,如何判断内存是否出现故障呢?下... 如果你的电脑是崩溃、冻结还是不稳定,那么它的内存可能有问题。要进行检查,你可以使用Windows 11

poj3261(可重复k次的最长子串)

题意:可重复k次的最长子串 解题思路:求所有区间[x,x+k-1]中的最小值的最大值。求sa时间复杂度Nlog(N),求最值时间复杂度N*N,但实际复杂度很低。题目数据也比较水,不然估计过不了。 代码入下: #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstring

usaco 1.3 Mixing Milk (结构体排序 qsort) and hdu 2020(sort)

到了这题学会了结构体排序 于是回去修改了 1.2 milking cows 的算法~ 结构体排序核心: 1.结构体定义 struct Milk{int price;int milks;}milk[5000]; 2.自定义的比较函数,若返回值为正,qsort 函数判定a>b ;为负,a<b;为0,a==b; int milkcmp(const void *va,c

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

hdu 2093 考试排名(sscanf)

模拟题。 直接从教程里拉解析。 因为表格里的数据格式不统一。有时候有"()",有时候又没有。而它也不会给我们提示。 这种情况下,就只能它它们统一看作字符串来处理了。现在就请出我们的主角sscanf()! sscanf 语法: #include int sscanf( const char *buffer, const char *format, ... ); 函数sscanf()和