题解 P2812 【校园网络【[USACO]Network of Schools加强版】】

Dog_Two · 2018-10-31 16:28:17 · 题解

Orz我太弱了，没有看出来第二问答案就是第一问的答案，这里给出"计算"第二问答案的方法。

我们已经知道，第一问的答案也就是缩点后0入度结点的个数，我们的第二个任务也就是把图改造成存在包含所有强连通分量的强连通分量的新图。

假设缩点后有n个点。

显然，这样的一个强连通分量至少要有n条边，我们想要添加的边最少，就需要让原有的边尽量多。

我们设每一个入度为0的点和它能到达的所有结点构成一个“块”，可以发现，每个“块”之间是互不影响的。

每一个“块”能贡献的原有的边最多是l，l是每一“块”中最长路径的长度，可以用拓扑排序或记忆化搜索求得。

统计每个“块”的l，scc_cnt-sigma(l)即为答案。

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e4+10;
inline int inp(){
    register int x=0;
    char c;
    while(!isdigit(c=getchar()));
    do x=(x<<1)+(x<<3)+(c^48); while(isdigit(c=getchar()));
    return x;
}

int n,m;
vector<int>G[maxn];
void read(){
    cin>>n;
    for(int u=1;u<=n;++u){
        int v;
        while(v=inp()) G[u].push_back(v);
    }
}

stack<int>s;
int dfs_clock,scc_cnt,dfn[maxn],low[maxn],sccno[maxn];
void tarjan(int u){
    s.push(u);
    dfn[u]=low[u]=++dfs_clock;
    for(int i=0;i<G[u].size();++i){
        int v=G[u][i];
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(!sccno[v]) low[u]=min(low[u],dfn[v]);
    }
    if(dfn[u]==low[u]){
        ++scc_cnt;
        while(true){
            int x=s.top(); s.pop();
            sccno[x]=scc_cnt;
            if(x==u) break;
        }
    }
}

int deg[maxn];
vector<int>M[maxn];
void rebuild(){
    for(int u=1;u<=n;++u) if(!dfn[u]) tarjan(u);
    for(int u=1;u<=n;++u)
        for(int i=0;i<G[u].size();++i){
            int v=G[u][i];
            if(sccno[u]!=sccno[v]){
                M[sccno[u]].push_back(sccno[v]);
                ++deg[sccno[v]];
            }
        }
}

int f[maxn];
int dfs(int u){
    if(f[u]) return f[u];
    int res=0;
    for(int i=0;i<M[u].size();++i){
        int v=M[u][i];
        res=max(res,dfs(v)+1);
    }
    return f[u]=res;
}

void solve(){
    int ans=0;
    for(int u=1;u<=scc_cnt;++u) ans+=deg[u]==0;
    cout<<ans<<endl;
    int lng=0;
    for(int u=1;u<=scc_cnt;++u) if(deg[u]==0) lng+=dfs(u);
    cout<<scc_cnt-lng;
}

int main(){
    read();
    rebuild();
    solve();
    return 0;
}