首页 > 其他 > 详细

YBTOJ 比较大小

时间:2021-09-24 02:32:26      阅读:7      评论:0      收藏:0      [点我收藏+]

题目算法要素:Floyd

题目分析:

最开始我想当作差分约束处理,但是没调过,只有20tps。
这个题的正解思路很有意思,很容易发现点数最多只有100,边数最多只有10000,因此可以用floyd维护f[a][b]表示a是否大于b。

若f[a][b]=true,则a>b。
若f[b][a]=true,则a<b。
若f[a][b]==0,则ab关系未知。

总结:有些时候根据数据范围猜算法也是个不错的选择。

Code

#include<bits/stdc++.h>
using namespace std;
int n,m,q,f[105][105],a,b;
int main()
{
	scanf("%d%d%d",&m,&n,&q);
	for(int i=1;i<=m;++i)
	{
		scanf("%d%d",&a,&b);
		f[a][b]=true;	
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;++j)
			for(int k=1;k<=n;++k)
				f[i][j]|=f[i][k]&f[k][j];
	for(int i=1;i<=n;++i)
	{
		for(int j=1;j<=n;++j)
		{
			if(i!=j && f[i][j] && f[j][i])
			{
				printf("10000words to copy");
				return 0;		
			}
		}
	}
	for(int g=1;g<=q;++g)
	{
		scanf("%d%d",&a,&b);
		if(f[a][b]) printf("YES\n"); 
		else if(f[b][a]) printf("NO\n"); 
		else printf("DK\n");
	}
	return 0;
}

YBTOJ 比较大小

原文:https://www.cnblogs.com/mint-hexagram/p/15307011.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!