Beyond the Void
BYVoid
USACO 4.3.3 Buy Street Race 街道赛跑 race3

一道基础的连通分量的图论题。这个题默认了0为起点,N为终点,如果不放心可以再读入的时候判断起点和终点,即入度为0的点为起点,出度为0的点为终点。

该题有两问,第一问很简单,可以尝试去掉每一个点,判断从起点到终点是否有通路,如果没有则该点为“必经点”。

第二问终点在于理解题意。首先可以确定第二问的解集是第一问的子集,所以我们可以第一问得出的每个点深搜,记录下可以到达的点。然后去掉该点,从起点深搜。如果不存在两次深搜皆可到达的点,就说明它是分割点。

/*
ID: cmykrgb1
PROG: race3
LANG: C++
*/
#include <iostream>
#include <fstream>
#define MAX 101
using namespace std;
ifstream fi("race3.in");
ofstream fo("race3.out");

int adjl[MAX][MAX];
int ans[MAX][2];
bool used[MAX],tused[MAX];
int N,start,end;

void init()
{
	int a=0,i=0;
	while (a!=-1)
	{
		fi >> a;
		while (a>=0)
		{
			adjl[i][ ++adjl[i][0] ]=a;
			used[a]=true;
			fi >> a;
		}
		i++;
	}
	N=i-2;
	for (i=0;i<=N;i++)
	{
		if (adjl[i][0]==0)
			end=i;
		if (!used[i])
			start=i;
	}
}

void dfs3(int i)
{
	int k,j;
	for (k=1;k<=adjl[i][0];k++)
	{
		j=adjl[i][k];
		if (!tused[j])
		{
			tused[j]=true;
			dfs3(j);
		}
	}
}

void dfs2(int i)
{
	int k,j;
	for (k=1;k<=adjl[i][0];k++)
	{
		j=adjl[i][k];
		if (!used[j])
		{
			used[j]=true;
			dfs2(j);
		}
	}
}

void question2()
{
	int i,j,k;
	for (i=1;i<=N-1;i++)
	{
		memset(used,0,sizeof(used));
		memset(tused,0,sizeof(tused));
		dfs2(i);
		tused[i]=true;
		tused[0]=true;
		dfs3(0);
		k=1;
		for (j=0;j<=N;j++)
			if (j!=i && used[j] && tused[j])
			{
				k=0;
				break;
			}
		if (k)
			ans[ ++ans[0][1] ][1]=i;
	}
}

void dfs1(int i)
{
	int k,j;
	for (k=1;k<=adjl[i][0];k++)
	{
		j=adjl[i][k];
		if (!used[j])
		{
			used[j]=true;
			dfs1(j);
		}
	}
}

void question1()
{
	int i;
	for (i=1;i<=N-1;i++)
	{
		memset(used,0,sizeof(used));
		used[i]=true;
		dfs1(0);
		if (!used[N])
			ans[ ++ans[0][0] ][0]=i;
	}
}

void print()
{
	int i;
	fo << ans[0][0];
	for (i=1;i<=ans[0][0];i++)
		fo <<' ' << ans[i][0];
	fo << endl;
	fo << ans[0][1];
	for (i=1;i<=ans[0][1];i++)
		fo <<' ' << ans[i][1];
	fo << endl;
	fi.close();
	fo.close();
}

int main()
{
	init();
	question1();
	question2();
	print();
	return 0;
}

上次修改时间 2017-02-03

相关日志