蒟蒻求救
查看原帖
蒟蒻求救
222578
jingkongwanglimiaoa楼主2020/8/9 12:59

这是一份连样例都过不了的代码

# include <cstdio>
# include <iostream>
# include <cstring>
using namespace std;
int lk[10010],pp = 0,q[10010],hd = 0,nd[10010],n,m,f[10010],ans[30];//lk数组与结构体是邻接链表存储,hd是队尾,q是队列,nd是入度,f是能力值即用来判断给的条件够不够确认顺序,ans存答案 
char aa,bb,hh,hhh;
struct sth{
	int sum,num;
}e[10010];
void ist(int x,int y)
{
	e[++pp] = {y,lk[x]};
	lk[x] = pp;
}
void dr()
{
	scanf("%c %c %c",&aa,&hh,&bb);
	if (hh == '<')  ist(aa - 'A' + 1,bb - 'A' + 1);
	else ist(bb - 'A' + 1,aa - 'A' + 1);
}
bool tppx()
{
	hd = 0;
	memset(f,0,sizeof(f));
	memset(nd,0,sizeof(nd));
	for (int i = 1;i <= n;i++)
		for (int j = lk[i];j != 0;j = e[j].num)
		{
			nd[e[j].sum]++;
			printf("%d",e[i].sum);
		}
	for (int i = 1;i <= n;i++)
	if (nd[i] == 0)
	{
		q[++hd] = i;
		f[i] = 1;
	}
	for (int k = 1;k <= hd;k++)
	{
		for (int i = lk[q[k]];i != 0;i = e[i].num)
		{
			nd[e[i].sum]--;
			if (nd[e[i].sum] == 0)
			q[++hd] = e[i].sum;
			printf("i = %d,q[k] = %d,f[i] =  %d,f[q[k]] + 1 = %d\n",i,q[k],f[i],f[q[k]] + 1);
			f[i] = max(f[i],f[q[k]] + 1);
		}
	}
	for (int i = 1;i <= hd;i++)
	printf("%d",q[i]);
	if (hd != n)  return false;
	return true;
}
int main()
{
	scanf("%d %d\n",&n,&m);
	for (int i = 1; i <= m;i++)
	{
		dr();
		if (!tppx())
		{
			ans[0] = -i;
			break;
		}
		else
		{
			for (int i = 1;i <= hd;i++)
			printf("f%d %d",i,f[i]);
			printf("\n");
			bool flag = true;
			for (int k = 1;k < hd;k++)
			if (f[k] == f[k + 1])
			{
				flag = false;
				break;
			}
			if (flag)
			{
				for (int j = 1;j <= n;j++)
				ans[j] = q[j];
				break;
			}
		}
	}
	if (ans[0] < 0)
	{
		printf("Inconsistency found after %d relations.",-ans[0]);
	}
	else
	if (ans[0] != 0)
	{
		printf("Sorted sequence determined after %d relations:",ans[0]);
	}
	else printf("Sorted sequence cannot be determined.");
	return 0;
}

有些奇妙的printf是我在调试的时候留下的请神犇们自动忽略

经过我多次调试我发现好像是链表存储出问题了想看看题解却发现大家都用的矩阵

救救蒟蒻吧

2020/8/9 12:59
加载中...