题意简述

农夫共有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

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;id[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;jd[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