首页 > 代码库 > HDU 1317 XYZZY（floyd+bellman_ford判环）
HDU 1317 XYZZY（floyd+bellman_ford判环）
http://acm.hdu.edu.cn/showproblem.php?pid=1317
题意：
给出一个有向图，每到达一个点，都会加上或减去一些能量，我们要做的就是判断从1出发是否能到达n。初始能量有100，行走的途中能量不能小于等于0。
思路：
首先我们用floyd来判断一下1和n之间是否有通路。
其次就是bellman_ford算法来判正环了。
1 #include <iostream> 2 #include <cstring> 3 #include <algorithm> 4 #include <vector> 5 #include <queue> 6 #include <cmath> 7 using namespace std; 8 9 const int maxn = 10000 + 5;10 const int INF = 0x3f3f3f3f;11 12 int n, m;13 int power[105];14 int d[105][105];15 int en[105];16 int cnt;17 18 struct node19 {20 int s, e;21 }edge[maxn];22 23 void floyd()24 {25 for (int k = 1; k <= n; k++)26 for (int i = 1; i <= n; i++)27 for (int j = 1; j <= n; j++)28 {29 d[i][j] = d[i][j] || (d[i][k] && d[k][j]);30 }31 }32 33 bool bellman_ford()34 {35 for (int i = 1; i <= n; i++) en[i] = -INF;36 en[1] = 100;37 for (int i = 1; i < n; i++)38 {39 bool flag = false;40 for (int j = 0; j <cnt; j++)41 {42 if (en[edge[j].e] < en[edge[j].s] + power[edge[j].e] && en[edge[j].s]+power[edge[j].e]>0)43 {44 en[edge[j].e] = en[edge[j].s] + power[edge[j].e];45 flag = true;46 }47 }48 if (!flag) break;49 }50 for (int j = 0; j < cnt; j++)51 {52 //这儿需要注意一下，判断正环的时候，这个正环必须能到达终点53 if (en[edge[j].e] < en[edge[j].s] + power[edge[j].e] && en[edge[j].s] + power[edge[j].e]>0 && d[edge[j].e][n]) return true;54 }55 if (en[n] <= 0) return false;56 else return true;57 }58 59 60 int main()61 {62 //freopen("D:\\input.txt", "r", stdin);63 int v;64 while (cin >> n && n != -1)65 {66 memset(d, 0, sizeof(d));67 cnt = 0;68 69 for (int i = 1; i <= n; i++)70 {71 scanf("%d%d", &power[i], &m);72 while (m--)73 {74 scanf("%d", &v);75 edge[cnt].s = i;76 edge[cnt].e = v;77 d[i][v] = 1;78 cnt++;79 }80 }81 floyd(); //首先判断1到n是否连通82 if (!d[1][n])83 {84 printf("hopeless\n");85 continue;86 }87 if (bellman_ford())88 printf("winnable\n");89 else90 printf("hopeless\n");91 }92 }
HDU 1317 XYZZY（floyd+bellman_ford判环）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。