P2746 P2812 [USACO5.3]校园网Network of Schools[SCC缩点]

题目描述

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

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

解析

这题除了数据有两个坑点之外，就是个板子，俩坑窝都踩了（窝太菜了。

坑点：1、scc缩点后可能只剩一个点，这个学校并不需要添加任何扩展。

2、子任务B要取得是入度为零的点的数目与出度为零的点的数目的较大值，显然扩展时对于这些度为零的点，每个出度为零的点都要连一条有向边到与它相连的入度为零的点。

参考代码

#include<cstdio>

#include<iostream>

#include<cmath>

#include<cstring>

#include<ctime>

#include<cstdlib>

#include<algorithm>

#include<queue>

#include<set>

#include<map>

#define N 50010

using namespace std;

inline int read()

{

	int f=1,x=0;char c=getchar();

	while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}

	while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}

	return x*f;

}

struct rec{

	int next,ver;

}g[N],G[N];

int head[N],headG[N],tot,totG,n,low[N],dfn[N];

int stack[N],top,c[N],cnt,ing[N],idt,scc[N],otg[N];

bool ins[N],v[N];

inline void add(int x,int y)

{

	g[++tot].ver=y;

	g[tot].next=head[x],head[x]=tot;

}

inline void addG(int x,int y)

{

	G[++totG].ver=y;

	G[totG].next=headG[x],headG[x]=totG;

	ing[y]++;otg[x]++;

}

inline void tarjan(int x)

{

	dfn[x]=low[x]=++cnt;

	stack[++top]=x,ins[x]=1;

	for(int i=head[x];i;i=g[i].next){

		int y=g[i].ver;

		if(!dfn[y]){

			tarjan(y);

			low[x]=min(low[x],low[y]);

		}

		else if(ins[y]) low[x]=min(low[x],dfn[y]);

	}

	if(low[x]==dfn[x]){

		int y;idt++;

		do{

			y=stack[top--],ins[y]=0;

			c[y]=idt;scc[idt]++;

		}while(x!=y);

	}

}

int main()

{

	n=read();

	for(int i=1;i<=n;++i){

		int v;

		while(scanf("%d",&v)&&v!=0)

			add(i,v);

	}

	for(int i=1;i<=n;++i)

		if(!dfn[i]) tarjan(i);

	for(int x=1;x<=n;++x)

		for(int i=head[x];i;i=g[i].next){

			int y=g[i].ver;

			if(c[x]==c[y]) continue;

			addG(c[x],c[y]);

		}

	int ans1=0,ans2=0;

	for(int i=1;i<=idt;++i){

		if(ing[i]==0) ans1++;

		if(otg[i]==0) ans2++;

	}

	cout<<ans1<<endl;

	if(idt==1)

		printf("0\n");

	else cout<<max(ans1,ans2)<<endl;

	return 0;

}

巴特西

P2746 P2812 [USACO5.3]校园网Network of Schools[SCC缩点]

题目描述

解析

参考代码

最新文章

热门文章