poj 3259 Wormholes(bellman_ford)

 

解题思路

题意：

       John的农场里N块地，M条路连接两块地，W个虫洞，虫洞是一条单向路，会在你离开之前把你传送到目的地，就是当你过去的时候时间会倒退Ts。我们的任务是知道会不会在从某块地出发后又回来，看到了离开之前的自己。简化下，就是看图中有没有负权环。有的话就是可以，没有的话就是不可以了。

 

思路：

       这是学了bellman_ford算法后才去做这个题的，学了算法之后就觉得很简单了。根据每条路建无向图权为t，再根据每个虫洞，建单向的路，权为-t，一开始用的是邻接矩阵，tel了，然后在队友帮助下在bellmen_ford 里加了优化之后A了，不过时间是922ms，很不满意。然后建邻接阵，200多ms，减少了很多，以为还不错了，一看status发现0ms的都有的，而且大多是47ms跟63ms，显然我的是太差劲了，然后再想办法优化。用一个边数组存每条边,提交了几次一直是RE，没办法，只好去找数据，不仅找到数据还找到了标程，用数据测自己的程序都能过，然后就去提交标程，可是让我更郁闷的是标程让我的账号多了几个CR，而且时间还是300ms+，哎….标程也靠不住啊。  后来又看了遍题目，终于发现原来是边数组开小了，加大之后一交47MS! 惊喜啊~

  没事做写了一大堆废话，呵呵，每次进步一点点的感觉真好。

源程序

 

#include <stdio.h>
#include <string.h>
#include <conio.h>
#define N 505
#define inf 100000
int d[N];
int n, m;
typedef struct
{
    int x;
    int y;
    int w;
}edge;
edge edges[5300];
int bellman_ford(int m)
{
    int i, j, k, t;
    int ok;
    for(i=1; i<=n; i++)
        d[i] = inf;
    d[1] = 0;
    for(i=1; i<=n-1; i++)
    {
        ok = 1;
        for(j=1; j<=m; j++)
        {
            if(d[edges[j].x] > d[edges[j].y] + edges[j].w)
            {
                d[edges[j].x] = d[edges[j].y] + edges[j].w;
                ok = 0;
            }
        }
        if(ok) //优化在这里，如果这趟没跟新任何节点就可以直接退出了。
            break;
    }
    for(j=1; j<=m; j++)
    {
        if(d[edges[j].x] > d[edges[j].y] + edges[j].w)
            return 0;
    }
    return 1;
}

int main()
{
    int i, j, t, x;
    int a, b, c, w;

    freopen("in.txt", "r", stdin);
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d%d%d", &n, &m, &w);
        memset(edges, 0, sizeof(edges));
        for(i=0, j=1; j<=m;j++)
        {
            scanf("%d%d%d", &a, &b, &c);
            i++;
            edges[i].x = a;
            edges[i].y = b;
            edges[i].w = c;
            i++;
            edges[i].x = b;
            edges[i].y = a;
            edges[i].w = c;

        }
        for(j=1; j<=w; j++)
        {
            scanf("%d%d%d", &a, &b, &c);

            i++;
            edges[i].x = a ;
            edges[i].y = b;
            edges[i].w = -c;

        }
        if(bellman_ford(i))
            printf("NO\n");
        else
            printf("YES\n");
    }
    getch();
    return 0;
}