社区讨论

妹妹码风良好 求调

P1347[ECNA 2001] 排序参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@m2ai4kdq
此快照首次捕获于
2024/10/15 21:51
去年
此快照最后确认于
2024/10/15 21:51
去年
查看原帖
为什么WA 第一个点啊 按照lyd蓝书std思路写的
CPP
#include<bits/stdc++.h>
using namespace std;
const int N=30;
int n,m,d[N][N],e[N][N];
int Floyd()
{
	memcpy(e,d,sizeof(e));
	//拷贝到e数组中,在e数组中对每个i,j进行迭代防止破坏原d数组的传递性
	for(int k=0;k<n;k++) //存入时-'A',那么'A'在这里对应的下标即为0 
	{
		for(int i=0;i<n;i++)
		{
			for(int j=0;j<n;j++)
			{
				e[i][j] |= e[i][k] & e[k][j];
				if(e[i][j] == e[j][i] && e[i][j]==1 && i!=j) return -1;//哎爆了 
			}
		}
	} 
	//跑传递闭包的时候同时判断一下,有矛盾return-1
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<n;j++)
		{
			if(e[i][j] ==0 && e[j][i] == 0 && i!=j)
			{
				return 0;//如果两方都为0,则return 0(无法判断)	
			}		
		}
	} 
	return 1; 
}
void works_it()
{
	memset(d,0,sizeof(d));//初始情况下所有的关系
	bool flag=1;
	for(int i=1;i<=m;i++)
	{
		char str[6];
		for(int i=0;i<=2;i++)
		{
			cin >> str[i] ;
		}
		// 0位为第一个字母 1位为大小关系 2位为第二个字母 
		d[str[0]-'A'][str[2]-'A'] = 1;//标记存在关系
		//本题中不等式全部为小于号,那就标记 i < j 是 1 吧 
		if(flag)//还没有选出来
		{
			int now=Floyd();//跑一边Floyd看是否满足
			if(now==-1)//哎,爆了
			{
				cout  << "Inconsistency found after " << i << " relations." << endl;
				flag=0;//失败了 
			}
			else if(now==1)//判断成功了 
			{
				cout << "Sorted sequence determined after " << i << " relations: ";
				pair<int , char> ans[N];
				for(int j=0;j<n;j++)
				{
					ans[j].first = 0;
					ans[j].second='A'+j;
				}//构建一个 权值 -> 字母的键值对
				for(int j=0;j<n;j++)
				{
					for(int k=0;k<n;k++)
					{
						if(e[j][k]) ans[j].first++;
						//如果存在 j 小于 k 给j的权值++
						//哎,那权值越高就越小 
					}
				} 
				sort(ans,ans+n);//对这些字母按照权值排序 
				for(int j=n-1;j>=0;j--)//越大的权值越小所以倒序输出 
				{
					cout << ans[j].second;
				} 
				cout << "." << endl;
				flag = 0;
			} 
		} 
	}
	//那跑完所有的都没有满足就没有呗 
	if(flag) cout << "Sorted sequence cannot be determined." << endl; 
	
}
int main()
{
	while(cin >> n >> m && (n!=0&&m!=0))
	{
		works_it();
	}
	return 0;
}
// 要去爱,要去劳动 

回复

0 条回复,欢迎继续交流。

正在加载回复...