首页 > 其他分享 >51nod 1366 贫富差距

51nod 1366 贫富差距

时间:2024-09-02 20:03:12浏览次数:11  
标签:贫富差距 51nod 1366 int inf dp

51nod 1366 贫富差距

这题题面挺抽象的,一个人与他所以的朋友的钱不能超过 \(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

相关文章

  • 51nod 3179 绝世好题
    3179绝世好题他仅仅要求序列最长的长度,我们可以引用最长上升子序列的思想(有些隐蔽),设状态\(dp[i]\)为二进制第i位为1的最长序列长度,对于一个数10101\(dp[1],dp[3],dp[5]\)都应该加一,对他们的数值取个最大值,并将他们的状态与最大值比较更新。下列代码为上述思路:#includ......
  • 51nod 3010 The Captain
    暴力构图为\(O(n^2)\)无法实现,但可以发现有些边无用,可以先按x排序,第i号点与第i+1号点一定最近,所以建一条边,y坐标同理,然后跑最短路即可自动选择\(min(|x_1-x_2|,|y_1-y_2|)\)#include<bits/stdc++.h>usingnamespacestd;constlonglongINF=0x3f3f3f3f;constint......
  • 51nod 1204 Parity
    闲话虽然这题好像找不到原题了,但毋庸置疑地说这的确是并查集的好题。分析可以先对奇偶区间进行分析,当这个有偶数个1时,区间\(1-(left-1)\)一定与区间\(1-right\)的奇偶性相同。如此图\(3-4\)为偶区间,根据分析,\(1-2\)为奇区间。\(1-4\)也为奇区间。但如果填入的......
  • 全球创新药商业化服务平台市场展望:2030年预计达到113660百万美元
    随着全球医药行业的快速发展和创新药物研发的不断涌现,创新药商业化服务平台行业作为支持新药上市和商业化的关键服务领域,其市场前景受到业界广泛关注。据恒州恒思(YHresearch)团队研究的数据显示,2023年全球创新药商业化服务平台市场规模已达到33210百万美元,并预计在未来六年内,该......
  • Mysql写入数据错误:General error: 1366 Incorrect string value: '\\xF0\\x9F\\
    这个问题,原因是UTF-8编码有可能是两个、三个、四个字节。Emoji表情或者某些特殊字符是4个字节,而Mysql的utf8编码最多3个字节,所以数据插不进去。我这边是在linux服务器,Mysql的版本是5.7。解决此问题需要修改Mysql的配置文件my.cnf。 总结修改配置:[client]default-character......
  • 51nod两问-Pinball等
    问题1-Pinball为什么这样解释的通,我看不懂什么意思?还有这个\(e\)在后面状态中没有体现。具体做法?为什么只有\([a_i,c_i]\)需要考虑?他可以往左边掉。那么从\(n\)开始掉又如何考虑Kamp手绘的图:这个图似乎就不满足了。不知道什么意思。这个思路怎么做。......
  • 51nod-3928方伯伯的玉米田
    https://class.51nod.com/Html/Textbook/ChapterIndex.html#textbookId=126&chapterId=338https://class.51nod.com/Html/Textbook/Problem.html#problemId=3928&textbookChapterId=725保证右端点为\(n\)是因为如果不是这样操作,可能导致后面的数大小关系发生变化,而如果保证了......
  • 51nod-3986-免费的馅饼
    https://class.51nod.com/Html/Textbook/Problem.html#problemId=3986&textbookChapterId=725https://class.51nod.com/Html/Textbook/ChapterIndex.html#textbookId=126&chapterId=338我们将馅饼表示为\((p_i,t_i)\),即一个平面直角坐标系上的点。我们把馅饼看成静止,人每次往......
  • 51nod-3976-最长序列
    https://class.51nod.com/Html/Textbook/ChapterIndex.html#textbookId=126&chapterId=338https://class.51nod.com/Html/Textbook/Problem.html#problemId=3976&textbookChapterId=725LIS是符号只有大于或小于,所以这道题就是LIS问题。状态设计同LIS,由于答案就是长度,所以就能知......
  • 51nod-基因匹配+luogu-【模板】最长公共子序列
    https://www.luogu.com.cn/problem/P1439https://class.51nod.com/Html/Textbook/ChapterIndex.html#textbookId=126&chapterId=338以上两个都是特例,一个是每个元素不重复,一个是每个元素均有5个。正确性说明参考:https://www.luogu.com.cn/article/1bcs9052由于一般情况可能出......