这题题面挺抽象的,一个人与他所以的朋友的钱不能超过 \(d\),问朋友链上钱最多的人的钱与钱最少的人的钱相差多少,求差距的最大值 。
如果两个人不属于同一个连通块那么差距可以无穷大,好了特殊情况解决了。然后为了使这个差距最大,那么对于每个朋友我们都取 \(d\) 为权值来连一条边,最后跑最短路可以得到最大差距。
因为这题的图很稠密,所以用 floyd(其实因为在 floyd 的例题做到的,所以不想再改了,但其实这数据范围也该这么写)
#include<bits/stdc++.h>
using namespace std;
const int N=100;
const int inf=0x3f3f3f3f;
int n,d;
int dp[N][N];
int main(){
ios::sync_with_stdio(false);
int t;
cin>>t;
while(t--){
cin>>n>>d;
char c;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>c;
dp[i][j]=inf;
dp[j][i]=inf;
dp[i][i]=0;
if(c=='Y'){
dp[i][j]=dp[j][i]=d;
}
}
}
for(int k=1;k<=n;k++){
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
}
}
}
int mx=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
mx=max(mx,dp[i][j]);
}
}
if(mx>=inf){
cout<<-1;
}
else{
cout<<mx;
}
cout<<"\n";
}
return 0;
}
标签:贫富差距,51nod,1366,int,inf,dp
From: https://www.cnblogs.com/sadlin/p/18393429