图论--传递闭包（Floyd模板）

#include<iostream>

#include<cstring>

#include<cmath>

using namespace std;

int dp[105][105],in[105],out[105];

int init()

{

	for(int i=1;i<=105;i++)

	{

		in[i]=0;

		out[i]=0;

		for(int j=1;j<=100;j++)

		{

			dp[i][j]=0;

		}

	}

}

int main()

{

	long long  t;

	cin>>t;

	while(t--)

	{

		init();

		long long n,m;

		cin>>n>>m;

        long long flag=0;

		for(int i=1;i<=m;i++)

		{

			long long  l,r;

			cin>>l>>r;

			dp[l][r]=1;

			if(l==r)    flag=1; //自己排在自己前面是不可能的，直接按题意输出0

		}

		for(int k=1;k<=n;k++)

			for(int i=1;i<=n;i++)

				for(int j=1;j<=n;j++)

					dp[i][j]=(dp[i][k]&&dp[k][j]);//floyd 讨论图的连通性

		for(int i=1;i<=n;i++)

			for(int j=1;j<=n;j++)

				if(dp[i][j]==1&&dp[j][i]==1)

					flag=1;

        //floyd 讨论图的连通性后，如果出现环的话，就是我排在你前面。你排在我前面，同样不可能

		for(int i=1;i<=n;i++)

			for(int j=1;j<=n;j++)

				if(dp[i][j]==1)

				{

					in[i]++;    //有几个人排在第I个人前面

					out[j]++;//有几个人排在第j个人后面面

				}

		if(flag)  //不符合现实的按题意输出0

		{

			for(int i=1;i<=n;i++)cout<<"0";

			cout<<endl;

		}

		else

		{

			for(int i=1;i<=n;i++)

			{

				if(in[i]>=(n+1)/2||out[i]>=(n+1)/2)  cout<<"0";

				//如果在他前面或者在他后面的不等于一般的人数，他绝对不是中间位置

				else   cout<<"1";

			}

			cout<<endl;

		}

	}

	return 0;

 }
巴特西

图论--传递闭包（Floyd模板）

最新文章

热门文章
