题目连接

http://poj.org/problem?id=3259

思路

大概是想问我们能不能找到一个负环，那么再看一眼数据范围，500，感觉乱搞都能过，但是出题人很恶心啊，n的范围并不是500，卡了巨久，但是用Floyd也是能过的，只不过写的时候要注意自己的常数，常数打了就过不了了，但是想到判负环我们应该联想到spfa和bellman算法，详情请看：spfa和bellman判负环,由于spfa算法是优化后的bellman所以我这里就不放bellman的代码了

代码

Floyd算法

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

const int INF = 0x3f3f3f3f;
const int N = 1e3+10;

int n,m,w;
int f[N][N];

bool floyd(){
	for(int k = 1;k <= n; ++k)
		for(int i = 1;i <= n; ++i){
			for(int j = 1;j <= n; ++j)
				if(f[i][j] > f[i][k] + f[k][j])
					f[i][j] = f[i][k] + f[k][j];
			if(f[i][i] < 0) return true;
		}
			
	return false;
}

void slove(){
	scanf("%d%d%d",&n,&m,&w);
	int u,v,k;
	for(int i = 1;i <= n; ++i)
		for(int j = 1;j <= n; ++j)
			f[i][j] = (i == j?0:INF);
	for(int i = 1;i <= m; ++i) {
		scanf("%d%d%d",&u,&v,&k);
		if(f[u][v] > k)
			f[u][v] = f[v][u] = k;
	}
	for(int i = 1;i <= w; ++i) {
		scanf("%d%d%d",&u,&v,&k);
		f[u][v] = -k;
	}
	
	if(floyd()) puts("YES");
	else puts("NO");
}

int main(){
	int t;
	scanf("%d",&t);
	while(t--)
		slove();
	return 0;
}

spfa算法

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
//----------------自定义部分----------------
#define ll long long
#define mod 1000000007
#define endl "\n"
#define PII pair<int,int>
#define INF 0x3f3f3f3f

int dx[4]={0,-1,0,1},dy[4]={-1,0,1,0};

ll ksm(ll a,ll b) {
	ll ans = 1;
	for(;b;b>>=1LL) {
		if(b & 1) ans = ans * a % mod;
		a = a * a % mod;
	}
	return ans;
}

ll lowbit(ll x){return -x & x;}

const int N = 2e6+10;
//----------------自定义部分----------------
int n,m,q,w;

vector<PII> E[N];
int dis[N],cnt[N];
bool vis[N];

void spfa(){
	queue<int> que;
	for(int i = 1;i <= n; ++i) que.push(i);
	while(!que.empty()){
		int t = que.front();
		que.pop();
		vis[t] = false;//表明t这个点已经离开这个队列了
		for(int i = 0,l = E[t].size();i < l; ++i) {
			int j = E[t][i].first,k = E[t][i].second;
			if(dis[j] > dis[t] + k) {
				dis[j] = dis[t] + k;
				cnt[j] = cnt[t] + 1;
				if(cnt[j] >= n) {//找到负环
					puts("YES");
					return;
				}
				if(!vis[j])//将j这个点重新加入队列
					que.push(j),vis[j] = true;
			}
		}
	}
	puts("NO");
}

void init(){
	for(int i = 1;i <= n; ++i) E[i].clear(),vis[i] = true,cnt[i] = 0;
}

void slove(){
	scanf("%d%d%d",&n,&m,&w);
	init();
	int u,v,k;
	for(int i = 1;i <= m; ++i) {
		scanf("%d%d%d",&u,&v,&k);
		E[u].push_back({v,k});
		E[v].push_back({u,k});
	}
	for(int i = 1;i <= w; ++i){
		scanf("%d%d%d",&u,&v,&k);
		E[u].push_back({v,-k});
	}
	spfa();
}

int main()
{
	int t;
	scanf("%d",&t);
	while(t--) 
		slove();
	return 0;
}