放牧代码和思想
专注自然语言处理、机器学习算法
    时间有限,只有GitHub上的issue能及时处理,大约每周末一次。另外,不要叫我楼主,谢谢。

POJ 3259 Wormholes 题解 《挑战程序设计竞赛》

POJ 3259 Wormholes

虫洞:农夫约翰有F个农场,每个农场有N块地,其间有M条路,W条时光隧道(时间倒流)。问是否可能回到过去?

2.5 它们其实都是“图”

最短路

依然很水很基础的 Bellman-Ford 判定负圈,什么都不用考虑,一个 Bellman-Ford 就结束了

#ifndef ONLINE_JUDGE
#pragma warning(disable : 4996)
#endif
#include <iostream>
using namespace std;

#define MAX_E (2500 + 200 + 16) * 2

// 从顶点from指向顶点to的权值为cost的边
struct edge
{
	int from, to, cost;
	edge(){}
	edge(int from, int to, int cost)
	{
		this->from = from;
		this->to = to;
		this->cost = cost;
	}
};

// 边
edge es[MAX_E];

// 最短距离
int d[MAX_E];
// V是顶点数,E是边数
int V, E;

// 是否存在负圈
bool find_negative_loop()
{
	memset(d, 0, sizeof(d));
	for (int i = 0; i < V; ++i)
	{
		for (int j = 0; j < E; ++j)
		{
			edge e = es[j];
			if (d[e.to] > d[e.from] + e.cost)
			{
				d[e.to] = d[e.from] + e.cost;
				// 如果更新了V次,则存在负圈
				if (i == V - 1)
				{
					return true;
				}
			}
		}
	}
	return false;
}

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	int F;
	cin >> F;
	while (F--)
	{
		int N, M, W;
		cin >> N >> M >> W;
		V = N;
		E = 0;
		for (int i = 0; i < M; ++i)
		{
			int from, to, cost;
			cin >> from >> to >> cost;
			--from;
			--to;
			es[E].from = from;
			es[E].to = to;
			es[E].cost = cost;
			++E;
			// 无向图再来一次
  			es[E].from = to;
  			es[E].to = from;
  			es[E].cost = cost;
  			++E;
		}
		for (int i = 0; i < W; ++i)
		{
			int from, to, cost;
			cin >> from >> to >> cost;
			--from;
			--to;
			es[E].from = from;
			es[E].to = to;
			es[E].cost = -cost;
			++E;
		}
		if (find_negative_loop())
		{
			cout << "YES" << endl;
		}
		else
		{
			cout << "NO" << endl;
		}
	}
#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	system("out.txt");
#endif
	return 0;
}
///////////////////////////End Sub//////////////////////////////////

知识共享许可协议 知识共享署名-非商业性使用-相同方式共享码农场 » POJ 3259 Wormholes 题解 《挑战程序设计竞赛》

分享到:更多 ()

评论 3

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
  1. #2

    lz的答案WA了啊

    shicheng3年前 (2015-06-12)回复
  2. #1

    不对啊,万一有多个连通分量呢。。。

    下雨了冒泡了4年前 (2015-03-11)回复
    • 哦,知道了,检查负环的代码和普通的Bellman-Ford有区别

      下雨了冒泡了4年前 (2015-03-11)回复

我的开源项目

HanLP自然语言处理包基于DoubleArrayTrie的Aho Corasick自动机