题解 P1983 【车站分级】

Sakura___ · 2017-10-12 20:55:13 · 题解

Accepted

100 168ms / 7.77MB

代码：1.82KB C++

大概是全洛谷最快的了

拓扑排序 + 虚点优化 + 线段树优化连边

边数 mlogn

原来是所有没有停靠的点向停靠的点连边

现在改为所有没有停靠的点向虚点连虚点向停靠的点连边

然后线段树优化

观察到停靠的点把区间分成了许多段将整个序列用线段树表示

每一段由不超过logn个线段树节点表示所以可以降边数

细节比较多看代码

‘’‘c++

#include <bits/stdc++.h>
using namespace std;
const int N = 1500;
int head[N << 3], top, n, m, tp, stp[N], in[N << 3], arc[N];
bool nd[N << 3];
struct Node
{
    int y, nxt;
    Node() {    }
    Node( int y, int nxt ) : y(y), nxt(nxt) {    }
} e[N * 700];
void Adde( int x, int y )
{
//    printf( "x %d  y %d\n", x, y );
    in[y]++;
    e[++top] = Node(y, head[x]), head[x] = top;
}
#define ls (bt << 1)
#define rs (bt << 1 | 1)
void Build( int bt, int lf, int rg )
{
    tp = max(tp, bt);
    if(lf == rg)
    {
        arc[lf] = bt;
        nd[bt] = 1;
        return;
    }
    int mid = (lf + rg) >> 1;
    Adde(ls, bt);
    Build(ls, lf, mid);
    Adde(rs, bt);
    Build(rs, mid + 1, rg);
}
void Query( int bt, int lf, int rg, int L, int R, int tmp )
{
    if(L > R) return;
    if(L <= lf && rg <= R)
    {
        Adde(bt, tmp);
        return;
    }
    int mid = (lf + rg) >> 1;
    if(L <= mid) Query(ls, lf, mid, L, R, tmp);
    if(R > mid) Query(rs, mid + 1, rg, L, R, tmp);
}
int que[N << 5], h, t, dep[N << 3];
void Bfs()
{
    for(int i = 1; i <= tp; ++i)
        if(!in[i]) que[++t] = i, dep[i] = nd[i];
    while(h < t)
    {
        int u = que[++h];
        for(int i = head[u]; i; i = e[i].nxt)
        {
            int v = e[i].y;
            in[v]--;
            dep[v] = max(dep[u] + nd[v], dep[v]);
            if(in[v] == 0) que[++t] = v;
        }
    }
}
int main()
{
    cin >> n >> m;
    Build(1, 1, n);
    for(int i = 1, cnt; i <= m; ++i)
    {
        scanf( "%d", &cnt );
        ++tp;
        for(int j = 1; j <= cnt; ++j)
            scanf( "%d", &stp[j] );
        for(int j = 1; j < cnt; ++j)
        {
            Adde(tp, arc[stp[j]]);
            Query(1, 1, n, stp[j] + 1, stp[j + 1] - 1, tp);
        }
        Adde(tp, arc[stp[cnt]]);
    }
    Bfs();
    int ans = 0;
    for(int i = 1; i <= n; ++i)
        ans = max(ans, dep[arc[i]]);
    cout << ans << endl;
    return 0;
} 
'''

题解 P1983 【车站分级 】

题解 P1983 【车站分级】