POJ - 3613 Cow Relays(Floyd思想+矩阵快速幂+动态规划)

60 阅读 0 评论 40 点赞

我是靠谱客的博主满意月饼，最近开发中收集的这篇文章主要介绍POJ - 3613 Cow Relays(Floyd思想+矩阵快速幂+动态规划)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目链接：点击查看

题目大意：给定一张由T(T<=100)条边构成的无向图，点的编号为1~1000,之间的整数，求从起点S到终点E恰好经过N(N<=1e6)条边(可重复经过)的最短路

题目分析：虽然点的编号在1e3以内，却只有100条边，我们可以离散化，这样最多只需要一个200*200的邻接矩阵就可以维护了，离散化后我们考虑maze储存了邻接矩阵，则dp[i][j]=min(maze[i][k]+maze[k][j])，dp[i][j]表示的是点i和点j经过了一条边的最短路，这样我们可以将整个数组上升至三维空间，dp[k][i][j]代表的是点i到点j经过了k个点后的最短路，转移方程为：

dp[k][i][j]=min(dp[x][i][t]+dp[k-x][t][j]) (t为连接点i和点j的中间点)

这样一来就可以用矩阵快速幂优化了，只不过需要将矩阵乘法改成取加法运算，矩阵加法改成取min运算，每次都由第k-1层转移到第k层，最后答案就是dp[k][st][ed]了，因为每次的空间都可以滚动使用，所以第一维的k并不需要真实体现出来，这只是一种思维的体现，实际实现的过程中完全可以省略掉

最后注意一下每条边的输入格式是w u v，太恶心人了吧？调了一个小时

代码：

#include<iostream>
#include<cstdlib>
#include<string>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<climits>
#include<cmath>
#include<cctype>
#include<stack>
#include<queue>
#include<list>
#include<vector>
#include<set>
#include<map>
#include<sstream>
using namespace std;
    
typedef long long LL;
    
const int inf=0x3f3f3f3f;

const int N=210;

struct Edge
{
	int u,v,w;
	void input()
	{
		scanf("%d%d%d",&w,&u,&v);//注意输入格式
	}
}edge[N];

int n;

vector<int>v;//离散化用 

int get_id(int x)//获得离散化后的映射
{
	return lower_bound(v.begin(),v.end(),x)-v.begin();
}

struct Ma
{
	int a[N][N];
	Ma()
	{
		memset(a,inf,sizeof(a));
	}
	friend Ma operator*(const Ma& a,const Ma& b)
	{
		Ma ans;
		for(int i=0;i<v.size();i++)
			for(int j=0;j<v.size();j++)
			{
				ans.a[i][j]=inf;
				for(int k=0;k<v.size();k++)
					ans.a[i][j]=min(ans.a[i][j],a.a[i][k]+b.a[k][j]);
			}
		return ans;
	}
};

Ma q_pow(Ma a,int b)
{
	Ma ans=a;
	while(b)
	{
		if(b&1)
			ans=ans*a;
		a=a*a;
		b>>=1;
	}
	return ans;
}

int main()
{
//  freopen("input.txt","r",stdin);
//  ios::sync_with_stdio(false);
	int k,n,st,ed;
	scanf("%d%d%d%d",&k,&n,&st,&ed);
	Ma ans;
	for(int i=1;i<=n;i++)
	{
		edge[i].input();
		v.push_back(edge[i].u);
		v.push_back(edge[i].v);
	}
	sort(v.begin(),v.end());
	v.erase(unique(v.begin(),v.end()),v.end());
	for(int i=1;i<=n;i++)
	{
		int x=get_id(edge[i].u);
		int y=get_id(edge[i].v);
		int w=edge[i].w;
		ans.a[x][y]=ans.a[y][x]=w;
	}
	ans=q_pow(ans,k-1);
	printf("%dn",ans.a[get_id(st)][get_id(ed)]);
	
	
	
	
	



        
        
        
         
        
    return 0;
}