poj 3259

本文主要是介绍poj 3259，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

把 field 想象成一个图。如果要输出YES，则此图存在负圈。

使用Bellman-Ford算法，判断第 n 次是否仍然更新了。

使用Floyd-Warshall算法，判断是否有点的值小于原来的值。

Bellman-Ford算法：

#include <iostream>  
using namespace std;  
#define MAXM 2710  
#define MAXV 505  
#define inf 1<<29  struct{  int x,y,t;  
}edge[MAXM];  int n,m,w;  int bellman_ford(int ids){  int i,j,d[MAXV],flag=1,cnt=1;  for(i=1;i<=n;i++) d[i]=inf;  while(flag){  flag=0;  if(cnt++>n) return 1;  for(i=1;i<=ids;i++){  if(d[edge[i].x]+edge[i].t < d[edge[i].y]) {d[edge[i].y] = d[edge[i].x] + edge[i].t;flag = 1;}  }}  return 0;  
}  int main(){  int t,i;  scanf("%d",&t);  while(t--){  scanf("%d%d%d",&n,&m,&w); int ids = m + w + 1; for(i=1;i<=m;i++) {scanf("%d%d%d",&edge[i].x,&edge[i].y,&edge[i].t);edge[ids].x = edge[i].y;edge[ids].y = edge[i].x;edge[ids++].t = edge[i].t;} for(; i<=m+w; i++) {scanf("%d%d%d",&edge[i].x,&edge[i].y,&edge[i].t);edge[i].t = -edge[i].t;}if(bellman_ford(ids)) printf("YES\n");  else printf("NO\n");  }  return 0;  
}

这篇关于poj 3259的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---