放牧代码和思想
专注自然语言处理、机器学习算法
    恕不接待索要源码语料者、索求技术方案者、以及不Google的懒人。

POJ 3268 Silver Cow Party 题解 《挑战程序设计竞赛》

POJ 3268 Silver Cow Party

奶牛派对:有分别来自 N 个农场的 N 头牛去农场 X 嗨皮,农场间由 M 条有向路径连接。每头牛来回都挑最短的路走,求它们走的路的最大长度?

2.5 它们其实都是“图”

最短路 dijkstra 解决任意两点最短路的变种

用warshall_floyd的话会TLE,10003复杂度果然不是盖的,另外X的编号记得减一,测试用例很恶心的,即使忘了减一也照样得出正确答案10,但是一提交就WA,让我深深地感到了来自命题者的恶意:

#ifndef ONLINE_JUDGE
#pragma warning(disable : 4996)
#endif
#include <iostream>
#include <algorithm>
using namespace std;
#define MAX_V 1024
int d[MAX_V][MAX_V];	//	d[u][v]表示边e=(u,v)的权值,不存在的时候等于无穷大或者d[i][i] = 0
int V;					//	顶点数

void warshall_floyd()
{
	for (int k = 0; k < V; ++k)
	{
		for (int i = 0; i < V; ++i)
		{
			for (int j = 0; j < V; ++j)
			{
				d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
			}
		}
	}
}

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	int M, X;
	cin >> V >> M >> X;
	--X
	memset(d, 0x3f, V * MAX_V * sizeof(int));
	for (int i = 0; i < V; ++i)
	{
		d[i][i] = 0;
	}
	while (M--)
	{
		int A, B, T;
		cin >> A >> B >> T;
		--A;
		--B;
		d[A][B] = T;
	}
	warshall_floyd();
	int ans = 0;
	for (int i = 0; i < V; ++i)
	{
		ans = max(ans, d[i][X] + d[X][i]);
	}
	cout << ans << endl;
#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	system("out.txt");
#endif
	return 0;
}
///////////////////////////End Sub//////////////////////////////////

dijkstra是解决单源最短路问题的,稍微修改一下就可以支持任意两点最短路:

#ifndef ONLINE_JUDGE
#pragma warning(disable : 4996)
#endif
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <functional>
using namespace std;
#define MAX_V 1024

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

// first 最短路径,second顶点编号
typedef pair<int, int> P;

// 图
vector<edge>  G[MAX_V];

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

// 求解从顶点s出发到所有点的最短距离
void dijkstra(int s)
{
	priority_queue<P, vector<P>, greater<P> > que;
	memset(d[s], 0x3f, MAX_V * sizeof(int));
	d[s][s] = 0;
	que.push(P(0, s));

	while (!que.empty())
	{
		P p = que.top(); que.pop();
		int v = p.second;
		if (d[s][v] < p.first) continue;
		for (int i = 0; i < G[v].size(); ++i)
		{
			edge e = G[v][i];
			if (d[s][e.to] > d[s][v] + e.cost)
			{
				d[s][e.to] = d[s][v] + e.cost;
				que.push(P(d[s][e.to], e.to));
			}
		}
	}
}

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	int M, X;
	cin >> V >> M >> X;
	--X;
	while (M--)
	{
		int A, B, T;
		cin >> A >> B >> T;
		--A;
		--B;
		G[A].push_back(edge(B, T));
	}
	for (int i = 0; i < V; ++i)
	{
		dijkstra(i);
	}

	int ans = 0;
	for (int i = 0; i < V; ++i)
	{
		if (i == X)
		{
			continue;
		}
		ans = max(ans, d[i][X] + d[X][i]);
	}

	cout << ans << endl;
#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	system("out.txt");
#endif
	return 0;
}
///////////////////////////End Sub//////////////////////////////////

12722110 hankcs 3268 Accepted 4316K 657MS C++ 1715B 2014-04-06 21:15:55

不过上面那个实在太浪费,我只想计算起点或终点是X的路径最短路问题,可以在上面while (!que.empty())的循环里加入判断条件,还可以这么玩:

来一个反向图,交换边的起点和终点得到反向的有向图,两次dijkstra解决问题:

#ifndef ONLINE_JUDGE
#pragma warning(disable : 4996)
#endif
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <functional>
using namespace std;
#define MAX_V 10240

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

// first 最短路径,second顶点编号
typedef pair<int, int> P;

// 图
vector<vector<edge> > G(MAX_V);
// 反向图
vector<vector<edge> > RG(MAX_V);

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

// 求解从顶点s出发到所有点的最短距离
void dijkstra(int s)
{
	priority_queue<P, vector<P>, greater<P> > que;
	memset(d, 0x3f, sizeof(d));
	d[s] = 0;
	que.push(P(0, s));

	while (!que.empty())
	{
		P p = que.top(); que.pop();
		int v = p.second;
		if (d[v] < p.first) continue;
		for (int i = 0; i < G[v].size(); ++i)
		{
			edge e = G[v][i];
			if (d[e.to] > d[v] + e.cost)
			{
				d[e.to] = d[v] + e.cost;
				que.push(P(d[e.to], e.to));
			}
		}
	}
}

///////////////////////////SubMain//////////////////////////////////
int main(int argc, char *argv[])
{
#ifndef ONLINE_JUDGE
	freopen("in.txt", "r", stdin);
	freopen("out.txt", "w", stdout);
#endif
	int M, X;
	cin >> V >> M >> X;
	--X;
	while (M--)
	{
		int A, B, T;
		cin >> A >> B >> T;
		--A;
		--B;
		G[A].push_back(edge(B, T));
		RG[B].push_back(edge(A, T));
	}
	dijkstra(X);
	G = RG;
	memcpy(rd, d, sizeof(d));
	dijkstra(X);
	for (int i = 0; i < V; ++i)
	{
		d[i] += rd[i];
	}

	cout << *max_element(d, d + V) << endl;
#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	system("out.txt");
#endif
	return 0;
}
///////////////////////////End Sub//////////////////////////////////
12722114 hankcs 3268 Accepted 488K 125MS C++ 1729B 2014-04-06 21:16:52

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

分享到:更多 ()

评论 5

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

    最后一段代码貌似错了

    input
    4 8 2
    1 2 4
    1 3 2
    1 4 7
    2 1 1
    2 3 5
    3 1 2
    3 4 4
    4 2 3

    4 7 2
    1 2 7
    2 1 3
    1 3 4
    3 1 2
    1 4 3
    4 3 5
    2 3 2

    4 8 2
    1 2 10
    2 1 1
    1 3 4
    3 1 6
    4 1 2
    3 4 4
    2 3 3
    3 2 1
    output
    10
    20
    14

    teng2年前 (2016-05-24)回复
    • 我错了

      teng2年前 (2016-05-24)回复
  2. #2

    楼主,这个G=RG行吗?

    qingxi曾4年前 (2015-03-11)回复
  3. #1

    其实楼主可以去掉A–,B–,这样可以省去很多麻烦

    李振4年前 (2015-02-08)回复

我的开源项目

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