洛谷 P2746 [USACO5.3]校园网Network of Schools

不念不忘少年蓝@ 2021-11-01 03:24 227阅读 0赞

### 题目描述 ###

一些学校连入一个电脑网络。那些学校已订立了协议：每个学校都会给其它的一些学校分发软件（称作“接受学校”）。注意即使 B 在 A 学校的分发列表中， A 也不一定在 B 学校的列表中。

你要写一个程序计算，根据协议，为了让网络中所有的学校都用上新软件，必须接受新软件副本的最少学校数目（子任务 A）。更进一步，我们想要确定通过给任意一个学校发送新软件，这个软件就会分发到网络中的所有学校。为了完成这个任务，我们可能必须扩展接收学校列表，使其加入新成员。计算最少需要增加几个扩展，使得不论我们给哪个学校发送新软件，它都会到达其余所有的学校（子任务 B）。一个扩展就是在一个学校的接收学校列表中引入一个新成员。

### 输入格式 ###

输入文件的第一行包括一个整数 N：网络中的学校数目（2 <= N <= 100）。学校用前 N 个正整数标识。

接下来 N 行中每行都表示一个接收学校列表（分发列表）。第 i+1 行包括学校 i 的接收学校的标识符。每个列表用 0 结束。空列表只用一个 0 表示。

### 输出格式 ###

你的程序应该在输出文件中输出两行。

第一行应该包括一个正整数：子任务 A 的解。

第二行应该包括子任务 B 的解。

### 输入输出样例 ###

输入 \#1复制

5
    2 4 3 0
    4 5 0
    0
    0
    1 0

输出 \#1复制

1
    2

### 说明/提示 ###

题目翻译来自NOCOW。

USACO Training Section 5.3

Tarjan模板题

首先进行tarjan缩点，重新建图

两个任务分别解决：

任务一：求有多少个缩完点后入度为0的强连通分量。

如果一个强连通分量入度为0，不会有其他的点给他送来软件，所以只能送给他一个副本。如果有边联向他，他就可以从父亲那里获得软件包

任务二：求 入度为0的点 和 出度为0的点 的最大值

第二问的意思就是加上多少条边可以使得整个图强连通。事实上，我们只需要让每个点的入度和出度都不为0

您可以想象环是什么样子（入度出度都是1）

解。

#include<bits/stdc++.h>
    #define inf 0x7fffffff
    #define ll long long
    using namespace std;
    int n;
    #define maxn 109
    vector<int> son[maxn];
    int dfn[maxn],low[maxn],cnt=0,scc_cnt=0,st[maxn];
    bool bein[maxn];
    int scc[maxn];
    int s=0;
    void Tarjan(int x)
    {
        dfn[x]=++s;
        low[x]=s;
        bein[x]=1;
        st[++cnt]=x;
        for(int i=0;i<son[x].size();i++)
        {
            int to=son[x][i];
            if(!dfn[to])
            {
                //to没有被访问过 
                Tarjan(to);
                low[x]=min(low[x],low[to]);
            }else if(bein[to])
            {
                low[x]=min(low[x],dfn[to]);
            }
        }
        if(low[x]!=dfn[x])return;
        int k;
        scc_cnt++;
        do
        {
            k=st[cnt--];
            bein[k]=0;
            scc[k]=scc_cnt;
        }while(k!=x);
    }
    struct node{
        int x,y;
    }e[maxn];
    int m=0;
    int in[maxn],out[maxn];//入度，出度 
    signed main()
    {
        scanf("%d",&n);
        for(int i=1;i<=n;i++)
        {
            int x;
            while(scanf("%d",&x)&&x!=0)
            {
                e[++m].x=i;
                e[m].y=x;
                son[i].push_back(x);
            }
        }
        for(int i=1;i<=n;i++)
        {
            if(!dfn[i])Tarjan(i);
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=0;j<son[i].size();j++)
            {
                if(scc[i]!=scc[son[i][j]])
                {
                    in[scc[son[i][j]]]++,out[scc[i]]++;
                }
                    
            }
        }
        int in0=0,out0=0;
        for(int i=1;i<=scc_cnt;i++)
        {
            if(in[i]==0)in0++;
            if(out[i]==0)out0++;
        }
        int ans=max(in0,out0);
        if(scc_cnt==1)ans=0;//当只有一个强连通分量的时候任务2的答案为1
        printf("%d\n%d\n",in0,ans);
        return 0;
    }

转载于:https://www.cnblogs.com/lzy-blog/p/11326612.html