這是一個(gè)全新的概念，省賽上出現(xiàn)了這種題目，zoj 3332
http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3332圖中任意兩點(diǎn),至少存在一條有向邊，構(gòu)成一個(gè)哈密頓(好像和 哈密爾頓 不同)路；
對(duì)于一條以構(gòu)建的哈密頓路的n個(gè)點(diǎn)(第1個(gè)點(diǎn)到第n個(gè)點(diǎn),注意 第i個(gè)點(diǎn) 不一定是 點(diǎn)i ,eg,1 - 4 - 2 - 3,第2個(gè)點(diǎn)為4，第3個(gè)點(diǎn)為2，第4個(gè)點(diǎn)為3),
插入第n+1個(gè)點(diǎn)，肯定找到一條有向路與之相連
這里分3種情況
1> 第n + 1個(gè)點(diǎn) 與第一個(gè)點(diǎn)相連，使第n + 1個(gè)點(diǎn)成為第一個(gè)點(diǎn)
2> 最后一個(gè)點(diǎn)與第n+1個(gè)點(diǎn)相連，使第n + 1個(gè)點(diǎn)成為最后一個(gè)點(diǎn)
3> 能在原哈密頓路中找到一個(gè)相連的點(diǎn) ，第i個(gè)點(diǎn) 和 第i+1個(gè)點(diǎn) 使得 (第i個(gè)點(diǎn)與第n+1個(gè)點(diǎn) 且 第n+1個(gè)點(diǎn)與第i+1個(gè)點(diǎn))相連，所以在第i個(gè)點(diǎn)與第i+1個(gè)點(diǎn)中插入第n+1個(gè)點(diǎn)，這是典型的鏈?zhǔn)讲僮鳎?br>
因此,用STL里的list即可完成如上3步驟；
我只是略懂略懂，不足之處，請(qǐng)指教，并附上代碼
#include <iostream>
#define M 101
#include <list>
using namespace std;
bool f[ M ][ M ];
bool flag;
list <int> L;
list <int>::iterator it , pre;
void init (int n)
{
for (int i = 1;i <= n;++ i)
for (int j = 1;j <= n;++ j)
f[ i ][ j ] = false;
}
void solve (int n){
int i;
L.push_back(1);
for (i = 2;i <= n;++ i){
it = L.begin ();
if (f[ i ][ *it ]){
L.push_front(i);
continue;
}
it = L.end();
-- it;
if (f[ *it ][ i ]){
L.push_back(i);
continue;
}
it = pre = L.begin();
++ it;
while (it != L.end()){
if (f[ *pre ][ i ] && f[ i ][ *it ]){
L.insert(it , i);
break;
}
pre ++;
it ++;
}
}
}
int main(){
int t , n , i , k , g;
int a , b;
scanf ("%d" , &t);
while (t --){
L.clear();
scanf ("%d" , &n);
k = n * (n - 1) / 2;
init (n);
flag = true;
for (i = 1;i <= k;++ i){
scanf ("%d %d" , &a , &b);
f[ a ][ b ] = true;
}
solve (n);
if (L.size() != n){
puts ("Impossible");
continue;
}
for (it = L.begin(); it != L.end();++ it){
if (it != L.begin()) printf (" ");
printf ("%d" , * it);
}
printf ("\n");
}
return 0;
}