建边求助

P1983 [NOIP2013 普及组] 车站分级

一个简单的原因就是你 $line$ 数组开小了,这是你建边的过程,都快近似于 $n^2$ 条边了,开 $1000$ 肯定远远不够 ```cpp for(int j=stop[i][1];j<=stop[i][stop[i][0]];j++) { if(vis[j]) continue; for(int k=1;k<=stop[i][0];k++) { if(!pd[j][stop[i][k]]) { ind[stop[i][k]]++; addline(j,stop[i][k]); pd[j][stop[i][k]]=1; } } } ```
by bianshiyang @ 2023-10-06 09:24:24


这是我 $AC$ 代码,$edge$ 开了 $1e7+100$,就过了,不然 $RE$,还可能有其他问题 ```cpp #include <bits/stdc++.h> using namespace std; const int N = 1e3 + 100; const int M = 1e7 + 100; int n, m, s, u[N], ans[N], maxx; int head[N], cnt, du[N]; bool vis[N], vv[N][N]; queue<pair<int, int>> q; struct node { int nxt, to; } edge[M]; void add(int from, int to) { edge[++cnt].nxt = head[from]; edge[cnt].to = to; head[from] = cnt; } void toposort() { for (int i = 1; i <= n; i++) { if (du[i] == 0) { du[i]--; q.push(make_pair(i, 1)); } } while (!q.empty()) { int u = q.front().first, val = q.front().second; q.pop(); for (int e = head[u]; e; e = edge[e].nxt) { int v = edge[e].to; du[v]--; if (du[v] == 0) { q.push(make_pair(v, val + 1)); maxx = max(maxx, val + 1); du[v]--; } } } } int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= m; i++) { scanf("%d", &s); memset(vis, 0, sizeof(vis)); memset(u, 0, sizeof(u)); for (int j = 1; j <= s; j++) { scanf("%d", &u[j]); vis[u[j]] = 1; } for (int j = 1; j <= s; j++) { int t = u[j]; for (int k = u[1]; k <= u[s]; k++) { if (!vis[k] && !vv[k][t]) { add(k, t); du[t]++; vv[k][t] = 1; } } } } maxx = 1; toposort(); printf("%d\n", maxx); return 0; } ```
by bianshiyang @ 2023-10-06 09:26:56


|