[Codeforces 1137C]Museums Tour

Link

这WA的有点难受2333333333333333333333333
一张边权为1的图,从点1处出发,如果走到某个点p经过的路径长度\bmod d的值属于一个特定的集合S_p,那么p点就能对答案做出1的贡献。点可以重复经过,但只能做一次贡献。问所有点的贡献最大和是多少。

Solution

首先把强连通分量缩起来。考虑强连通分量内的点的答案如何计算。
从分量内任意一个点出发BFS,可以得到一个能到达的(p,l\bmod d)二元组集合。为了简单,可以假设到达连通分量内的出发点已经走过的距离,那么对于d种距离,可以得到d个集合。而这d个集合中,(p,l\mod d)二元组的相对关系是不变的,因此一次BFS就可以得到d个集合的元素。
对于这d个集合,求一下每个集合各自有多少个点能产生贡献,然后在后面的DP中,每个集合的所有的点的DP值就是集合中产生贡献的点+集合中二元组的原来DP值的最大值。
求出(p,l\bmod d)的DP值之后,用它去更新后继SCC中的点。最后,在所有二元组的DP值中取max。
注意!由于必须从1开始,所有的合法值都只能从(1,0)二元组来!其他的所有初始值都必须是不合法的极小值!

Code

const int XN=1e5+11;

std::vector<int> G[XN],C[XN],scc[XN],lc[XN];

int low[XN],dfn[XN],stack[XN],dft,cc,belong[XN],top;
bool instack[XN];
void DFS(int u){
    dfn[u]=low[u]=++dft;
    stack[++top]=u;instack[u]=1;
    for(auto v : G[u])
        if(!dfn[v]){
            DFS(v);
            low[u]=std::min(low[u],low[v]);
        }else if(instack[v]){
            low[u]=std::min(low[u],dfn[v]);
        }
    if(dfn[u]==low[u])
        for(++cc;;){
            int x=stack[top--];
            instack[x]=0;
            scc[cc].push_back(x);
            belong[x]=cc;
            if(x==u) break;
        }
}

int d;
std::string status[XN];
auto Level=[&](int cur,int t)->int {
    return ((t-cur)%d+d)%d;
};


std::vector<int> T[XN];
void BFS(int c) {
    static bool ud[XN][55];
    std::queue<std::pair<int,int>> Q;
    Q.push({scc[c].front(),0});
    ud[Q.front().first][0]=1;
    while(!Q.empty()) {
        int pos,t;std::tie(pos,t)=Q.front();
        Q.pop();
        for(auto u : G[pos])
            if(belong[u]==c && !ud[u][(t+1)%d]) {
                ud[u][(t+1)%d]=1;
                Q.push({u,(t+1)%d});
            }
    }
    for(auto u : scc[c]) {
        for(int t=0;t<d;++t)
            if(ud[u][t])
                T[u].push_back(t);
    }
    lc[c].resize(d);
    for(int t=0;t<d;++t) {
        lc[c][t]=0;
        for(auto u : scc[c])
            for(int ut=0;ut<d;++ut)
                if(ud[u][ut] && status[u][(t+ut)%d]=='1') {
                    lc[c][t]++;
                    break;
                }
    }
}

int main() {
    freopen("input","r",stdin);
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    int n,m;std::cin>>n>>m>>d;
    for(int i=1;i<=m;++i) {
        int x,y;std::cin>>x>>y;
        G[x].push_back(y);
    }
    for(int i=1;i<=n;++i) {
        std::cin>>status[i];
    }
    for(int i=1;i<=n;++i)
        if(!dfn[i])
            DFS(i);
    for(int i=1;i<=n;++i)
        for(auto u : G[i])
            if(belong[u]!=belong[i])
                C[belong[i]].push_back(belong[u]);
    static int f[XN][55],deg[XN];
    for(int i=1;i<=cc;++i) {
        BFS(i);
        std::sort(C[i].begin(),C[i].end());
        C[i].erase(std::unique(C[i].begin(),C[i].end()),C[i].end());
        for(int u : C[i])
            deg[u]++;
    }
    for(int i=1;i<=n;++i)
        for(int t=0;t<d;++t)
            f[i][t]=-1e9;
    f[1][0]=0;
    std::queue<int> Q;
    for(int i=1;i<=cc;++i)
        if(!deg[i])
            Q.push(i);
    while(!Q.empty()) {
        int pos=Q.front();Q.pop();
        std::vector<int> lf(d,-1e9);//写成0最后没过!
        for(auto u : scc[pos])
            for(int t=0;t<d;++t)
                for(auto ut : T[u])
                    Enlarge(lf[Level(ut,t)],f[u][t]+lc[pos][Level(ut,t)]);
        for(auto u : scc[pos])
            for(int t=0;t<d;++t)
                for(auto ut : T[u])
                    Enlarge(f[u][t],lf[Level(ut,t)]);
        for(auto u : scc[pos])
            for(int t=0;t<d;++t)
                for(auto v : G[u]) {
                    if(belong[v]==belong[u])
                        assert(!Enlarge(f[v][(t+1)%d],f[u][t]));
                    Enlarge(f[v][(t+1)%d],f[u][t]);
                }
        for(auto u : C[pos])
            if(--deg[u]==0)
                Q.push(u);
    }
    for(int i=1;i<=cc;++i)
        assert(deg[i]==0);

    int Ans=0;
    for(int i=1;i<=n;++i)
        for(int t=0;t<d;++t)
            Enlarge(Ans,f[i][t]);
    std::cout<<Ans<<'\n';
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注