POJ3613 Cow Relays——Floyd与矩阵相乘的应用

转：https://blog.csdn.net/Monster__Yi/article/details/51069236 

题意：给定一个T(2 <= T <= 100)条边的无向图，求S到E恰好经过N(2 <= N <= 1000000)条边的最短路。

分析：

这应该是本周作业题里最难的一道题了，本蒟蒻只想到了dp做法，f(i, j, k)表示i到j经过k条边的最短路，f(i, j, k) = min(f(i, o, k-1) + edge(o, j).w)，不用说，一看就超时。

今天听完zrt神犇的讲解后，顿时大彻大悟。

用一个矩阵a(i, j)来表示i到j经过若干条边的最短路，初始化a为i到j边的长度，没有则是正无穷。

然后重载*运算符，比如a矩阵表示经过n条边，b矩阵表示经过m条边，那么a * b得到的矩阵表示经过m + n条边，采用Floyd的思想进行更新。

为了省时间，用了快速幂，这样时间复杂度达到了O(n^3logk)，可以通过。

因为题目最多只有100条边，也就是200个点，但是数据中点的序号可能达到1000，所以进行了map在线离散化。

#include <bits/stdc++.h>
using namespace std;
const int maxn = 210;
const int inf = 0x3f3f3f3f;
map<int, int> m;
int n, t, s, e;
int num;
struct matrix
{
	int v[maxn][maxn];
	matrix operator *(const matrix &r)
	{
		matrix res;
		memset(res.v, inf, sizeof(res.v));
		for (int i = 1; i <= num; i++)
			for (int j = 1; j <= num; j++)
				for (int k = 1; k <= num; k++)
					res.v[i][j] = min(res.v[i][j], v[i][k] + r.v[k][j]);
		return res;
	}
};
matrix ini, res;

void power()
{
	res = ini;
	n--;
	while (n)
	{
		if (n & 1)
			res = res * ini;
		ini = ini * ini;
		n >>= 1;
	}
	return;
}

int main()
{
	int v, x, y;
	int a, b;

	memset(ini.v, inf, sizeof(ini.v));
	cin >> n >> t >> s >> e;
	while (t--)
	{
		cin >> v >> x >> y;
		if (m[x]) a = m[x];
		else a = m[x] = ++num;
		if (m[y]) b = m[y];
		else b = m[y] = ++num;
		ini.v[a][b] = ini.v[b][a] = v;
	}
	//cout << num << endl;
	power();
	cout << res.v[m[s]][m[e]] << endl;

	return 0;
}

最后

以上就是呆萌西牛为你收集整理的POJ3613 Cow Relays——Floyd与矩阵相乘的应用的全部内容，希望文章能够帮你解决POJ3613 Cow Relays——Floyd与矩阵相乘的应用所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。