社区讨论
妹妹码风良好 求调
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 条回复,欢迎继续交流。
正在加载回复...