POJ 3268 Silver Cow Party

54 阅读 0 评论 36 点赞

我是靠谱客的博主含糊小丸子，最近开发中收集的这篇文章主要介绍POJ 3268 Silver Cow Party，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

这里写图片描述

题目大意：给出n个点m条边以及最后要回到的点t，接着是m条边，代表从牛a到牛b需要花费c时间，现在所有牛要到牛x那里去参加聚会，并且所有牛参加聚会后还要回来，给你牛x，除了牛x之外的牛，他们都有一个参加聚会并且回来的最短时间，从这些最短时间里找出一个最大值输出

解题思路：最短路径只需要从x到i的最短路径代表他们返回的最短路径，然后将所有边反过来，再从x到i的最短路径代表他们来参加聚会的最短路径，这样对应相加找出一个最大值就可以了。因为此题的数据是1000左右，所以弗洛伊德算法是不行的，但dijkstra算法和贝尔曼算法是可以解决的。

贝尔曼算法

//Memory: 260 KB        
//Time: 47 MS
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <map>
#include <cmath>
#include <queue>
#include <string>
#include <vector>
#include <set>

using namespace std;

#define ll long long
#define sc(x) scanf("%d",&x)
#define dsc(x,y) scanf("%d%d",&x,&y)
#define sssc(x)   scanf("%s",s)
#define sdsc(x,y) scanf("%s %s",x,y)
#define ssc(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define pr(x) printf("%dn",x)
#define FOR(i,n,o) for(int i=o;i<=n;i++)
#define lcr(a,b)  memset(a,b,sizeof(a))
#define Inf 1<<29

const int maxn=100005;
int m,n,t;
int dis[maxn],a[maxn];
struct node
{
    int u;
    int v;
    int w;
}q[maxn];
void bellman(int s)
{
        FOR(i,n,1)
        {
            dis[i]=Inf;
        }
        dis[s]=0;
        FOR(i,n,1)
        {
            FOR(j,m,1)
            {
                  if(dis[q[j].u]+q[j].w<dis[q[j].v])
                        dis[q[j].v]=dis[q[j].u]+q[j].w;
            }
        }
}
int main()
{
     while(~ssc(n,m,t))
     {
         int cnt=-1;
         FOR(i,m,1)
         {
             ssc(q[i].u,q[i].v,q[i].w);
         }
         bellman(t);
         FOR(i,n,1)
           a[i]=dis[i];
         FOR(i,m,1)
         swap(q[i].u,q[i].v);//交换 返回
         bellman(t);
         FOR(i,n,1)
         {
             a[i]+=dis[i];
             cnt=max(a[i],cnt);//选取最大值
         }
         pr(cnt);
     }
    return 0;
}

dijkstra算法

//Memory: 4120 KB       
//Time: 79 MS
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <map>
#include <cmath>
#include <queue>
#include <string>
#include <vector>
#include <set>

using namespace std;

#define ll long long
#define sc(x) scanf("%d",&x)
#define dsc(x,y) scanf("%d%d",&x,&y)
#define sssc(x)   scanf("%s",s)
#define sdsc(x,y) scanf("%s %s",x,y)
#define ssc(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define pr(x) printf("%dn",x)
#define FOR(i,n,o) for(int i=o;i<=n;i++)
#define lcr(a,b)  memset(a,b,sizeof(a))
#define Inf 1<<29

const int maxn=1005;
int m,n,t;
int dis[maxn],a[maxn],vis[maxn],mp[maxn][maxn];
void dij(int s)
{
       FOR(i,n,1)
       {
           vis[i]=0;
           dis[i]=mp[s][i];
       }
       vis[s]=1;
       dis[s]=0;
       FOR(i,n,1)
       {
            int to=-1;
            int d=Inf;
            FOR(j,n,1)
            {
                if(!vis[j]&&d>dis[j])
                {
                    d=dis[j];
                    to=j;
                }
            }
            if(to==-1)
                break;
            vis[to]=1;
            FOR(j,n,1)
            {
                if(!vis[j]&&dis[j]>dis[to]+mp[to][j])
                     dis[j]=dis[to]+mp[to][j];
            }
       }
}
void init()
{
     FOR(i,n,1)
     {
         FOR(j,n,1)
         {
            if(i!=j)
                mp[i][j]=Inf;
            else
                mp[i][j]=0;
         }
     }
}
int main()
{
     while(~ssc(n,m,t))
     {
         lcr(a,0);
         int cnt=-1;
         int u,v,w;
         init();
         FOR(i,m,1)
         {
             ssc(u,v,w);
             mp[u][v]=w;
         }
         dij(t);
         FOR(i,n,1)
         a[i]=dis[i];
         FOR(i,n,1)
         {
             FOR(j,i,1)
             {
                 swap(mp[i][j],mp[j][i]);//注意 这里要这样交换
             }
         }
         dij(t);
         FOR(i,n,1)
         {
             a[i]+=dis[i];
             cnt=max(a[i],cnt);
         }
         pr(cnt);
     }
    return 0;
}