随笔 - 32  文章 - 2  trackbacks - 0
<2024年3月>
252627282912
3456789
10111213141516
17181920212223
24252627282930
31123456

常用链接

留言簿(3)

随笔档案

文章档案

搜索

  •  

积分与排名

  • 积分 - 8413
  • 排名 - 1249

最新评论

阅读排行榜

评论排行榜

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==0break;
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 阅读(255) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理