題目鏈接：點(diǎn)擊查看

題目大意：有 n 個城市由 n - 1 條邊連接成一個連通塊，給出一個 n * n 的距離矩陣，代表 n 個城市中每兩個城市之間的最短路，問該矩陣是否合法，如果合法從小到大輸出 n - 1 條邊

題目分析：比賽的時候沒反應(yīng)過來這個題的題意是想干什么，補(bǔ)題的時候發(fā)現(xiàn)原來就是一個最小生成樹，因?yàn)?n 個點(diǎn)由?n - 1 條邊組成了聯(lián)通塊，很顯然是一棵樹，題目又說了需要顯示城市之間的最短距離，這就暗示了這棵樹就是 n 個城市的最小生成樹，現(xiàn)在給出的矩陣是否合法，我們只需要先判斷一下是否對稱(廢話)，然后再利用這個矩陣建邊然后跑出最小生成樹，利用這個最小生成樹跑一遍 Floyd ，最后與原距離矩陣比較一下是否相同就可以判斷是否合法了

代碼：

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<unordered_map> using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=510;struct Edge {int u,v,w;Edge(int u,int v,int w):u(u),v(v),w(w){}bool operator<(const Edge& a)const{return w<a.w;} };vector<Edge>edge;vector<int>ans;int maze[N][N],dis[N][N],f[N];int find(int x) {return x==f[x]?x:f[x]=find(f[x]); }bool merge(int x,int y) {int xx=find(x);int yy=find(y);if(xx!=yy){f[xx]=yy;return true;}return false; }int main() { //#ifndef ONLINE_JUDGE // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); //#endif // ios::sync_with_stdio(false);int n;scanf("%d",&n);for(int i=1;i<=n;i++)f[i]=i;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){scanf("%d",&maze[i][j]); dis[i][j]=i==j?0:inf;}for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++){edge.push_back(Edge(i,j,maze[i][j]));if(maze[i][j]!=maze[j][i])return 0*printf("No");}sort(edge.begin(),edge.end());for(auto it:edge){if(merge(it.u,it.v)){ans.push_back(it.w);dis[it.u][it.v]=dis[it.v][it.u]=it.w;}}for(int k=1;k<=n;k++)for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(maze[i][j]!=dis[i][j])return 0*printf("No");puts("Yes");for(auto it:ans)printf("%d\n",it);return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的牛客 - 导航系统(最小生成树+Floyd)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。