新普京【洛谷P3659】[USACO17FEB]Why Did the Cow Cross the Road I G算法训练 安慰奶牛。

问题叙述:

奶牛们为什么要穿街?一个缘故只是以FJ的牧场的路程实在是极其多矣,使得奶牛们每天只能穿梭在大量底马路中央

FJ的牧场可以看成是相同片 N*N 的地步(3<=N<=100),N-1
漫长南北向的道路和 N-1
漫漫东西朝着的道贯通整个牧场,同时是每块田野的分界线。牧场的极致外面是一模一样圈高大的栅栏以备奶牛离开牧场。Bessie只要通过分离两片田野的征途,就可以于任何田野移动及和那个附近的原野里去(北,东,南或西)。当然,Bessie穿过每一样漫漫街都是得
T 时间之。(0<=T<=1,000,000)

发平等天,FJ邀请Bessie来他家下棋,Bessie从牧场的西北角出发,FJ的下于牧场的东南角。因为Bessie在中途可能会见饿,所以它各个走过三片田野就要告一段落下来,享用其所当田野上的异样的牧草(不包Bessie的视角,但是也许会见席卷终端FJ的家),牧场上有些田野的牧草长得较任何地方茂盛,所以Bessie对应的停留时间也会变长。

要帮帮Bessie计算出它活动至FJ家的卓绝缺日。

算法训练 安慰奶牛  

输入输出格式

输入格式:

先是实行两单数N,T。

搭下去 N 行,每行 N
个数表示每块田野Bessie需要留的工夫(每块最多无跳100,000),第一实践之第一块田野是牧场的西北角。

输出格式:

一行一个平头表示Bessie走至FJ家的绝缺乏日。

岁月限制:1.0s   内存限制:256.0MB

说明:

对样例,Bessie先向东面走过了三片田野(在“10”停留),再为南部移动两步,又为西走了一样步(在“5”停留),最后为南边移动相同步,再向东方挪相同步到FJ的小(不用停留),总共时间是15(停留时间)+16(穿街时)=31。

   

分析

转载Slager_Z大佬的题解。

题目讲述

代码

来自Slager_Z大佬。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<queue>
using namespace std;
int n,v[110][110];
long long dis[110][110],t;
bool vis[110][110];
struct node
{
    int x,y;
};
int dx[]={0,0,3,-3,1,1,2,2,-1,-1,-2,-2,0,0,1,-1};
int dy[]={3,-3,0,0,2,-2,1,-1,2,-2,1,-1,1,-1,0,0};
void spfa(int x,int y)
{
    queue<node>q;
    q.push((node){x,y});
    memset(dis,0x7f,sizeof(dis));
    dis[x][y]=0; vis[x][y]=1;
    do
    {
    node u=q.front();q.pop();
        vis[u.x][u.y]=0;
        for(int i=0;i<16;i++)
        {    int tx=u.x+dx[i],ty=u.y+dy[i];
            if(tx>=1&&tx<=n&&ty>=1&&ty<=n)
            {
             if(dis[tx][ty]>dis[u.x][u.y]+v[tx][ty]+t*3)
            {    
                dis[tx][ty]=dis[u.x][u.y]+v[tx][ty]+t*3;
                if(!vis[tx][ty])
                {
                    vis[tx][ty]=1;q.push((node){tx,ty});
                    }
                }
            }
        }
    }while(q.size()!=0);
}
int main()
{    ios::sync_with_stdio(false);
    cin>>n>>t;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cin>>v[i][j];
    spfa(1,1);
    long long ans;
    ans=dis[n][n];//参照题解:牛不可能直接到达,所以得枚举终点3步之内的所有点的值+位移的时间; 
    ans=min(ans,dis[n][n-1]+t);
    ans=min(ans,dis[n-1][n]+t);
    ans=min(ans,dis[n][n-2]+t*2);
    ans=min(ans,dis[n-2][n]+t*2);
    ans=min(ans,dis[n-1][n-1]+t*2);
    printf("%lld",ans);
    return 0;
}

 

Farmer
John变得特别累,他非思量还持续维护供奶牛里面供通行的道路。道路被用来连续N个牧场,牧场被连接地号码吧1届N。每一个牧场都是一个奶牛的下。FJ计划除去P条道路被尽量多的道,但是还要保持牧场中
的连通性。你首先要控制那些道路是索要保留的N-1久道路。第j长达双向道路连接了牧场Sj和Ej(1
<= Sj <= N; 1 <= Ej <= N;
Sj !=
Ej),而且走了它需要Lj的岁月。没有点儿只牧场是让同修以上的征途所连接。奶牛们分外伤心,因为她俩的交通系统被核减了。你待交各个一个奶牛的住处去劝慰他们。每次你到达第i独牧场的上(即使你都交过),你必花去Ci的年华跟奶牛交谈。你每个晚上都见面于与一个牧场(这是供应你挑选的)过夜,直到奶牛们还由悲伤中复苏过神来。在早
起来与夜间归来睡觉的下,你还要以及以公睡眠的牧场的奶牛交谈一次于。这样您才会成功而的
交谈任务。假设Farmer
John采纳了而的建议,请计算出使所有奶牛都给抚慰的起码时。

输入格式

第1实践包含两独整数N和P。

接下N行,每行包含一个平头Ci

属下去P行,每行包含三单整数Sj, Ej和Lj

出口格式

输出一个整数, 所急需之究竟时(包含和在你所于的牧场的奶牛的简单不善谈话时)。

样例输入

5 7
10
10
20
6
30
1 2 5
2 3 5
2 4 12
3 4 17
2 5 15
3 5 6

样例输出

176

数量规模以及约定

5 <= N <= 10000,N-1 <= P <= 100000,0 <= Lj
<= 1000,1 <= Ci <= 1,000。

思路:

立刻道题真将自身恶心到了,题目题意表述不根本,测试样例错误。

先拿对的输入样例给出:

5 7

10

10

20

6

30

1 2 5

2 3 5

2 4 12

3 4 17

2 5 15

3 5 6

4 5 12

出口还是 176

问题题意表述不到头,刚开头当是每日只去拜访一贱农场,只安慰一峰奶牛。然后忽略了同一商行要之说话:你每个晚上还见面在和一个牧场(这是供而拣的)过夜

正好起之思绪是这样的,先随限聊要出同颗最小生成树,然后访问的当儿在设想每个农场安慰之光阴

新普京 1

倘达到图,假设以边权获得了同粒最小生成树,然后起巅峰1出发,按照1~10之依次去看,那么每个终端的拜访是开就是是自己度数的2加倍,遍历一浅生成树。但是顶点1假如掉多1破

早晨打1启程,到2,然后于2这边过夜,第二天更打2出发到3…

下一场实际成功验证当时是错的+_+

关键的说话:你每个晚上且见面以和一个牧场(这是供应您选的)过夜

照上图的口舌,我每晚可能会见在不同的农场过夜,如果要于同一个农场过夜,说明每天只能挪一个分支然后回到

新普京 2

苟齐图,1->2->3->2->1当1此过夜  1->4->1 以1这里过夜 
1->5->6->5->1最终回到1

这样的话就会担保每晚在一个农场过夜

唯独这样到底出来的结果要么错误的,因为边权的数值改变了。如果一味的的本输出进来的数值作为边权,的确是一个最为小生成树,但是到底时间内还会受点权的影响,这样得出来的时刻连无克确保是绝小值。

因而,边权的数值需要改变。和点的法则一样,每个点的看次数是自己点度数的2加倍,始点多一致不善。所以我们可以拿点权加入到边权中。一久边的边权等于边权+两端顶点的点权。正好遍历一次于每条访问片差。再长刚开始点多下的同软就是可以了。

除此以外,在吐槽一下,为什么我于是非抽路径的并查集得下的结果不同那基本上,貌似以前为遇到过这种问题,老老实实用带路径压缩的吧。

AC代码:

#include<iostream>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
const int MAXN=100005;
struct node{
    int s;//始点
    int e;//终点
    int comfort_time;//边权
}edge[MAXN];//定义边集数组
int v[MAXN];//点权
int father[MAXN];
bool cmp1(node a, node b)//顶点权重比较函数
{
    return a.comfort_time<b.comfort_time;
}
int Find(int x)
{
    if(father[x]!=x)
    {
        int temp=Find(father[x]);
        father[x]=temp;
        return temp;
    }
    return x;
}
int krusal(int N, int P)
{
    sort(edge+1,edge+P+1,cmp1);
    int cost=0;
    for(int i=0;i<=N;i++)
    {
        father[i]=i;
    }
    int cnt=0;
    for(int i=1;i<=P;i++)
    {
        int fe=Find(edge[i].e);
        int fs=Find(edge[i].s);
        if(fs!=fe)
        {
            father[fs]=fe;
            cost+=edge[i].comfort_time;
            cnt++;
        }
        if(cnt==N-1)
            break;
    }
    return cost;
}
int main()
{
    int N,P;
    int cnt_time=0;
    scanf("%d %d",&N,&P);
    for(int i=1;i<=N;i++)
        scanf("%d",&v[i]);
    for(int i=1;i<=P;i++)
    {
        scanf("%d %d %d",&edge[i].e,&edge[i].s,&edge[i].comfort_time);
        edge[i].comfort_time=2*edge[i].comfort_time+v[edge[i].e]+v[edge[i].s];
    }
    cnt_time+=krusal(N,P);
    sort(v+1,v+N+1);
    cnt_time+=v[1];
    printf("%d\n",cnt_time);
    return 0;
}

第一种植想法的代码(警戒自己):

#include<iostream>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
using namespace std;
const int MAXN=100005;
struct node{
    int s;//始点
    int e;//终点
    int comfort_time;//边权
}edge[MAXN];//定义边集数组
struct vertex{
    int weight;//点权
    int postion;//输入进来时候的位置
}v[MAXN];//定义每个点自身花费的时间
int father[MAXN];
int flag[MAXN];//标记数组
int du[MAXN];//顶点的度数
bool cmp1(node a, node b)//顶点权重比较函数
{
    return a.comfort_time<b.comfort_time;
}
bool cmp2(vertex a, vertex b)//边权比较函数
{
    return a.weight<b.weight;
}
bool check(int N)//检查是否所有的点都已经遍历完成
{
    for(int i=1;i<=N;i++)
        if(!flag[i])
            return false;
    return true;
}
int Find(int x)
{
    if(father[x]!=x)
        father[x]=Find(father[x]);
    return father[x];
}
void unionn(int x, int y)
{
    int fa=Find(x);
    int fb=Find(y);
    if(fa!=fb)
        father[x]=y;
}
int krusal(int N, int P)
{
    sort(edge+1,edge+P+1,cmp1);
    int cost=0;
    memset(flag,false,sizeof(flag));
    memset(du,0,sizeof(du));
    for(int i=0;i<=N;i++)
    {
        father[i]=i;
    }
    int index=1;//选择边的下标
    while(!check(N))
    {
        if(Find(edge[index].e)!=Find(edge[index].s))
        {
            unionn(edge[index].e,edge[index].s);
            cost+=edge[index].comfort_time;
            flag[edge[index].e]=true;
            flag[edge[index].s]=true;
            du[edge[index].e]++;
            du[edge[index].s]++;
        }
        index++;
    }
    return cost;
}
int main()
{
    int N,P;
    int cnt_time=0;
    scanf("%d %d",&N,&P);
    for(int i=1;i<=N;i++)
    {
        scanf("%d",&v[i].weight);
        v[i].postion=i;
    }
    for(int i=1;i<=P;i++)
    {
        scanf("%d %d %d",&edge[i].e,&edge[i].s,&edge[i].comfort_time);
    }
    cnt_time+=2*krusal(N,P);
    sort(v+1,v+N+1,cmp2);
    cnt_time+=(du[v[1].postion]+1)*v[1].weight;
    for(int i=2;i<=N;i++)
    {
        cnt_time+=du[v[i].postion]*v[i].weight;
    }
    printf("%d\n",cnt_time);
    return 0;
}

相关文章

发表评论

电子邮件地址不会被公开。 必填项已用*标注