W - Cow Relays(倍增Floyd)

95 阅读 0 评论 63 点赞

我是靠谱客的博主留胡子白开水，最近开发中收集的这篇文章主要介绍W - Cow Relays(倍增Floyd)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

题目大意 : 给定无向图, 起点S, 终点E, 问恰好经过N条边的最短路

思路 : 这是一道典型的Floyd倍增的题目(之前没见过, 完全没思路, 寄!), 就是通过对Floyd进行变形的一个dp做法

Floyd算法:

f[k][i][j] : i 到 j , 通过中转点k的最短路, f[i][j] = min(f[i][k] + f[j][k])

类Floyd:

f[k][i][j] : i到j, 通过k条边的最短路, f[a+b][i][k] = min(f[a][i][k] + f[b][j][k]), 因为i 到中转点k经过a边的最短路不会影响中转点k 到 j 经过b边的最短路, 所以具有可加性, 可以通过快速幂来进行优化(不优化的话, O(N*n^3) 会直接t)

AC代码如下:

#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
#include <iterator>
#include <cmath>
#include <algorithm>
#include <sstream>
#include <map>
#include <stack>
#include <set>
#include <queue>
#include <iomanip>
using namespace std;

stringstream ss;
typedef long long ll;
typedef pair<int, int> PII;
const int N = 220;
const int INF = 0x3f3f3f3f;

int k, n, m, S, E;
int g[N][N];
int res[N][N];

// 通过类Floyd, 做dp, f[k][i][j] 代表的是i,j经过k边的最短路
// 状态转移 f[a+b][i][j] = min(... , f[a][i][k]+f[b][k][j]) 即, i到k经过a条边, k到j经过b条边
void mul(int c[][N], int a[][N], int b[][N])
{
    static int temp[N][N];
    memset(temp, 0x3f, sizeof temp);

    for(int k = 1; k<=n; k++)
    {
        for(int i = 1; i<=n; i++)
        {
            for(int j = 1; j<=n; j++)
            {
                temp[i][j] = min(temp[i][j], a[i][k]+b[k][j]);
            }
        }
    }
    memcpy(c, temp, sizeof temp);
}

// 矩阵快速幂
void qmi()
{
    memset(res, 0x3f, sizeof res);
    for(int i = 1; i<=n; i++) res[i][i] = 0;

    while(k)
    {
        if(k&1) mul(res, res, g); // res = res*g
        mul(g,g,g); // g = g*g;
        k>>=1;
    }
}

int main()
{
    cin>>k>>m>>S>>E;

    memset(g, 0x3f, sizeof g);
    // 这里不能对g[i][i] 初始化为0, 若指通过一条边, g[i][i] 从i到i只有自环能从i回到i
    // 此时i到i的距离因为不可达INF, 而不是0
    // for(int i = 1; i<N; i++) g[i][i] = 0;
    // 数据大但用的少, 需要进行离散化
    map<int, int> ids;
    if(!ids.count(S)) ids[S] = ++n;
    if(!ids.count(E)) ids[E] = ++n;
    S = ids[S], E = ids[E];
    while( m -- )
    {
        int a,b,c;
        cin>>c>>a>>b;
        if(!ids[a]) ids[a] = ++n;
        if(!ids[b]) ids[b] = ++n;
        a = ids[a], b = ids[b];
        g[a][b] = g[b][a] = min(c, g[a][b]);
    }

    qmi();

    cout<<res[S][E]<<endl;
}