题目链接:http://poj.org/problem?id=3259
题意是有n个点,m条边,k个虫洞(权值为负),输入完m条无向边后输入k条有向边,问能不能找到一个点,从这个点出发,最后回到这个点的时候权值是负的(时光倒流)。
首先这个可以用Floyd去跑一遍,然后遍历每个点看看有没有能得到负权的点,想看Floyd做法的可以看看这篇博客:POJ 3259 Wormholes(Floyd判负环),这篇博客是用spfa去跑的,从一个点出发,我们只需要看在这个图中有没有负环存在(就是一个环的权值和为负的),如果有的话,我们就可以以这个负环中的任意一点为起点,最终回来的时候就可以得到负的权值了。
AC代码:
#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#define maxn 505
#define inf 0x3f3f3f3f
using namespace std;
struct Node{
int to,w,next;
bool operator < (const Node &a) const{
return a.w < w;
}
}Edge[maxn * maxn];
int head[maxn * maxn],num;
int dist[maxn];
bool vis[maxn];
int T,n,m,k;
void init(){
memset(head,-1,sizeof(head));
num = 0;
}
void add(int u,int v,int w){
Edge[num].w = w;
Edge[num].to = v;
Edge[num].next = head[u];
head[u] = num ++;
}
bool spfa(){
int cnt[maxn];
memset(cnt,0,sizeof(cnt));
memset(dist,inf,sizeof(dist));
memset(vis,false,sizeof(vis));
dist[1] = 0;
cnt[1] = 1;
queue<int> q;
q.push(1);
while(!q.empty()){
int u = q.front();
q.pop();
vis[u] = false;
for(int i=head[u];i!=-1;i=Edge[i].next){
int v = Edge[i].to;
if(dist[v] > dist[u] + Edge[i].w){
dist[v] = dist[u] + Edge[i].w;
if(vis[v] == false){
cnt[v]++;
q.push(v);
vis[v] = true;
if(cnt[v] >= n){
return true;
}
}
}
}
}
return false;
}
int main()
{
scanf("%d",&T);
while(T--){
init();
scanf("%d%d%d",&n,&m,&k);
for(int i=0;i<m;i++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
add(u, v, w);
add(v, u, w);
}
for(int i=0;i<k;i++){
int u,v,w;
scanf("%d%d%d",&u,&v,&w);
add(u, v, -w);
}
if(spfa()){
puts("YES");
}
else{
puts("NO");
}
}
return 0;
}