建边求助

P1983 [NOIP2013 普及组] 车站分级

oiyang @ 2023-08-28 21:01:38

我一开始用链式前向星建边，然后有WA有T，后来改成vector后就AC了。为啥？

这是过了的代码

#include <bits/stdc++.h>
using namespace std;
const int maxn=1010;
int ind[maxn];
int n,m,ans;
queue<pair<int,int> >q;
vector<int>line[maxn];
void topo()
{
    for(int i=1;i<=n;i++)
        if(ind[i]==0)
            q.push(make_pair(i,1));
    ans=1;
    while(!q.empty())
    {
        int num=q.front().first,level=q.front().second;
        q.pop();
        for(int i=0;i<(int)line[num].size();i++)
        {
            int v=line[num][i];
            ind[v]--;
            if(ind[v]==0)
            {
                q.push(make_pair(v,level+1));
                ans=max(ans,level+1);
            }
        }
    }
}
bool vis[maxn];
int stop[maxn][maxn];
bool pd[maxn][maxn];
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-')
            f=-f;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}
int main()
{
    n=read(),m=read();
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)
            vis[j]=0;
        stop[i][0]=read();
        for(int j=1;j<=stop[i][0];j++)
        {
            int x;
            x=read();
            stop[i][j]=x;
            vis[x]=1;
        }
        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]]++;
                    line[j].push_back(stop[i][k]);
                    pd[j][stop[i][k]]=1;
                }
            }
        }
    }
    topo();
    printf("%d",ans);
    return 0;
}

这是没过的代码


#include <bits/stdc++.h>
using namespace std;
const int maxn=1010;
int ind[maxn];
int head[maxn],cnt;
struct edge{
    int to,pre;
}line[maxn];
void addline(int u,int v)
{
    cnt++;
    line[cnt].to=v;
    line[cnt].pre=head[u];
    head[u]=cnt;
}
int n,m,ans;
queue<pair<int,int> >q;
void topo()
{
    for(int i=1;i<=n;i++)
        if(ind[i]==0)
            q.push(make_pair(i,1));
    ans=1;
    while(!q.empty())
    {
        int num=q.front().first,level=q.front().second;
        q.pop();
        for(int i=head[num];i;i=line[i].pre)
        {
            int v=line[i].to;
            ind[v]--;
            if(ind[v]==0)
            {
                q.push(make_pair(v,level+1));
                ans=max(ans,level+1);
            }
        }
    }
}
bool vis[maxn];
int stop[maxn][maxn];
bool pd[maxn][maxn];
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(!isdigit(ch))
    {
        if(ch=='-')
            f=-f;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return x*f;
}
int main()
{
    n=read(),m=read();
    for(int i=1;i<=m;i++)
    {
        for(int j=1;j<=n;j++)
            vis[j]=0;
        stop[i][0]=read();
        for(int j=1;j<=stop[i][0];j++)
        {
            int x;
            x=read();
            stop[i][j]=x;
            vis[x]=1;
        }
        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;
                }
            }
        }

    }
    topo();
    printf("%d",ans);
    return 0;
}

by bianshiyang @ 2023-10-06 09:24:24

一个简单的原因就是你 line 数组开小了，这是你建边的过程，都快近似于 n^2 条边了，开 1000 肯定远远不够

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:26:56

这是我 AC 代码，edge 开了 1e7+100，就过了，不然 RE，还可能有其他问题

#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;
}