本题可以用传递闭包做吗?
查看原帖
本题可以用传递闭包做吗?
782096
leeeeedr楼主2023/12/16 15:12

rt,本人代码,可以拿20pts

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXX=1e4+10;
bool f[MAXX][MAXX];
long long sum[MAXX];
int n,m;
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	while(m--)
	{
		int a,b;
		cin>>a>>b;
		f[a][b]=1;
	}
	for(int i=1;i<=n;i++)
	{
		f[i][i]=1;
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			for(int k=1;k<=n;k++)
			{
				if(f[j][k]&&f[k][i])
				{
					f[j][i]=1;
				}
			}
			if(f[j][i]) sum[i]++;
		}
	}
	long long maxx=-1;
	for(int i=1;i<=n;i++)
	{
		maxx=max(maxx,sum[i]);
	}
	int summm=0;
	for(int i=1;i<=n;i++)
	{
		if(sum[i]==maxx)
		{
			summm++;
		}
	}
	cout<<summm;
	return 0;
}
2023/12/16 15:12
加载中...