这道题的 N 的范围是不是有点问题?
查看原帖
这道题的 N 的范围是不是有点问题?
1000268
PassionOfLife楼主2023/10/1 17:09

我的代码如下:

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
#include<cstring>
#include<cmath>
using namespace std;
const int N = 120;
const int M = 2*N;

int h[N], e[M], ne[N], idx; 
int deg[N]; 
int n;
vector<int> a;

void init_G() {
	memset(h, -1, sizeof(h));
	memset(ne, -1, sizeof(ne));
	idx = 0;
}

void add(int a, int b) {
	e[idx] = b;
	ne[idx] = h[a];
	h[a] = idx++;
}

void top_sort() {
	queue<int> q;
	
	for(int node = 1; node<=n; node++) {
		if(deg[node] == 0)
			q.push(node); 
	}
	
	while(!q.empty()) {
		int t = q.front();	q.pop();
		a.push_back(t);	
		for(int p = h[t]; p != -1; p = ne[p]) {
			int t2 = e[p];
			deg[t2]--;
			if(deg[t2] == 0) q.push(t2); 
		}
	}
}

int main() {
	init_G();
	memset(deg, 0, sizeof(deg));
	scanf("%d", &n);
	for(int i = 1; i<=n; i++) {
		int num;
		scanf("%d", &num);
		while(num != 0) {
			deg[num]++;	add(i, num);
			scanf("%d", &num);
		}
	}
	top_sort();
	for(int i = 0; i<a.size(); i++)
		printf("%d ", a[i]);
	return 0;
}

我给 N 赋了不同的值,测试结果如下

  1. N = 1010的结果 AC
  2. N = 200的结果 AC
  3. N = 120结果 #6 WA
  4. N = 160的结果 #6 WA
  5. N = 165的结果 #6 WA
  6. N = 167的结果 AC
  7. N = 166的结果 AC

我看本题讨论区有人在说 #6 过不了是因为 N 取小了,又根据我上面的测试,所以至少在我发贴时, N 的最大值其实是 165?

2023/10/1 17:09
加载中...