http://acm.timus.ru/problem.aspx?space=1&num=1004
计算最小非负环
1 #include <iostream>
2 using namespace std;
3 const int OO=10000000;
4 int n,m;
5 int map[111][111];
6 int d[111];
7 int pre[111];
8 int ans,alist[111],an;
9 bool v[111];
10
11 int findmin(){
12 int mm=OO,re=0;
13 for (int i=1;i<=n;++i) if (d[i]<mm&&!v[i]){
14 mm=d[i];
15 re=i;
16 }
17 return re;
18 }
19
20 void dij(int a,int b){
21 for (int k=1;k<n;++k){
22 int f=findmin();
23 if (f==0) break;
24 v[f]=true;
25 for (int i=1;i<=n;++i) if (d[f]+map[f][i]<d[i]){
26 d[i]=map[f][i]+d[f];
27 pre[i]=f;
28 }
29 }
30 }
31
32 void work(int a,int b){
33 int dis=map[a][b];
34 map[a][b]=map[b][a]=OO;
35 for (int i=1;i<=n;++i) d[i]=OO;
36 for (int i=1;i<=n;++i) v[i]=0;
37 for (int i=1;i<=n;++i) pre[i]=0;
38 d[a]=0;
39 dij(a,b);
40 if (d[b]+dis<ans){
41 ans=d[b]+dis;
42 int x=b;
43 an=0;
44 while (x!=0){
45 alist[++an]=x;
46 x=pre[x];
47 }
48 }
49 map[a][b]=map[b][a]=dis;
50 }
51
52 int main(){
53 scanf("%d",&n);
54 while (n!=-1){
55 for (int i=1;i<=n;++i)
56 for (int j=1;j<=n;++j) map[i][j]=OO;
57 scanf("%d",&m);
58 for (int i=1;i<=m;++i){
59 int a,b,c;
60 scanf("%d %d %d",&a,&b,&c);
61 if (c<map[a][b]) map[a][b]=map[b][a]=c;
62 }
63 ans=OO;
64 an=0;
65 for (int i=1;i<n;++i)
66 for (int j=i+1;j<=n;++j) if (map[i][j]<OO) work(i,j);
67 if (an==0) printf("No solution.\n");
68 else{
69 printf("%d",alist[an]);
70 for (int i=an-1;i>0;--i) printf(" %d",alist[i]);
71 cout<<endl;
72 }
73 scanf("%d",&n);
74 }
75 }
76
posted on 2008-11-04 09:48
Joseph 阅读(265)
评论(0) 编辑 收藏 引用