POJ 3259 Wormholes

Description

农夫有T个农场，对应T组测试样例

每个农场有N块地，M条双向路，W条单向负权路（原文指走这条路时光回到之前）

问是否存在负权回路

题目链接

Bellman_Ford

#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 10005;///数组3005都算开小了...
const int INF = 0x3f3f3f3f;

struct node
{
    int from, to, w;
}a[N];

int n, m, w, cnt, dis[N];

void add(int from, int to, int w)
{
    a[cnt].from = from;
    a[cnt].to = to;
    a[cnt].w = w;
    cnt++;
}

bool Bellman_Ford(int start)
{
    dis[start] = 0;
    int tot = n;
    while(tot--)
    {
        bool flag = 0;
        for(int i = 0; i < cnt; ++i)
        {
            if(dis[ a[i].to ] > dis[ a[i].from ] + a[i].w)
            {
                flag = 1;
                dis[ a[i].to ] = dis[ a[i].from ] + a[i].w;
            }
        }
        if(flag == 0)
            break;
    }
    for(int i = 0; i < cnt; ++i)
        if(dis[ a[i].to ] > dis[ a[i].from ] + a[i].w)
        return 0;
    return 1;
}

int main()
{
    int t, there, here, val;
    scanf("%d", &t);
    while(t--)
    {
        memset(dis, INF, sizeof(INF));
        cnt = 0;
        scanf("%d%d%d", &n, &m, &w);
        for(int i = 0; i < m; ++i)
        {
            scanf("%d%d%d", &there, &here, &val);
            add(there, here, val);
            add(here, there, val);
        }
        for(int i = 0; i < w; ++i)
        {
            scanf("%d%d%d", &there, &here, &val);
            add(there, here, -val);
        }
        bool ans = 0;
        for(int i = 1; i <= n; ++i)
            if(Bellman_Ford(i) == 0)
            {
                ans = 1;
                break;
            }
        if(ans)
            cout << "YES" << '\n';
        else
            cout << "NO" << '\n';
    }
    return 0;
}

Floyd

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int INF = 0x3f3f3f3f;

int n, m, w;
int mp[510][510];

void floyd()
{
    bool flag = 0;
    for(int k = 1; k <= n; ++k)/// 又写成了 ++i
    {
        for(int i = 1; i <= n; ++i)
        {
            for(int j = 1; j <= n; ++j)
            {
                if(mp[i][j] > mp[i][k] + mp[k][j])
                    mp[i][j] = mp[i][k] + mp[k][j];
    ///本想用下面这句话提前结束循环
    ///后来发现这句话本身的耗时多于提前终结所省的时间
//                if(i == j && mp[i][j] < 0
//                {
//                    flag = 1;
//                    break;
//                }
            }
//            if(flag)
//                break;
            if(mp[i][i] < 0)
            {
                flag = 1;
                break;
            }
        }
        if(flag)
            break;
    }
    if(flag)
        cout << "YES" << '\n';
    else
        cout << "NO" << '\n';
}

int main()
{
    int t, there, here, val;
    scanf("%d", &t);
    while(t--)
    {
        scanf("%d%d%d", &n, &m, &w);
        for(int i = 1; i <= n; ++i)
            for(int j = 1; j <= n; ++j)
                mp[i][j] = (i == j ? 0 : INF);
        for(int i = 0; i < m; ++i)
        {
            scanf("%d%d%d", &there, &here, &val);
            if(mp[there][here] > val)
                mp[there][here] = mp[here][there] = val;
        }
        for(int i = 0; i < w; ++i)
        {
            scanf("%d%d%d", &there, &here, &val);
            mp[there][here] = -val;
        }
        floyd();
    }
    return 0;
}