最小环 hdu1599 poj1734

　　最小环用floyd改编。

　　hdu1599特殊一些。要求至少有三个不同的点，并且除了起点与终点重合外，中间不能有环。有点很奇怪，最大值不能为0x3f3f3f3f。

　　poj1374就没那么讲究。

 //hdu1599

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int N = , INF=;

 int Map[N][N], dist[N][N], pre[N][N];

 int mc;

 void fc(int n)

 {

     int i,j,k;

     mc=INF;

     for(i=;i<=n;i++)

     {

         for(j=;j<=n;j++)

         {

             dist[i][j]=Map[i][j];

             pre[i][j]=i;

         }

     }

     for(k=;k<=n;k++)

     {

         for(i=;i<k;i++)

         {

             for(j=;j<i;j++)

             {

                 if(dist[i][j]+Map[k][j]+Map[i][k]<mc)

                     mc=min(mc,dist[i][j]+Map[k][j]+Map[i][k]);

             }

         }

         for(i=;i<=n;i++)

         {

             for(j=;j<=n;j++)

             {

                 if(dist[k][j]!=INF&&dist[i][k]!=INF&&dist[i][j]>dist[i][k]+dist[k][j])

                 {

                     dist[i][j]=dist[i][k]+dist[k][j];

                     pre[i][j]=pre[k][j];

                 }

             }

         }

     }

 }

 void init(int n)

 {

     for(int i=;i<=n;i++)

     {

         Map[i][i]=;

         for(int j=;j<i;j++)

             Map[j][i]=Map[i][j]=INF;

     }

 }

 int main()

 {

     //freopen("test.txt","r",stdin);

     int n,m,i,j,k;

     while(scanf("%d%d",&n,&m)!=EOF)

     {

         init(n);

         while(m--)

         {

             scanf("%d%d%d",&i,&j,&k);

             if(i==j) continue;

             Map[i][j]=Map[j][i]=min(Map[i][j],k);

         }

         fc(n);

         if(mc!=INF) printf("%d\n",mc);

         else printf("It's impossible.\n");

     }

     return ;

 }

下面是poj1374

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 const int N=, INF=0x3f3f3f3f;

 int Map[N][N], dist[N][N], pre[N][N];

 int mc, p[N], t, n;

 void fc()

 {

     int i,j,k;

     mc=INF;

     t=;

     for(i=;i<=n;i++)

     {

         for(j=;j<=n;j++)

         {

             dist[i][j]=Map[i][j];

             pre[i][j]=i;

         }

     }

     for(k=;k<=n;k++)

     {

         for(i=;i<=n;i++)

         {

             if(Map[k][i]==INF) continue;

             if(i==k) continue;

             for(j=;j<=n;j++)

             {

                 if(i==j||j==k) continue;

                  if(dist[i][j]==INF||Map[j][k]==INF) continue;

                 int temp=dist[i][j]+Map[i][k]+Map[k][j];

                 if(temp<mc)

                 {

                     mc=temp;

                     int x=j;

                     t=;

                     while(x!=i)

                     {

                         p[t++]=x;

                         x=pre[i][x];

                     }

                     p[t++]=i;

                     p[t++]=k;

                 }

             }

         }

         for(i=;i<=n;i++)

         {

             if(dist[i][k]==INF) continue;

             for(j=;j<=n;j++)

             {

                 if(dist[i][j]>dist[i][k]+dist[k][j])

                 {

                     dist[i][j]=dist[i][k]+dist[k][j];

                     pre[i][j]=pre[k][j];

                 }

             }

         }

     }

 }

 int main()

 {

     int i,j,k,m;

     //freopen("test.txt","r",stdin);

     //freopen("out.txt","w",stdout);

     while(cin>>n>>m)

     {

         for(i=;i<=n;i++)

             for(j=;j<=n;j++)

                 Map[i][j]=INF;

         while(m--)

         {

             scanf("%d%d%d",&i,&j,&k);

             Map[j][i]=Map[i][j]=k<Map[i][j]?k:Map[i][j];

         }

         fc();

         if(mc==INF) printf("No solution.\n");

         else

         {

             printf("%d",p[]);

             for(i=;i<t;i++) printf(" %d",p[i]);

             printf("\n");

         }

     }

     return ;

 }

巴特西

最小环 hdu1599 poj1734

最新文章

热门文章