「NOIP模拟赛」上白泽慧音

2014年9月10日2,9890

题目描述	在幻想乡，上白泽慧音是以知识渊博闻名的老师。春雪异变导致人间之里的很多道路都被大雪堵塞，使有的学生不能顺利地到达慧音所在的村庄。因此慧音决定换一个能够聚集最多人数的村庄作为新的教学地点。人间之里由N个村庄（编号为1..N）和M条道路组成，道路分为两种一种为单向通行的，一种为双向通行的，分别用1和2来标记。如果存在由村庄A到达村庄B的通路，那么我们认为可以从村庄A到达村庄B，记为(A,B)。当(A,B)和(B,A)同时满足时，我们认为A,B是绝对连通的，记为<A,B>。绝对连通区域是指一个村庄的集合，在这个集合中任意两个村庄X,Y都满足<X,Y>。现在你的任务是，找出最大的绝对连通区域，并将这个绝对连通区域的村庄按编号依次输出。若存在两个最大的，输出字典序最小的，比如当存在1,3,4和2,5,6这两个最大连通区域时，输出的是1,3,4。
输入格式	第1行：两个正整数N,M第2..M+1行：每行三个正整数a,b,t, t = 1表示存在从村庄a到b的单向道路，t = 2表示村庄a,b之间存在双向通行的道路。保证每条道路只出现一次。
输出格式	第1行： 1个整数，表示最大的绝对连通区域包含的村庄个数。第2行：若干个整数，依次输出最大的绝对连通区域所包含的村庄编号。
输入样例	5 51 2 1 1 3 2 2 4 2 5 1 2 3 5 1
输出样例	31 3 5
数据范围	对于60%的数据：N <= 200且M <= 10,000对于100%的数据：N <= 5,000且M <= 50,000

题解

tarjan模板

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<algorithm>
#include<queue>
#define pa pair<int,int>
#define inf 1000000000
#define ll long long
using namespace std;
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n,m,cnt,ind,top,scc,mx,ans;
int dfn[5005],low[5005],q[5005],last[5005],belong[5005],hav[5005];
bool inq[5005];
struct edge{int to,next;}e[100005];
void insert(int u,int v)
{
	e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;
}
void tarjan(int x)
{
	q[++top]=x;
	dfn[x]=low[x]=++ind;
	inq[x]=1;
	for(int i=last[x];i;i=e[i].next)
		if(!dfn[e[i].to])
		{
			tarjan(e[i].to);
			low[x]=min(low[x],low[e[i].to]);
		}
		else if(inq[e[i].to])low[x]=min(low[x],dfn[e[i].to]);
	int now=0;
	if(low[x]==dfn[x])
	{
		scc++;
		while(now!=x)
		{
			now=q[top];top--;
			inq[now]=0;
			belong[now]=scc;
			hav[scc]++;
		}
	}
}
int main()
{
	//freopen("classroom.in","r",stdin);
	//freopen("classroom.out","w",stdout);
	n=read();m=read();
	for(int i=1;i<=m;i++)
	{
		int u=read(),v=read(),t=read();
		if(t==1)insert(u,v);
		else 
		{
			insert(u,v);
			insert(v,u);
		}
	}
	for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i);
	for(int i=1;i<=n;i++)
		if(hav[belong[i]]>mx)
		{
			mx=hav[belong[i]];
			ans=belong[i];
		}
	printf("%d\n",mx);
	for(int i=1;i<=n;i++)
		if(belong[i]==ans)printf("%d ",i);
	return 0;
}

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<cstdlib>

#include<algorithm>

#include<queue>

#define pa pair<int,int>

#define inf 1000000000

#define ll long long

using namespace std;

inline int read()

{

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

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

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

return x*f;

}

int n,m,cnt,ind,top,scc,mx,ans;

int dfn[5005],low[5005],q[5005],last[5005],belong[5005],hav[5005];

bool inq[5005];

struct edge{int to,next;}e[100005];

void insert(int u,int v)

{

e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;

}

void tarjan(int x)

{

q[++top]=x;

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

inq[x]=1;

for(int i=last[x];i;i=e[i].next)

if(!dfn[e[i].to])

{

tarjan(e[i].to);

low[x]=min(low[x],low[e[i].to]);

}

else if(inq[e[i].to])low[x]=min(low[x],dfn[e[i].to]);

int now=0;

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

{

scc++;

while(now!=x)

{

now=q[top];top--;

inq[now]=0;

belong[now]=scc;

hav[scc]++;

}

int main()

{

//freopen("classroom.in","r",stdin);

//freopen("classroom.out","w",stdout);

n=read();m=read();

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

{

int u=read(),v=read(),t=read();

if(t==1)insert(u,v);

else

{

insert(u,v);

insert(v,u);

}

for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i);

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

if(hav[belong[i]]>mx)

{

mx=hav[belong[i]];

ans=belong[i];

}

printf("%d\n",mx);

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

if(belong[i]==ans)printf("%d ",i);

return 0;

}

« 「BZOJ1123」[POI2008] BLO 「BZOJ3391」[Usaco2004 Dec] Tree Cutting网络破坏 »

hzwer.com _ Home | http://hzwer.com

「NOIP模拟赛」上白泽慧音

分类目录

热门文章

Myfriends

近期评论