POJ 3259

题意：一个图，有两种边，一种是双向边，权值为正，一种是单向边，权值为负。
问能否在图中找到一个负环。

分析：典型的找负环的题，但是这个题没有规定起点，所以直接从点1开始做bf是错误的。
bellman-ford算法可以判断一个从源点可达的环，那这个题需要做n次bf吗？
其实可以建立一个源，从源向每个图中的点引一条任意权值的边（不必为0），然后用bf就行了。
本质上就是初始化和经典的初始化不同，细节见代码。

/*
    POJ 3259
    code by heifrank
*/
#include <cstdio>
#include <vector>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;

const int MV = 505;

vector< pair<int, int> > G[MV];
int d[MV];

bool work(int n){
    for(int i=1; i<=n; i++)d[i] = 5;
    for(int i=1; i<n; i++){
        for(int j=1; j<=n; j++){
            for(int k=0; k<G[j].size(); k++){
                pair<int, int> v = G[j][k];
                if(d[v.first] > d[j] + v.second)
                    d[v.first] = d[j] + v.second;   
            }   
        }   
    }
    for(int i=1; i<=n; i++){
        for(int j=0; j<G[i].size(); j++){
            pair<int, int> v(G[i][j]);  
            if(d[v.first] > d[i] + v.second)return 0;
        }   
    }
    return 1;
}

int main(){
    int F, n, m, w, t, u, v;
    scanf("%d", &F);
    while(F--){
        scanf("%d%d%d", &n, &m, &w);
        for(int i=1; i<=n; i++)G[i].clear();
        for(int i=0; i<m; i++){
            scanf("%d%d%d", &u, &v, &t);
            G[u].push_back(make_pair(v, t));
            G[v].push_back(pair<int, int>(u, t));       
        }    
        for(int i=0; i<w; i++){
            scanf("%d%d%d", &u, &v, &t);
            G[u].push_back(make_pair(v, -t));   
        }
        if(work(n))puts("NO");
        else puts("YES");
    }
    return 0;   
}

Comments

Pages

Categories

Tags