[NOIP2017模拟]路徑統計

2017.11.9 T2 2049

題目描述

一個 n 個點 m 條邊的無重邊無自環的無向圖，點有點權，邊有邊權，定義一條路徑的權值為路徑經過的點權的最大值乘邊權最大值。

求任意兩點間的權值最小的路徑的權值。

輸入格式

第一行兩個整數 n ，m ，分别表示無向圖的點數和邊數。

第二行 n 個正整數，第 i 個正整數表示點i的點權。

接下來 m 行每行三個正整數 ui，vi，wi ，分别描述一條邊的兩個端點和邊權。

輸出格式

輸出 n 行，每行 n 個整數。

第 i 行第 j 個整數表示從 i 到 j 的路徑的最小權值；如果從 i 不能到達 j ，則該值為 -1 。特别地，當 i=j 時輸出 0 。

樣例資料

輸入

3 3

2 3 3

1 2 2

2 3 3

1 3 1

輸出

0 6 3

6 0 6

3 6 0

備注

【資料範圍與約定】

對于 20% 的資料：n≤5；m≤8。

對于 50% 的資料：n≤50。

對于 100% 的資料：n≤500；m≤n*(n-1)/2，邊權和點權不超過 109 。

分析：考試的時候剛開始想到并查集，開始打了才發現中間步驟實作不了……灰心喪氣地去打大暴搜了。正解竟然是floyd？！這可是O( N3 )的呀？？？結果就是能過，神奇（雖然我之前想的并查集也要O( N3 )）。

先按點權排序，floyd最外層k表示路徑上最大點權為a[k]，i、j就是枚舉任意兩點，正常更新邊的最小值，如果兩個點的點權都小于a[k]，看能不能更新最短路，跑一遍，複雜度O( N3 )。

代碼

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<ctime>
#include<cmath>
#include<algorithm>
#include<cctype>
#include<iomanip>
#include<queue>
#include<set>
using namespace std;

int getint()
{
    int sum=,f=;
    char ch;
    for(ch=getchar();!isdigit(ch)&&ch!='-';ch=getchar());
    if(ch=='-')
    {
        f=-;
        ch=getchar();
    }
    for(;isdigit(ch);ch=getchar())
        sum=(sum<<)+(sum<<)+ch-;
    return sum*f;
}

const int N=,inf=;
const long long INF=;
int n,m;
struct node
{
    int w,id;
    inline friend bool operator <(const node &a,const node &b)
    {
        return a.w<b.w;
    }
}a[N];
int bian[N][N];
long long dis[N][N];

int main()
{
    freopen("path.in","r",stdin);
    freopen("path.out","w",stdout);

    int x,y,z;
    n=getint(),m=getint();
    for(int i=;i<=n;++i)
        for(int j=;j<=n;++j)
            dis[i][j]=INF,bian[i][j]=inf;//賦初值，極大值

    for(int i=;i<=n;++i)
        dis[i][i]=bian[i][i]=,a[i].w=getint(),a[i].id=i;

    for(int i=;i<=m;++i)
    {
        x=getint(),y=getint(),z=getint();
        bian[x][y]=bian[y][x]=z;//讀到邊的值
    }

    sort(a+,a+n+);//按點權排序

    for(int k=;k<=n;++k)//點權最大為a[k]
        for(int i=;i<=n;++i)
            for(int j=;j<=n;++j)
            {
                x=a[i].id,y=a[j].id,z=a[k].id;
                bian[x][y]=min(bian[x][y],max(bian[x][z],bian[z][y]));//邊權正常更新，是正常floyd應該進行的步驟
                if(i<=k&&j<=k)
                    dis[x][y]=min(dis[x][y],l*a[k].w*bian[x][y]);//隻有i和j的點權都不大于k的時候才能更新dis
            }

    for(int i=;i<=n;++i)
    {
        for(int j=;j<=n;++j)
            if(dis[i][j]!=INF)
                cout<<dis[i][j]<<" ";
            else
                cout<<-<<" ";
        cout<<'\n';
    }
    return ;
}
           

本題結。