POJ-3259 解题报告

题意简述

农夫共有F（1≤F≤5）个农场，每个农场有N块田（1 ≤ N ≤ 500）和M条普通无向路（1 ≤ M ≤ 2500），走过这些路需要一定时间。同时还存在W条有向虫洞（1 ≤ W ≤ 200），走这些虫洞可倒流一定时间。问对于各个农场，农夫是否有可能从某点出发，回到原点时时间早于出发时间。每个农场输出一行。可能则输出YES，否则为NO。

算法分析

这题可抽象为：对于F张图，每张图有M条权值为正的无向路和W条权值为负的有向路。问图中是否存在负权环。

处理时将无向路处理为两条有向路。

因为涉及负权，所以使用Bellman-Ford判断负权环即可。在处理过程中，为了避免非连通图造成的漏解，新建一个与所有节点都联通的节点并将它作为Bellman-Ford的起点。

关于Bellman-Ford和其余最短路算法，以后单独开一篇日志讨论~

Problem Status: AC。时间47ms，内存232k

程序样例

#include<stdio.h>

int bellman_ford(int n, int edge, int e[][3]) {
  int d[1001], i, j, flag;
  d[0] = 0;
  for (i = 1; i <= n; i++)
    d[i] = 10000000;
  for (i = 1; i < n; i++) {
    flag = 0;
    for (j = 0; j < edge; j++)
      if (d[e[j][1]] > d[e[j][0]] + e[j][2]) {
        d[e[j][1]] = d[e[j][0]] + e[j][2];
        flag = 1;
      }
    if (!flag) break;
  }
  for (j = 0; j < edge; j++)
    if (d[e[j][1]] > d[e[j][0]] + e[j][2])
      return 1;
  return 0;
}

int main() {
  int t, n, m, w, e[6000][3], i, edge;
  scanf("%d", &t);
  while (t > 0) {
    edge = 0;
    scanf("%d%d%d", &n, &m, &w);
    for (i = 1; i <= n; i++) {
      e[edge][0] = 0;
      e[edge][1] = i;
      e[edge][2] = 0;
      edge++;
    }
    for (i = 0; i < m; i++) {
      scanf("%d%d%d", &e[edge][0], &e[edge][1], &e[edge][2]);
      edge++;
      e[edge][0] = e[edge - 1][1];
      e[edge][1] = e[edge - 1][0];
      e[edge][2] = e[edge - 1][2];
      edge++;
    }
    for (i = 0; i < w; i++) {
      scanf("%d%d%d", &e[edge][0], &e[edge][1], &e[edge][2]);
      e[edge][2] = -e[edge][2];
      edge++;
    }

    if (bellman_ford(n, edge, e)) printf("YES\n");
    else printf("NO\n");

    t--;
  }
}