5.3.3 Network of Schools 校园网

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;  
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

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