hdu 1706 The diameter of graph(folyd计数)

题意：

给你一个图，定义图的直径为所有两点距离最短路中的最长的那条。

问图的直径为多长，有多少条。

题解：

将folyd改一改，加一个计数的数组就行了，然后就是注意重边的处理。

 1 #include<bits/stdc++.h>
 2 #define F(i,a,b) for(int i=a;i<=b;++i)
 3 using namespace std;
 4 
 5 const int N=107,inf=1e9+7;
 6 int n,m,mp[N][N],cnt[N][N];
 7 
 8 int main(){
 9     while(~scanf("%d%d",&n,&m))
10     {
11         F(i,1,n)F(j,1,n)mp[i][j]=(i==j?0:inf),cnt[i][j]=0;
12         int x,y,z;
13         F(i,1,m)
14         {
15             scanf("%d%d%d",&x,&y,&z);
16             if(mp[x][y]>z)
17             {
18                 mp[x][y]=mp[y][x]=z;
19                 cnt[x][y]=cnt[y][x]=1;
20             }else if(mp[x][y]==z)cnt[x][y]++,cnt[y][x]++;
21         }
22         F(k,1,n)F(i,1,n)F(j,1,n)
23         {
24             if(mp[i][j]>mp[i][k]+mp[k][j])
25             {
26                 mp[i][j]=mp[i][k]+mp[k][j];
27                 cnt[i][j]=cnt[i][k]*cnt[k][j];
28             }else if(mp[i][j]==mp[i][k]+mp[k][j])
29                 cnt[i][j]+=cnt[i][k]*cnt[k][j];
30         }
31         int mxd=0,ans=0;
32         F(i,1,n)F(j,1,n)if(i!=j&&mxd<mp[i][j]&&mp[i][j]!=inf)mxd=mp[i][j],ans=cnt[i][j];
33         else if(i!=j&&mxd==mp[i][j])ans+=cnt[i][j];
34         printf("%d %d
",mxd,ans/2);
35     }
36     return 0;
37 }

View Code