CF1608C Game Master

· · 题解

一道比较显然的隐式图问题。

转化

我们考虑一种情况：选手 A 想要获胜，但是存在一个选手 B，A 在两个场地中都无法击败 B，那么应该怎么处理呢？

我们需要找到一个选手 C 来击败 B，这样 A 就不需要直接面对 B 了。如果 A 也无法击败 C 呢？

显然，这个问题具有传递性。我们最终的目的就是要找到一条长得像 A\rightarrow K\rightarrow \cdots \rightarrow D \rightarrow C \rightarrow B 一样的链，使得 A 最终能够击败 K，那么 A 就能击败这条链上的所有选手。

思路

考虑对于每个选手建一个点，如果 A 能够在任意一个场地中击败 B，我们就从 A 到 B 连一条有向边。如果从 A 出发可以走到某一个点，说明 A 能够击败这个选手。如果从 A 出发可以遍历全图，说明 A 有可能取得冠军。

这样，对图上每个强连通分量 tarjan 缩点后，有且只有一个点没有入度，只有在这个点内的所有选手可能成为冠军，我们找到这个点就解决问题。

简单证明一下：如果缩点后，有边 u \rightarrow v，v 无论怎样都不可能打败 u ，就不可能是冠军。又因为可以成为冠军的人可以遍历到其他所有节点，那么他们一定被缩在一个点里，这个点没有入度且能遍历到其他所有节点。

建边的优化

在真正写代码的时候，我们会发现，如果真的把每个击败关系都建成边，可以达到 \mathbb O(n^2) 的复杂度，需要优化。实际上，考虑以下的情况： 如果有两条边 A \rightarrow B 和 B \rightarrow C,由于具有传递性， A \rightarrow C 这条边建了跟没建一样。

如果我们对 a_i 和 b_i 排序，只连接排序后大小相邻的两个选手之间的边，就能达到优化为 \mathbb O(n) 的效果。

代码

习惯压行，看着很丑陋。

#include<bits/stdc++.h>
using namespace std;
int t,n,head[100005],flag,dfn[100005],low[100005],st[100005],color[100005],timer,cnt;
bool in[100005];
struct star{
    int to,nxt;
}edge[400005],po[100005];
inline void add(int u,int v){
    edge[++flag]=(star){v,head[u]};head[u]=flag;
}
bool cmp(star a,star b){
    return a.nxt<b.nxt;
}
inline void clear(){
    memset(dfn,0,sizeof(dfn));memset(low,0,sizeof(low));
    memset(head,0,sizeof(head));flag=timer=cnt=0;
}
void tarjan(int id){
    dfn[id]=low[id]=++timer,in[id]=1,st[++st[0]]=id;
    for(int i=head[id];i;i=edge[i].nxt){
        int v=edge[i].to;
        if(!dfn[v]){
            tarjan(v);low[id]=min(low[id],low[v]);
        }
        else if(in[v])low[id]=min(low[id],dfn[v]);
    }
    if(dfn[id]==low[id]){
        cnt++;
        while(st[st[0]]!=id)color[st[st[0]]]=cnt,in[st[st[0]]]=0,st[0]--;
        color[id]=cnt,in[id]=0,st[0]--;
    }
}
int main(){
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);clear();
        for(int times=1;times<=2;times++){//读入a和b，相当于循环两次 
            for(int i=1;i<=n;i++){
               scanf("%d",&po[i].nxt);po[i].to=i;
            }
            sort(po+1,po+n+1,cmp);
            for(int i=2;i<=n;i++)add(po[i].to,po[i-1].to);
        }
        for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i);
        for(int i=1;i<=n;i++)
        for(int j=head[i];j;j=edge[j].nxt){
            int v=edge[j].to;if(color[i]!=color[v])in[color[v]]=1;
            //in之前是标记是否在tarjan栈内的，这里被我用来标记是否有入度了 
        }
        for(int i=1;i<=n;i++)putchar(in[color[i]]?'0':'1');putchar('\n');
    }
    return 0;
}