简单的最大生成树，使用SPFA算法可获最优解。 注意： 1.这里要求输出最大路径，因此执行松弛操作时需要同时记录路径信息。这里使用并查集的思想：即每一个结点只记录它的上一个城市。输出时使用递归后序输出即可。 2.这里的终点为n+1，初始化时不要忘了[n+1]城市。同时输出时应将“n+1”改为1号城市
（PS:由于不是常用程序，这里没有free空间，读者可自行释放空间。） 以下为代码实现：
#include <iostream> #include <cstdio> #include <queue> #include <cstdlib> #include <cstring> #define IN freopen("in.txt", "r", stdin) #define OUT freopen("out.txt", "wb", stdout) #define max(a, b) (((a) > (b)) ? (a) : (b)) #define min(a, b) (((a) < (b)) ? (a) : (b)) #define N 110 using namespace std; struct node{ int point; //城市 int inter; //兴趣值 node *next; //下一节点 }; node *temp,city[N]; //建立出边表 int n,m; int SPFA() //函数任务：找到并返回最大值，同时将路径存入头结点 { int i; bool inQueue[N]; queue <node*> que; fill(inQueue+1,inQueue+n+2,false); for(i=1;i<=n;i++) city[i].inter=0; //此时将头结点作为最大路的存储器,头结点的point记录路径(用并查集的手法) temp=(node*)malloc(sizeof(node)); temp->point=1; que.push(temp); inQueue[1]=true; //在队列中 while(!que.empty()) { temp=que.front(); que.pop(); node *p=&city[temp->point]; while(p->next) //进行松弛操作 { if(city[p->next->point].inter<city[temp->point].inter+p->next->inter) //可进行松弛操作 { city[p->next->point].point=temp->point; city[p->next->point].inter=city[temp->point].inter+p->next->inter; if(!inQueue[p->next->point])//松弛成功且不在队列中 { inQueue[p->next->point]=true; node *other; other=(node*)malloc(sizeof(node)); other->point=p->next->point; que.push(other); } } p=p->next; } inQueue[temp->point]=false;//出队 } return city[n+1].inter; } void path(int pos) { if(pos!=1) path(city[pos].point); if(pos!=n+1) printf("%d->",pos); //第一个结点“1”忽略 } int main() { IN; int i,j,t,k; cin>>t; for(k=1;k<=t;k++) { cin>>n; for(i=1;i<=n;i++) { cin>>city[i].inter; city[i].next=NULL;//置空链 } city[i].inter=0; //n+1城市即原点 city[i].next=NULL; cin>>m; for(i=0;i<m;i++) { cin>>j; //接受起点 temp=(node*)malloc(sizeof(node)); cin>>temp->point; temp->inter=city[temp->point].inter; temp->next=city[j].next; city[j].next=temp; //插入新路径 } printf("CASE %d#\n",k); printf("points : %d\n",SPFA()); printf("circuit : "); path(n+1); printf("1\n"); if(k!=t) //输出格式要求，最后一个数据不得有空行 cout<<endl; } return 0; }