POJ1734 Sightseeing trip


floyd经典应用,求无向图最小环,由于floyd循环k层开始时保存的是$d[i,j]$经过编号最大为k-1的节点的最短路,

于是$min(d[i,j]+a[j,k]+a[k,i])$就是满足由编号不超过k的点构成的并且经过k点的最小环,所以从1-n循环后即可求得整个最小环

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<vector>
using namespace std;
inline int read()
{
    int x=0,t=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')t=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*t;
}
int n,m,pos[500][500];
int a[500][500],d[500][500],ans=0x3f3f3f3f;
vector<int> path;
void getpath(int x,int y)
{
    if(pos[x][y]==0) return;
    getpath(x,pos[x][y]);
    path.push_back(pos[x][y]);
    getpath(pos[x][y],y);
}
int main()
{
    n=read(),m=read();
    memset(a,0x3f,sizeof(a));
    for(int i=1;i<=n;i++) a[i][i]=0;
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        x=read(),y=read(),z=read();
        a[y][x]=a[x][y]=min(a[x][y],z);
    }
    memcpy(d,a,sizeof(a));
    for(int k=1;k<=n;k++)
    {
        for(int i=1;i<k;i++)
            for(int j=i+1;j<k;j++)
            if((long long)d[i][j]+a[j][k]+a[k][i]<ans)
            {
                ans=d[i][j]+a[j][k]+a[k][i];
                path.clear();
                path.push_back(i);
                getpath(i,j);
                path.push_back(j);
                path.push_back(k);
            }
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
            if(d[i][j]>d[i][k]+d[k][j])
            {
                d[i][j]=d[i][k]+d[k][j];
                pos[i][j]=k;
            }
    }
    if(ans==0x3f3f3f3f)
    {
        printf("No solution.\n");
        return 0;
    }
    for(int i=0;i<path.size();i++) printf("%d ",path[i]);
    return 0;
}

文章作者: songhn
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 songhn !
评论
 上一篇
POJ2976 Dropping tests POJ2976 Dropping tests
01分数规划裸题,给出n个物品有a b两个属性,选定n-k个元素,使$\sum{a_i}/\sum{b_i}$最大 #include<iostream> #include<cstdio> #include<cstring
2019-07-05
下一篇 
POJ 3662 Telephone Lines POJ 3662 Telephone Lines
这道题有两种解法,第二种是以后会写的动态规划,还有就是二分加最短路,这是最小化图中第k大的值,不难想到二分花费,对于大于此花费边权为1,其他为0,之后dijkstra最短路是否小于等于k,来进行判断,其实只有0和1的边也可以通过双端队列bf
2019-07-05
  目录