5.3.3 Network of Schools 校园网
时间： 1ms 内存：64M
描述：
一些学校连入一个电脑网络。那些学校已订立了协议：每个学校都会给其它的一些学校分发软件（称作“接受学校”）。注意如果 B 在 A 学校的分发列表中，那么 A 不必也在 B 学校的列表中。
你要写一个程序计算，根据协议，为了让网络中所有的学校都用上新软件，必须接受新软件副本的最少学校数目（子任务 A）。更进一步，我们想要确定通过给任意一个学校发送新软件，这个软件就会分发到网络中的所有学校。为了完成这个任务，我们可能必须扩展接收学校列表，使其加入新成员。计算最少需要增加几个扩展，使得不论我们给哪个学校发送新软件，它都会到达其余所有的学校（子任务 B）。一个扩展就是在一个学校的接收学校列表中引入一个新成员。
输入：
输入文件的第一行包括一个整数 N：网络中的学校数目（2 <= N <= 100）。学校用前 N 个正整数标识。接下来 N 行中每行都表示一个接收学校列表（分发列表）。第 i+1 行包括学校 i 的接收学校的标识符。每个列表用 0 结束。空列表只用一个 0 表示。
输出：
你的程序应该在输出文件中输出两行。第一行应该包括一个正整数：子任务 A 的解。第二行应该包括子任务 B 的解。
示例输入：
5
2 4 3 0
4 5 0
0
0
1 0示例输出：
1
2提示：
参考答案（内存最优[1272]）：
#include <iostream>
#include <cstring>
using namespace std;
#define MAXN 110
typedef struct edge
{
int t;
struct edge *next;
}edge;
int DFN[MAXN],LOW[MAXN];
bool instack[MAXN];
int Belong[MAXN];
int Stap[MAXN];
int Stop,Bcnt,Dindex;
edge* V[MAXN];
int n;
int res;
int indegree[MAXN],outdegree[MAXN];
int idcnt,odcnt;
void tarjan(int i)
{
int j;
DFN[i]=LOW[i]=++Dindex;
instack[i]=true;
Stap[++Stop]=i;
for(edge *e=V[i];e;e=e->next)
{
j=e->t;
if(!DFN[j])
{
tarjan(j);
if(LOW[j]<LOW[i])
LOW[i]=LOW[j];
}
else if(instack[j]&&DFN[j]<LOW[i])
LOW[i]=DFN[j];
}
if(DFN[i]==LOW[i])
{
Bcnt++;
do
{
j=Stap[Stop--];
instack[j]=false;
Belong[j]=Bcnt;
}while(j!=i);
}
}
void solve()
{
int i;
Stop=Bcnt=Dindex=0;
memset(DFN,0,sizeof(DFN));
memset(LOW,0,sizeof(LOW));
for(i=1;i<=n;i++)
if(!DFN[i])
tarjan(i);
}
int main()
{
int i;
int tmp;
edge* q=NULL;
edge* p=NULL;
memset(V,0,sizeof(V));
memset(instack,0,sizeof(instack));
cin>>n;
for(i=1;i<=n;i++)
{
while(cin>>tmp)
{
if(tmp==0)
break;
q=new edge;
q->t=tmp;
p=V[i];
if(V[i]==0)
{
V[i]=q;
q->next=NULL;
}
else
{
while(p->next)
p=p->next;
q->next=p->next;
p->next=q;
}
}
}
solve();
memset(indegree,0,sizeof(indegree));
memset(outdegree,0,sizeof(outdegree));
for(i=1;i<=n;i++)
{
for(edge *e=V[i];e;e=e->next)
{
if(Belong[i]!=Belong[e->t])
{
indegree[Belong[i]]++;
outdegree[Belong[e->t]]++;
}
}
}
idcnt=odcnt=0;
if(Bcnt==1)
cout<<"1"<<endl<<"0"<<endl;
else
{
for(i=1;i<=Bcnt;i++)
{
if(indegree[i]==0)
idcnt++;
if(outdegree[i]==0)
odcnt++;
}
cout<<odcnt<<endl;
if(idcnt>odcnt)
cout<<idcnt<<endl;
else
cout<<odcnt<<endl;
}
return 0;
}参考答案（时间最优[0]）：
#include<iostream>
#include<cstring>
using namespace std;
int g1[101][101],g2[101][101];
int into[101],out[101],belong[101];
bool vis[101],dis[101][101];
int n,m,I0,O0;
void g1dfs(int k)
{
vis[k]=true;
for (int i=1;i<=g1[k][0];i++)
if (!vis[g1[k][i]])
g1dfs(g1[k][i]);
}
void g2dfs(int k)
{
belong[k]=m;
for (int i=1;i<=g2[k][0];i++)
if (vis[g2[k][i]] && !belong[g2[k][i]])
g2dfs(g2[k][i]);
}
void solve()
{
memset(vis,false,sizeof(vis));
memset(belong,0,sizeof(belong));
m=0;
for (int i=1;i<=n;i++)
if (belong[i]==0)
{
g1dfs(i);
m++;
g2dfs(i);
memset(vis,false,sizeof(vis));
}
memset(dis,false,sizeof(dis));
for (int i=1;i<=n;i++)
for (int j=1;j<=g1[i][0];j++)
dis[belong[i]][belong[g1[i][j]]]=true;
memset(into,0,sizeof(into));
memset(out,0,sizeof(out));
for (int i=1;i<=m;i++)
for (int j=1;j<=m;j++)
if (i!=j && dis[i][j])
{
into[j]++;
out[i]++;
}
I0=0;O0=0;
for (int i=1;i<=m;i++)
{
if (into[i]==0) I0++;
if (out[i]==0) O0++;
}
}
void print()
{
if (m==1) printf("1\n0\n");
else
{
printf("%d\n",I0);
if (I0>O0) printf("%d\n",I0);
else printf("%d\n",O0);
}
}
int main()
{
scanf("%d",&n);
memset(g1,0,sizeof(g1));
memset(g2,0,sizeof(g2));
int x;
for (int i=1;i<=n;i++)
{
scanf("%d",&x);
while (x)
{
g1[i][++g1[i][0]]=x;
g2[x][++g2[x][0]]=i;
scanf("%d",&x);
}
}
solve();
print();
return 0;
}题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。