hdu1599 图的最小环问题的floyd算法+path输出

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1599

最小环的定义：经过一条简单路径（除起点每点只经过一次）回到起点成为环，并且环的总长度最小称为最小环。

关于floyd算法路径的计算方式参考博客：http://blog.sina.com.cn/s/blog_6fbae1120100xfdd.html

floyd算法很好的运用了dp的思想，dp是一个多阶段优化问题，因为最短路最多经过n-1个其他结点，所以最多迭代n次求出最终结果。我们用dp[m][i][j]表示前m个阶段的计算时（i,j）之间的最短距离，所以有dp[m][i][j]=min(dp[m-1][i][k]+dp[m-1][k][j])也就是用前m-1个阶段的（i,k）(k,j)之间的最短距离更新第m个阶段的（i,j）之间的最短距离，这个迭代过程最多是n次，因为第m次迭代会使得（i,j）之间经过k=0,1,2,m-1的距离更新成当前最小。可以滚动优化这个dp方程为dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j])，外层叠加n层迭代即可。

对于至少三个点的最小环，我们可以枚举最大的点k，在floyd更新的过程中以1,2....k-1为中转点的d[i][j]已经更新完毕，此时只要枚举比k小的i和j，其中i是k之前的一个结点，j是k之后的一个结点，且i不等于k，再加上d[i][j]就是以k为最大点，（i,k）&（k,j）为两条边的环的大小，通过两层（i,j）循环就能得出以k为最大点的环的最小值，在套一层k循环便能得出整个图的最小环。打印路径也是可以做到的，可以定义nxt[i][j]是从i到j的当前路径的i的下一个结点，所以只要在d[i][j]<d[i][k]+d[k][j]更新成功的时候对更新nxt[i][j]=nxt[i][k]就可以了，因为nxt[k][j]在之前已经更新过了.

这道题有一个注意点，就是inf的设置，我设置inf为0x7f7f7f7f时炸了，一看原来是对Map设置了inf的时候，floyd里面套了两个Map，所以越界了，所以最好inf设置合适点，比如0x7ffffff。

裸hdu1599代码：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef unsigned int ui;
 4 typedef long long ll;
 5 typedef unsigned long long ull;
 6 #define pf printf
 7 #define mem(a,b) memset(a,b,sizeof(a))
 8 #define prime1 1e9+7
 9 #define prime2 1e9+9
10 #define pi 3.14159265
11 #define lson l,mid,rt<<1
12 #define rson mid+1,r,rt<<1|1
13 #define scand(x) scanf("%llf",&x) 
14 #define f(i,a,b) for(int i=a;i<=b;i++)
15 #define scan(a) scanf("%d",&a)
16 #define mp(a,b) make_pair((a),(b))
17 #define P pair<int,int>
18 #define dbg(args) cout<<#args<<":"<<args<<endl;
19 #define inf 0x7ffffff
20 inline int read(){
21     int ans=0,w=1;
22     char ch=getchar();
23     while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
24     while(isdigit(ch))ans=(ans<<3)+(ans<<1)+ch-'0',ch=getchar();
25     return ans*w;
26 }
27 const int maxn=105;
28 int n,m,t;
29 int dis[maxn][maxn],Map[maxn][maxn];
30 int ans;
31 int cnt;
32 void floyd()
33 {
34     f(k,1,n)
35     {
36         f(i,1,k-1)
37             f(j,i+1,k-1)
38             {
39                 int tmp=dis[i][j]+Map[i][k]+Map[k][j];//注意inf两倍不能超过int范围orz 
40                 if(tmp<ans)ans=tmp;
41             }
42         f(i,1,n)
43             f(j,1,n)
44             {
45                 if(dis[i][j]>dis[i][k]+dis[k][j])
46                 {
47                     dis[i][j]=dis[i][k]+dis[k][j];
48                 }
49             }
50     }
51 }
52 int main()
53 {
54     //freopen("input.txt","r",stdin);
55     //freopen("output.txt","w",stdout);
56     std::ios::sync_with_stdio(false);
57     while(scanf("%d%d",&n,&m)!=EOF)
58     {
59         int u,v,w;
60         f(i,0,maxn-1)
61             f(j,0,maxn-1)dis[i][j]=Map[i][j]=inf;
62             ans=inf;
63         while(m--)
64         {
65             u=read(),v=read(),w=read();
66             if(Map[u][v]>w)
67             {
68                 Map[u][v]=Map[v][u]=dis[u][v]=dis[v][u]=w;
69             }
70         }
71         floyd();
72         if(ans==inf)pf("It's impossible.
");
73         else 
74             pf("%d
",ans);
75     }
76     return 0; 
77 }

输出最小环路径的代码如下：

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 typedef unsigned int ui;
 4 typedef long long ll;
 5 typedef unsigned long long ull;
 6 #define pf printf
 7 #define mem(a,b) memset(a,b,sizeof(a))
 8 #define prime1 1e9+7
 9 #define prime2 1e9+9
10 #define pi 3.14159265
11 #define lson l,mid,rt<<1
12 #define rson mid+1,r,rt<<1|1
13 #define scand(x) scanf("%llf",&x) 
14 #define f(i,a,b) for(int i=a;i<=b;i++)
15 #define scan(a) scanf("%d",&a)
16 #define mp(a,b) make_pair((a),(b))
17 #define P pair<int,int>
18 #define dbg(args) cout<<#args<<":"<<args<<endl;
19 #define inf 0x7ffffff
20 inline int read(){
21     int ans=0,w=1;
22     char ch=getchar();
23     while(!isdigit(ch)){if(ch=='-')w=-1;ch=getchar();}
24     while(isdigit(ch))ans=(ans<<3)+(ans<<1)+ch-'0',ch=getchar();
25     return ans*w;
26 }
27 const int maxn=105;
28 int n,m,t;
29 int dis[maxn][maxn],Map[maxn][maxn],path[maxn],nxt[maxn][maxn];
30 int ans;
31 int cnt;
32 void floyd()
33 {
34     f(k,1,n)
35     {
36         f(i,1,k-1)
37             f(j,i+1,k-1)
38             {
39                 int tmp=dis[i][j]+Map[i][k]+Map[k][j];//注意inf两倍不能超过int范围orz 
40                 if(tmp<ans)
41                 {
42                     ans=tmp;
43                     cnt=0;
44                     int p=i;
45                     while(p!=j)//最小环的路径 
46                     {
47                         path[cnt++]=p;
48                         p=nxt[p][j];
49                     }
50                     path[cnt++]=j;
51                     path[cnt++]=k;
52                 }
53             }
54         f(i,1,n)
55             f(j,1,n)
56             {
57                 if(dis[i][j]>dis[i][k]+dis[k][j])
58                 {
59                     dis[i][j]=dis[i][k]+dis[k][j];
60                     nxt[i][j]=nxt[i][k];
61                 }
62             }
63     }
64 }
65 int main()
66 {
67     //freopen("input.txt","r",stdin);
68     //freopen("output.txt","w",stdout);
69     std::ios::sync_with_stdio(false);
70     while(scanf("%d%d",&n,&m)!=EOF)
71     {
72         int u,v,w;
73         f(i,0,maxn-1)
74             f(j,0,maxn-1)dis[i][j]=Map[i][j]=inf,nxt[i][j]=j;
75             ans=inf;
76         while(m--)
77         {
78             u=read(),v=read(),w=read();
79             if(Map[u][v]>w)
80             {
81                 Map[u][v]=Map[v][u]=dis[u][v]=dis[v][u]=w;
82             }
83         }
84         floyd();
85         if(ans==inf)pf("It's impossible.
");
86         else 
87         {
88             pf("%d
",ans);
89             f(i,0,cnt-1)pf("%d ",path[i]);
90             pf("
");
91         }
92     }
93     return 0; 
94 }