pku 3408 多米若 bfs.txt

包括计算几何、特殊数据结构、组合数学等知识点的代码。每个代码对应一道ACM试题

#include <stdio.h>
#include <iostream>
#include <stdlib.h>
#include <vector>
#include <math.h>
#include <algorithm>
#include <iterator>
using namespace std;

//PKU 3408 多米若 BFS
#define NMAX 1005
#define MH make_heap
#define OH pop_heap
#define PH push_heap
#define PB push_back
#define OB pop_back

bool visited[NMAX];
int qnum[NMAX];
int len[NMAX];
int queue[NMAX*2];
int arc[NMAX][NMAX];//注意为什么不用int arc[][]

int bfs(int start,int num)
{
	int s,e,p,i,count=0;
	memset(visited,0,sizeof(visited));
	memset(len,0,sizeof(len));
	memset(queue,0,sizeof(queue));
	s=-1;e=0;
	queue[e]=start;
	len[start]=0;
	visited[start]=true;
	count++;
	while(s<e)
	{
		s++;
		p=queue[s];
		for(i=1;i<=qnum[p];i++)
		{
			if(visited[arc[p][i]]==false)
			{
				visited[arc[p][i]]=true;
				len[arc[p][i]]=len[p]+1;
				++e;
				queue[e]=arc[p][i];
				count++;
			}
		}
	}
	if(count==num) return len[queue[e]];
	else return -1;
}

void solve(int num)
{
	int i,ans=-1,ansq,t;
	for(i=1;i<=num;i++)
	{//枚举第一个倒下的牌
		t=bfs(i,num);
		if(ans<=t) {ans=t;ansq=i;}
	}
	if(ans<0) printf("impossible\n");
	else printf("%d\n%d\n",ans,ansq);
}

int main()
{
	int num,i,j,a;
	scanf("%d",&num);
//	for(i=1;i<=num;i++)
//		for(j=1;j<=num;j++) arc[i][j]=false;
	for(i=1;i<=num;i++)
	{
		scanf("%d",&qnum[i]);
		for(j=1;j<=qnum[i];j++)
		{
			scanf("%d",&a);
			arc[i][j]=a;
		}
	}
	solve(num);//如果num=1,应该输出 0 1
	return 0;
}