90分求助，#9TLE

zhibuba @ 2020-08-21 17:16:17

#include <iostream>
#include <algorithm>
#include <vector>
#include <unordered_set>
#include <queue>
#include <iterator>

using namespace std;

unordered_set<int> G[1001];
int grade[1001], indegree[1001];
int n, m;

void build_graph()
{
    cin >> n >> m;
    while (m--)
    {
        int s;
        cin >> s;
        vector<int> a(s), b;
        copy_n(istream_iterator<int>(cin), s, begin(a));
        for (int i = a.front(), j = 0; i <= a.back(); i++)
        {
            if (i == a[j])
                j++;
            else
            {
                for (int v : a)
                    indegree[v] += G[i].insert(v).second;
            }
        }
    }
}

int ans;
queue<int> Q;
void topsort()
{
    for (int i = 1; i <= n; i++)
    {
        if (indegree[i] == 0)
        {
            Q.push(i);
            grade[i] = 1;
        }
    }
    while (!Q.empty())
    {
        int a = Q.front();
        Q.pop();
        for (auto b : G[a])
        {
            indegree[b]--;
            grade[b] = max(grade[b], grade[a] + 1);
            if (indegree[b] == 0)
                Q.push(b);
        }
        ans = max(ans, grade[a]);
    }
}

int main()
{
    ios::sync_with_stdio(false);
    build_graph();
    topsort();
    cout << ans;
    return 0;
}

by do_while_true @ 2020-08-21 17:35:35

@zhibuba 直接连边的复杂度不对吧

by do_while_true @ 2020-08-21 17:36:16

这个题的一半题解都是错的吧

by do_while_true @ 2020-08-21 17:38:11

此题跑拓扑排序的正确连边方法是建立虚拟节点，或者线段树优化建图

by zhibuba @ 2020-08-22 23:23:32

@do_while_true 虚拟节点是怎么弄？

by do_while_true @ 2020-08-22 23:44:03

@zhibuba 可以参考我这份代码

虚拟节点单独开出来，标记哪些节点是虚拟节点，在拓扑排序的时候遇到虚拟节点不更新答案。

#include<iostream>
#include<cstdio>
#include<queue>
#define mp std::make_pair
#define pp std::pair<int,int>
const int N=10100;
inline int read()
{
    int r=0,w=0;
    char ch=getchar();
    while(ch<'0'||ch>'9') {
        if(ch=='-') w=1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9') {
        r=(r<<3)+(r<<1)+(ch^48);
        ch=getchar();
    }
    return w ? ~r+1 : r;
}
int n,m,num;
int f[N<<1],ans,in[N<<1];
int fl[N<<1];
int cnt,head[N<<1];
struct node {
    int to,nxt;
}e[N*N<<1];
int s[N],vis[N];
std::queue<int>q; 
void add(int x,int y)
{
    e[++cnt].to=y;
    e[cnt].nxt=head[x];
    head[x]=cnt;
    in[y]++;
}
int main()
{
    n=read();m=read();
    num=n;
    for(int i=1;i<=m;i++) {
        int k=read();
        int bnt=0;
        for(int j=1;j<=k;j++)
            s[j]=read();
        for(int j=s[1];j<=s[k];j++)
            vis[j]=0;
        for(int j=1;j<=k;j++)
            vis[s[j]]=1,bnt++;
        if(bnt==s[k]-s[1]+1) continue;
        ++num;
        fl[num]=1; 
        for(int j=s[1];j<=s[k];j++) {
            if(!vis[j])
                add(j,num);
            else
                add(num,j);
        }
    }
    for(int i=1;i<=num;i++)
        if(!in[i])
            q.push(i),f[i]=1;
    while(!q.empty()) {
        int now=q.front();
        q.pop();
        ans=std::max(ans,f[now]);
        for(int i=head[now];i;i=e[i].nxt) {
            in[e[i].to]--;
            f[e[i].to]=std::max(f[e[i].to],f[now]+(fl[e[i].to] ? 0 : 1 ));
            if(!in[e[i].to])
                q.push(e[i].to);
        }
    }
    printf("%d",ans);
    return 0;
}

by do_while_true @ 2020-08-22 23:45:04

如果对代码哪里有疑问可以问我

by zhibuba @ 2020-08-22 23:58:14

@do_while_true 懂了，多谢

by theHermit @ 2020-08-29 09:34:09

@do_while_true

非常感谢~

对蒟蒻(我)特别有帮助！~