求任意圖的最長路。
其實(shí)思路很簡單，兩次bfs即可。
首先在圖中任意選擇一個點(diǎn)，對它進(jìn)行bfs擴(kuò)展，找到距該點(diǎn)最遠(yuǎn)的點(diǎn)，然后再一次bfs尋找最遠(yuǎn)點(diǎn)，此時找到的最遠(yuǎn)距離就是最長路的大小。
Pku 1383 Labyrinth 代碼：
#include <iostream>
#include <queue>
using namespace std;
int dir[4][2] = 
{{0, 1}, {0, -1}, {1, 0}, {-1, 0}};
struct point {
int x;
int y;
int step;
}temp, tt;
int n, m;
point q[1500000];
int hash[1002][1002];
char map[1002][1002];
int rear, front;
void bfs(point temp) {
int i;
memset(hash, 0, sizeof(hash));
rear = front = 0;
hash[ temp.x ][ temp.y ] = 0;
q[ rear ++ ] = temp;
while(front < rear) {
temp = q[ front++ ];
for(i = 0; i < 4; i++) {
tt.x = temp.x + dir[i][0];
tt.y = temp.y + dir[i][1];
tt.step = temp.step + 1;
if(tt.x < 0 || tt.y < 0 || tt.x >= n || tt.y >= m)
continue;
if(map[tt.x][tt.y] == '.' && !hash[ tt.x ][ tt.y ]) {
hash[ tt.x ][ tt.y ] = tt.step;
q[ rear ++ ] = tt;
}
}
}
}
int main() {
int t;
int i, j;
scanf("%d", &t);
while(t--) {
scanf("%d %d", &m, &n);
for(i = 0; i < n; i++) {
scanf("%s", map[i]);
}
int flag = 0;
for(i = 0; i < n; i++) {
for(j = 0; j < m; j++) {
if(map[i][j] == '.') {
temp.x = i;
temp.y = j;
temp.step = 0;
flag = 1;
break;
}
}
if(flag)
break;
}
bfs(temp);
temp.step = 0;
for(i = 0; i < n; i++) {
for(j = 0; j < m; j++) {
if(hash[i][j] > temp.step) {
temp.step = hash[i][j];
temp.x = i;
temp.y = j;
}
}
}
temp.step = 0;
bfs(temp);
temp.step = 0;
for(i = 0; i < n; i++) {
for(j = 0; j < m; j++) {
if(hash[i][j] > temp.step) {
temp.step = hash[i][j];
temp.x = i;
temp.y = j;
}
}
}
printf("Maximum rope length is %d.\n", temp.step);
}
}
Zju 3172 Extend 7-day Vacation 代碼：
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
struct point {
int now;
int step;
}temp, tt;
vector < int > vec[1001];
int hash[1001];
int n, m, x, y;
int i, j;
bool exsit[1001];
queue < point > q;
void bfs(point temp) {
int i;
while(!q.empty())
q.pop();
q.push( temp );
hash[ temp.now ] = 0;
memset(hash, -1, sizeof(hash));
while(!q.empty()) {
temp = q.front();
q.pop();
int size = vec[ temp.now ].size();
for(i = 0; i < size; i++) {
if(hash[ vec[temp.now][i] ] == -1) {
tt.now = vec[temp.now][i];
tt.step = temp.step + 1;
hash[ vec[temp.now][i] ] = tt.step;
q.push( tt );
}
}
}
}
int main() {
while(scanf("%d %d", &n, &m) != EOF) {
memset(exsit, 0, sizeof(exsit));
for(i = 0; i < n; i++)
vec[i].clear();
while(m --) {
scanf("%d %d", &x, &y);
vec[x].push_back( y );
vec[y].push_back( x );
exsit[x] = exsit[y] = 1;
}
for(i = 0; i < n; i++) {
if(exsit[i] == 1)
break;
}
temp.now = i;
temp.step = 0;
bfs(temp);
for(i = 0; i < n; i++) {
if(hash[i] > temp.step) {
temp.step = hash[i];
temp.now = i;
}
}
temp.step = 0;
bfs(temp);
for(i = 0; i < n; i++) {
if(hash[i] > temp.step) {
temp.step = hash[i];
temp.now = i;
}
}
if(temp.step < 7)
printf("Impossible\n");
else
printf("%d\n", temp.step + 1);
}
return 0;
}