ZJ a674: 10048 - Audiophobia

題目鏈接:https://zerojudge.tw/ShowProblem?problemid=a674

Floyd把DP式改成\(dp_{ij}=min(dp_{ij},max(dp_{ik},dp_{kj}))\)就行了

至於原因就請自己思考看看啦

以下為code

#include<bits/stdc++.h>

#include<bits/extc++.h>

using namespace std;

using namespace __gnu_cxx;

using namespace __gnu_pbds;

using ll = long long;

#define AC ios::sync_with_stdio(0),cin.tie(0);

int main()

{

    AC

    int c,s,q,cnt=1;

    while(cin>>c>>s>>q&&c&&s&&q)

    {

        cout<<"Case #"<<cnt++<<'\n';

        vector<vector<ll>> v(c+1,vector<ll>(c+1,1e9));

        for(int i=0;i<s;i++)

        {

            ll f,t,val;

            cin>>f>>t>>val;

            v[f][t]=val;

            v[t][f]=val;

        }

        for(int k=1;k<=c;k++)

            for(int i=1;i<=c;i++)

                for(int j=1;j<=c;j++)

                    v[i][j]=min(v[i][j],max(v[i][k],v[k][j]));

        for(int i=0;i<q;i++)

        {

            int f,t;

            cin>>f>>t;

            if(v[f][t]==1e9) cout<<"no path\n";

            else cout<<v[f][t]<<'\n';

        }

        cout<<'\n';

    }

}

2019/12/9 更

還有一種做法是透過求最小生成樹而得

使用Kruskal's演算法

根據邊的權重sort

從權重小的開始加入

當想查詢的點之間聯通時

最後被加入的那條邊權重一定是最大的

以下為code

#include<bits/stdc++.h>

#include<bits/extc++.h>

using namespace std;

using namespace __gnu_cxx;

using namespace __gnu_pbds;

using ll = long long;

#define AC ios::sync_with_stdio(0),cin.tie(0);

struct edge

{

    int u,v,w;

};

bool cmp(edge const& a, edge const& b)

{

    return a.w < b.w;

}

vector<edge> v;

struct DSU

{

    vector<int> v;

    DSU(int x)

    {

        v.resize(x);

        for(int i=1;i<x;i++)

            v[i] = i;

    }

    int find(int x)

    {

        if(v[x]==x) return x;

        return v[x]=find(v[x]);

    }

    void Union(int x,int y)

    {

        v[find(x)]=find(y);

    }

};

int main()

{

    AC

    int c,s,q,cnt=1;

    while(cin>>c>>s>>q&&c&&s&&q)

    {

        cout<<"Case #"<<cnt++<<'\n';

        v.clear();

        v.resize(s);

        for(auto &e:v)

            cin>>e.u>>e.v>>e.w;

        sort(v.begin(),v.end(),cmp);

        while(q--)

        {

            DSU d(c+1);

            bool b=0;

            int f,t;

            cin>>f>>t;

            for(auto e:v)

            {

                if(d.find(e.u)!=d.find(e.v)) d.Union(e.u,e.v);

                if(d.find(f)==d.find(t))

                {

                    cout<<e.w<<'\n';

                    b=1;

                    break;

                }

            }

            if(!b) cout<<"no path\n";

        }

        cout<<'\n';

    }

}