入门题90pts求助
  • 板块P1347 排序
  • 楼主kevin985
  • 当前回复4
  • 已保存回复4
  • 发布时间2021/9/23 23:49
  • 上次更新2023/11/4 05:48:37
查看原帖
入门题90pts求助
384064
kevin985楼主2021/9/23 23:49

思路主要就是Floyd传递闭包,但是数据1和数据9不管怎么调都至少有一个过不了,有巨佬帮忙调下吗,求求了

#include <bits/stdc++.h>
#define N 110
#define rint register int
using namespace std;
int n,m;
bool f[N][N];
bool vis[N][N];
bool b[N];
int ans;
int main()
{
	scanf("%d%d",&n,&m);
	for(rint i=1; i<=n; ++i) vis[i][i] = 1;
	for(rint ii=1; ii<=m; ++ii)
	{
		string s;
		cin>>s;
		int u = s[0] - 'A' + 1,v = s[2] - 'A' + 1;
		if((!f[u][v] && vis[u][v]) || (f[v][u]) || u == v)
		{
			return !printf("Inconsistency found after %d relations.",ii);
		}
		f[u][v] = 1;
		f[s[0] - 'A' + 1][s[2] - 'A' + 1] = 1;
		vis[s[0] - 'A' + 1][s[2] - 'A' + 1] = 1;
		for(rint k=1; k<=n + 1; ++k)
			for(rint i=1; i<=n + 1; ++i)
				for(rint j=1; j<=n + 1; ++j)
					if(f[i][k] && f[k][j])
					{
						if(!f[i][j] && vis[i][j])
							return !printf("Inconsistency found after %d relations.",ii);
						f[i][j] = 1,vis[i][j] = 1;
					}
//		for(rint i=1; i<=n; ++i)
//		{
//			for(rint j=1; j<=n; ++j)
//			{
//				printf("%d",f[i][j]);
//			}
//			printf("\n");
//		}
//		printf("\n");
//		for(rint i=1;i<=n;++i)
//		{
//			for(rint j=1;j<=n;++j)
//			{
//				printf("%d",vis[i][j]);
//			}
//			printf("\n");
//		}
		for(rint i=1; i<=n + 1; ++i)
		{
			bool flag = 0;
			for(rint j=1; j<=n + 1; ++j)
			{
				if(!f[i][j] && !f[j][i])
				{
					flag = 1;
					break;
				}
			}
			if(!flag) ++ans;
			else break;
		}
		printf("%d\n",ans);
		if(ans == n)
		{
//			for(rint i=1;i<=n;++i)
//			{
//				for(rint j=1;j<=n;++j)
//				{
//					printf("%d",f[i][j]);
//				}
//				printf("\n");
//			}
//			return 0;
			printf("Sorted sequence determined after %d relations: ",ii);
			memset(b,0,sizeof(b));
			for(rint k=1; k<=n; ++k)
			{
				for(rint i=1; i<=n; ++i)
				{
					if(b[i]) continue;
					bool flag = 0;
					for(rint j=1; j<=n; ++j)
					{
						if(b[j] || i == j) continue;
						if(!f[i][j] || f[j][i])
						{
							flag = 1;
							break;
						}
					}
					if(!flag)
					{
						b[i] = 1;
						cout<<char(i + 'A' - 1);
						break;
					}
				}
			}
			return !printf(".");
		}
	}
	printf("Sorted sequence cannot be determined.");
	return 0;
}
2021/9/23 23:49
加载中...