Floyd(多源匯最短路)

Floyd求最短路

給定一個?n?個點?m?條邊的有向圖，圖中可能存在重邊和自環，邊權可能為負數。

再給定?k?個詢問，每個詢問包含兩個整數?x?和?y，表示查詢從點?x?到點?y?的最短距離，如果路徑不存在，則輸出?impossible。

數據保證圖中不存在負權回路。

輸入格式

第一行包含三個整數?n,m,k

接下來?m?行，每行包含三個整數?x,y,z，表示存在一條從點?x?到點?y?的有向邊，邊長為?z。

接下來?k?行，每行包含兩個整數?x,y表示詢問點?x?到點?y?的最短距離。

輸出格式

共?k?行，每行輸出一個整數，表示詢問的結果，若詢問兩點間不存在路徑，則輸出?impossible。

數據范圍

1≤n≤200
1≤k≤n2
1≤m≤20000
圖中涉及邊長絕對值均不超過?10000

輸入樣例：

輸出樣例：

impossible
1

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=220,INF=0x3f3f3f3f;
int f[N][N];
int main()
{int n,m,K;cin>>n>>m>>K;memset(f,0x3f,sizeof f);for(int i=0;i<=n;i++) f[i][i]=0;while(m--){int x,y,z;cin>>x>>y>>z;f[x][y]=min(f[x][y],z);}for(int k=1;k<=n;k++){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++)f[i][j]=min(f[i][j],f[i][k]+f[k][j]);}}while(K--){int a,b;cin>>a>>b;if(f[a][b]>=INF/2) cout<<"impossible"<<endl;else cout<<f[a][b]<<endl;}return 0;
}

牛的旅行

農民John的農場里有很多牧區，有的路徑連接一些特定的牧區。

一片所有連通的牧區稱為一個牧場。

但是就目前而言，你能看到至少有兩個牧區不連通。

現在，John想在農場里添加一條路徑（注意，恰好一條）。

一個牧場的直徑就是牧場中最遠的兩個牧區的距離（本題中所提到的所有距離指的都是最短的距離）。

考慮如下的兩個牧場，每一個牧區都有自己的坐標：

圖 1 是有 5 個牧區的牧場，牧區用“*”表示，路徑用直線表示。

圖 1 所示的牧場的直徑大約是 12.07106, 最遠的兩個牧區是 A 和 E，它們之間的最短路徑是 A-B-E。

圖 2 是另一個牧場。

這兩個牧場都在John的農場上。

John將會在兩個牧場中各選一個牧區，然后用一條路徑連起來，使得連通后這個新的更大的牧場有最小的直徑。

注意，如果兩條路徑中途相交，我們不認為它們是連通的。

只有兩條路徑在同一個牧區相交，我們才認為它們是連通的。

現在請你編程找出一條連接兩個不同牧場的路徑，使得連上這條路徑后，所有牧場（生成的新牧場和原有牧場）中直徑最大的牧場的直徑盡可能小。

輸出這個直徑最小可能值。

輸入格式

第 1 行：一個整數 N, 表示牧區數；

第 2 到 N+1 行：每行兩個整數 X,Y，表示 N 個牧區的坐標。每個牧區的坐標都是不一樣的。

第 N+2 行到第 2*N+1 行：每行包括 N 個數字 ( 0或1 ) 表示一個對稱鄰接矩陣。

例如，題目描述中的兩個牧場的矩陣描述如下：

  A B C D E F G H 
A 0 1 0 0 0 0 0 0 
B 1 0 1 1 1 0 0 0 
C 0 1 0 0 1 0 0 0 
D 0 1 0 0 1 0 0 0 
E 0 1 1 1 0 0 0 0 
F 0 0 0 0 0 0 1 0 
G 0 0 0 0 0 1 0 1 
H 0 0 0 0 0 0 1 0

輸入數據中至少包括兩個不連通的牧區。

輸出格式

只有一行，包括一個實數，表示所求答案。

數字保留六位小數。

數據范圍

1≤N≤150

0≤X,Y≤10^5

輸入樣例：

輸出樣例：

22.071068

直徑最大值最小?

?題目的問題：給定兩個聯通塊，在兩個連通塊中各取任意一點進行連接合成一個連通塊，求合并后的聯通塊的最長路徑的最小值

?floyd：
這里可以分為兩種情況：一種是在同一個連通分量，還有一種是不在同一個連通分量
1.在同一連通分量：
我們用maxd[i]表示和i所在連通分量的最長直徑
那么這里的答案就是max1≤i≤nmaxd[i]max1≤i≤nmaxd[i]
2.不在同一連通分量：
我們可以用兩個連通分量的maxd+它們之間的最短距離即可
這里的答案就是maxd[i]+get (i,j)+max[j]

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#define x first
#define y second
using namespace std;
typedef pair<int,int>PII;
const int N=200;
const double INF=1e20;
PII q[N];//存儲n個牧場的坐標
char g[N][N];//存儲n個牧場之間是否有邊
double d[N][N];//存儲n牧場之間的距離最下值
double dmax[N];//dmax[i]表示 i所在的連通分量的最長直徑
int n;
//兩個牧場之間的距離
double get_dist(PII a,PII b)
{double dx=b.x-a.x,dy=b.y-a.y;return sqrt(dx*dx+dy*dy);
}
int main()
{cin>>n;for(int i=0;i<n;i++) cin>>q[i].x>>q[i].y;for(int i=0;i<n;i++) cin>>g[i];for(int i=0;i<n;i++){for(int j=0;j<n;j++){if(i!=j){if(g[i][j]=='1')d[i][j]=get_dist(q[i],q[j]);else d[i][j]=INF;}}}//floyd 得出d[i][j] 距離的最小值for(int k=0;k<n;k++){for(int i=0;i<n;i++){for(int j=0;j<n;j++){d[i][j]=min(d[i][j],d[i][k]+d[k][j]);}}}for(int i=0;i<n;i++){for(int j=0;j<n;j++){if(d[i][j]<INF){dmax[i]=max(dmax[i],d[i][j]);}}}double ans1=0;//情況1for(int i=0;i<n;i++) ans1=max(ans1,dmax[i]);double ans2=INF;//情況2for(int i=0;i<n;i++){for(int j=0;j<n;j++){if(d[i][j]>=INF){ans2=min(ans2,get_dist(q[i],q[j])+dmax[i]+dmax[j]);}}}printf("%.6lf\n",max(ans1,ans2));return 0;
}

排序（傳遞閉包）

給定?n?個變量和?m?個不等式。其中?n?小于等于?26，變量分別用前?n?的大寫英文字母表示。

不等式之間具有傳遞性，即若?A>B 且?B>C，則?A>C。

請從前往后遍歷每對關系，每次遍歷時判斷：

如果能夠確定全部關系且無矛盾，則結束循環，輸出確定的次序；
如果發生矛盾，則結束循環，輸出有矛盾；
如果循環結束時沒有發生上述兩種情況，則輸出無定解。

輸入格式

輸入包含多組測試數據。

每組測試數據，第一行包含兩個整數?n?和?m。

接下來?m?行，每行包含一個不等式，不等式全部為小于關系。

當輸入一行?0 0?時，表示輸入終止。

輸出格式

每組數據輸出一個占一行的結果。

結果可能為下列三種之一：

如果可以確定兩兩之間的關系，則輸出?"Sorted sequence determined after t relations: yyy...y.",其中't'指迭代次數，'yyy...y'是指升序排列的所有變量。
如果有矛盾，則輸出：?"Inconsistency found after t relations."，其中't'指迭代次數。
如果沒有矛盾，且不能確定兩兩之間的關系，則輸出?"Sorted sequence cannot be determined."。

數據范圍

2≤n≤26，變量只可能為大寫字母?A～Z。

輸入樣例1：

4 6
A<B
A<C
B<C
C<D
B<D
A<B
3 2
A<B
B<A
26 1
A<Z
0 0

輸出樣例1：

Sorted sequence determined after 4 relations: ABCD.
Inconsistency found after 2 relations.
Sorted sequence cannot be determined.

輸入樣例2：

6 6
A<F
B<D
C<E
F<D
D<E
E<F
0 0

輸出樣例2：

Inconsistency found after 6 relations.

輸入樣例3：

5 5
A<B
B<C
C<D
D<E
E<A
0 0

輸出樣例3：

Sorted sequence determined after 4 relations: ABCDE.

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=30;
bool g[N][N],d[N][N];
bool st[N];
int n,m;
void floyd()//通過floyd 來逐漸判斷兩個點的連通情況
{memcpy(d,g,sizeof d);for(int k=0;k<n;k++)for(int i=0;i<n;i++)for(int j=0;j<n;j++)if(!d[i][j]) d[i][j]=d[i][k]&d[k][j];}
int check()
{for(int i=0;i<n;i++)//矛盾情況 A<Aif(d[i][i]) return 2;for(int i=0;i<n;i++)for(int j=0;j<i;j++)//不能確定情況if(!d[i][j]&&!d[j][i]) return 0;//可以確定情況return 1;
}
char get_min()//每次取出最小值
{for(int i=0;i<n;i++){if(!st[i])//如果沒有取出 {bool flag=true;for(int j=0;j<n;j++)//判斷是否 最小{if(!st[j]&&d[j][i]) {flag=false;break;}}if(flag){st[i]=true;return 'A'+i;}}}
}
int main()
{while(cin>>n>>m,n||m){memset(g,0,sizeof g);int type=0,t;// t 記錄輪次  type記錄判斷出來與否的標志for(int i=1;i<=m;i++){char str[10];cin>>str;int a=str[0]-'A',b=str[2]-'A';if(!type){g[a][b]=1;floyd();type=check();if(type) t=i;}}if(!type) cout<<"Sorted sequence cannot be determined."<<endl;else if(type==2)printf("Inconsistency found after %d relations.\n",t);else{memset(st,0,sizeof st);printf("Sorted sequence determined after %d relations: ",t);for(int i=0;i<n;i++) printf("%c",get_min());printf(".\n");}}return 0;
}

本文來自互聯網用戶投稿，該文觀點僅代表作者本人，不代表本站立場。本站僅提供信息存儲空間服務，不擁有所有權，不承擔相關法律責任。
如若轉載，請注明出處：http://www.pswp.cn/news/38522.shtml
繁體地址，請注明出處：http://hk.pswp.cn/news/38522.shtml
英文地址，請注明出處：http://en.pswp.cn/news/38522.shtml

如若內容造成侵權/違法違規/事實不符，請聯系多彩編程網進行投訴反饋email:809451989@qq.com，一經查實，立即刪除！