题解：P1983 [NOIP2013 普及组] 车站分级

· · 题解

图论建模

首先观察对于一条线路，我们可以从中直接得到什么信息：

假设这条线路的开头为 st，结尾为 ed，那么在 [st,ed] 的车站中，没有被选入线路的点一定比选入线路的点的级数至少少 1。

对于这一点条件，我们就可以建模了。

和差分约束一样，我们从某个点起连到所有比其多 1 的点的有向边，边权赋为 1。

然后拓扑排序跑最长路即可。不是最短路的原因是这些都是充分必要条件，每一个都必须满足，因此要选最长路。

这样建图是 O(n^2m) 的，虽然常数小，但还是容易被卡。

优化

发现复杂度瓶颈在于是一堆点往一堆点连边，所以我们从优化建边的方式入手：虚点优化。

我们把那些原来的起点们连多条向这个虚点的有向边，边权赋为 0；然后从这个虚点连多条向原来的终点们的有向边，边权赋为 1，这样就可以在 O(n) 的时间里完成 O(n^2) 的建边了。

总体复杂度是 O(nm)。

细节

边权全部赋值为 1 的做法

对于这种做法，非常万能，但我想不到。

写这种做法细节很少，我们无需处理起点是 0 是 1，直接全赋为 0 就好了，因为我们先不考虑起点。

最后统计答案的时候，我们只需要将 ans \div 2 +1 即可，\div2 是因为经过虚点一次会走两条边，要除回来；+1 是因为要加上起点。

同时注意有可能虚点入度为 0，所以虚点也要加入拓扑排序的初始化中，比如下面的数据：

in:
3 1
2 1 2

out:
1

代码如下：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,a[1005],dp[3005],rd[3005],ans=0;
vector<int>g[3005];
queue<int>q;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int s,st=0,ed=0;
        cin>>s;
        bitset<1005>isin;
        for(int j=1;j<=s;j++)
        {
            cin>>a[j];
            isin[a[j]]=1;
            if(j==1)st=a[j];
            if(j==s)ed=a[j];
        }
        int vt=n+i;
        for(int j=st;j<=ed;j++)
        {
            if(isin[j]==0)
            {
                g[j].push_back(vt);
                rd[vt]++;
            }
            else
            {
                g[vt].push_back(j);
                rd[j]++;
            }
        }
    }
    for(int i=1;i<=n+m;i++)
    {
        if(rd[i]==0)
        {
            q.push(i);
            dp[i]=0;
        }
    }
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(auto v:g[u])
        {
            dp[v]=max(dp[v],dp[u]+1);
            rd[v]--;
            if(rd[v]==0)
            {
                q.push(v);
            }
        }
    }
    for(int i=1;i<=n+m;i++)
    {
        ans=max(ans,dp[i]/2+1);
    }
    cout<<ans;
    return 0;
}

对于边权先赋为 1，后面再赋为 0 的做法

依然是上面的那个 hack 数据：

in:
3 1
2 1 2

out:
1

如果把入度为 0 的虚点的最长路也初始化为 1 的话，就会导致这组数据结果多一个 1。因此应该把虚点初始化为 0，其他点初始化为 1。

另外，不要读错题了，只有起点和终点之间的车站才受分级的约束，而不是全部车站。

代码如下：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,m,a[1005],dp[3005],rd[3005],ans=0;
struct edge{
    int to,w;
};
vector<edge>g[3005];
queue<int>q;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int s,st=0,ed=0;
        cin>>s;
        bitset<1005>isin;
        for(int j=1;j<=s;j++)
        {
            cin>>a[j];
            isin[a[j]]=1;
            if(j==1)st=a[j];
            if(j==s)ed=a[j];
        }
        int vt=n+i;
        for(int j=st;j<=ed;j++)
        {
            if(isin[j]==0)
            {
                g[j].push_back({vt,0});
                rd[vt]++;
            }
            else
            {
                g[vt].push_back({j,1});
                rd[j]++;
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        if(rd[i]==0)
        {
            q.push(i);
            dp[i]=1;
        }
    }
    for(int i=n+1;i<=n+m;i++)
    {
        if(rd[i]==0)
        {
            q.push(i);
            dp[i]=0;
        }
    }
    while(!q.empty())
    {
        int u=q.front();
        q.pop();
        for(auto tmp:g[u])
        {
            int v=tmp.to,w=tmp.w;
            dp[v]=max(dp[v],dp[u]+w);
            rd[v]--;
            if(rd[v]==0)
            {
                q.push(v);
            }
        }
    }
    for(int i=1;i<=n+m;i++)
    {
        ans=max(ans,dp[i]);
    }
    cout<<ans;
    return 0;
}