?? pku 3408 多米若 bfs.txt
字號:
#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;
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -