头像

Dear.隆冬




离线:1小时前


最近来访(37)
用户头像
dellqang
用户头像
LcccY
用户头像
Dinas
用户头像
Stereo
用户头像
zymTokyoTech
用户头像
dsc182
用户头像
luxcgo
用户头像
封禁用户
用户头像
wxy_
用户头像
LAG-银河组织号
用户头像
沙漠之狐
用户头像
一只斑蝥
用户头像
国家级白嫖
用户头像
孤独なSpring
用户头像
EastPorridge
用户头像
云代码
用户头像
刘俊凯
用户头像
1lgorithm
用户头像
icebreaker
用户头像
SUPERDOGE

活动打卡代码 AcWing 342. 道路与航线

有负权边的单源最短路,看数据类型还是SPFA
难得一见USACO的题竟然卡了SPFA,只好加上SLF优化
SLF优化基本思路:

    1. 对于当前要入队的点to,如果dis[to]大于目前队头的dis,那么入队时加到队头
    2. 否则就加入队尾,优先处理dis值小的点会加快效率
#include <bits/stdc++.h>
using namespace std;
int n,p,r,start,dis[25010];
bool vis[25010];
struct road
{
    int to,len;
};
vector<road> way[25010];
void spfa()
{
    memset(dis,0x3f,sizeof(dis));
    dis[start]=0;
    deque<int> q;
    q.push_front(start);
    vis[start]=true;
    while(!q.empty())
    {
        int t=q.front();
        q.pop_front();
        vis[t]=false;
        for(int i=0;i<way[t].size();i++)
        {
            int to=way[t][i].to;
            if(dis[to]>dis[t]+way[t][i].len)
            {
                dis[to]=dis[t]+way[t][i].len;
                if(!vis[to])
                {
                    if(!q.empty()&&dis[to]<dis[q.front()]) q.push_front(to);
                    else q.push_back(to);
                    vis[to]=true;
                }
            }
        }
    }
}
int main()
{
    scanf("%d %d %d %d",&n,&r,&p,&start);
    for(int i=1;i<=r;i++)
    {
        int a,b,c;
        scanf("%d %d %d",&a,&b,&c);
        way[a].push_back({b,c});
        way[b].push_back({a,c});
    }
    for(int i=1;i<=p;i++)
    {
        int a,b,c;
        scanf("%d %d %d",&a,&b,&c);
        way[a].push_back({b,c});
    }
    spfa();
    for(int i=1;i<=n;i++)
        if(dis[i]>1e9) puts("NO PATH");
        else printf("%d\n",dis[i]);
    return 0;
}

2022年1月22日16:35:55




警官不是叫中森银三吗,题目开头第二行怎么变成了中村?



活动打卡代码 AcWing 340. 通信线路

题目大意

找一条从1到n的路径,使得路径上K条边的权值为零 后 剩下的最长边 最短

解题思路

基本想法还是dijkstra,但需要在dis数组上再加一维
$dis[i][j]$表示从起点到i的路径上使j条边权值为零,所剩的边中最大权值 的 最小值
考虑如何转移:
存边时对于每条无向边,再存一条端点相同但权值为0的边
如果这条边是0边,那么就转移到 $dis[to][now+1]$
否则就正常转移到 $dis[to][now]$
最后答案就是dis[n][k]
实际dijkstra就是一种动态规划
给dis数组加一维 就相当于 动态规划加一条限制条件
普通dijkstra复杂度是:$O(mlog_n)$
数组再加一维就是:$O(k·m·log_n)$

#include <bits/stdc++.h>
using namespace std;
int n,m,k,dis[1010][1010];
bool vis[1010][1010];
struct node
{
    int point,len,p;
    bool operator<(const node &x)const
    {
        return x.len!=len?x.len<len:x.p<p;//按距离排序,距离相等按用过的0边数量排序
    }
};
struct road
{
    int to,len;
};
vector<road> way[1010];
void dijkstra(int start)
{
    memset(dis,0x3f,sizeof(dis));
    dis[start][0]=0;
    priority_queue<node> q;
    q.push({1,0,0});
    while(!q.empty())
    {
        int t=q.top().point,now=q.top().p;
        q.pop();
        if(vis[t][now]) continue;
        vis[t][now]=true;
        for(int i=0;i<way[t].size();i++)
        {
            int to=way[t][i].to;
            if(way[t][i].len==0)//如果是0边
            {
                if(now<k)//还有能用的0边
                {
                    if(dis[to][now+1]>dis[t][now])//其实就是正常转移的len=0,就不用取max了
                    {
                        dis[to][now+1]=dis[t][now];
                        q.push({to,dis[to][now+1],now+1});
                    }
                    else continue;
                }
            }
            else
            {
                if(dis[to][now]>max(dis[t][now],way[t][i].len))
                {
                    dis[to][now]=max(dis[t][now],way[t][i].len);
                    q.push({to,dis[to][now],now});//一定要注意是取最大值,此题只求最大值
                }
            }
        }
    }
}
int main()
{
    scanf("%d %d %d",&n,&m,&k);
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        scanf("%d %d %d",&u,&v,&w);
        way[u].push_back({v,w});
        way[v].push_back({u,w});
        way[u].push_back({v,0});//加入0边
        way[v].push_back({u,0});
    }
    dijkstra(1);
    if(dis[n][k]>1e9) puts("-1");
    else printf("%d",dis[n][k]);
    return 0;
}

2022年1月20日14:39:22



活动打卡代码 AcWing 340. 通信线路

题目大意

找一条从1到n的路径,使得路径上K条边的权值为零 后 剩下的最长边 最短

解题思路

基本想法还是dijkstra,但需要在dis数组上再加一维
$dis[i][j]$表示从起点到i的路径上使j条边权值为零,所剩的边中最大权值 的 最小值
考虑如何转移:
存边时对于每条无向边,再存一条端点相同但权值为0的边
如果这条边是0边,那么就转移到 $dis[to][now+1]$
否则就正常转移到 $dis[to][now]$
最后答案就是dis[n][k]
实际dijkstra就是一种动态规划
给dis数组加一维 就相当于 动态规划加一条限制条件
普通dijkstra复杂度是:$O(mlog_n)$
数组再加一维就是:$O(k·m·log_n)$

#include <bits/stdc++.h>
using namespace std;
int n,m,k,dis[1010][1010];
bool vis[1010][1010];
struct node
{
    int point,len,p;
    bool operator<(const node &x)const
    {
        return x.len!=len?x.len<len:x.p<p;//按距离排序,距离相等按用过的0边数量排序
    }
};
struct road
{
    int to,len;
};
vector<road> way[1010];
void dijkstra(int start)
{
    memset(dis,0x3f,sizeof(dis));
    dis[start][0]=0;
    priority_queue<node> q;
    q.push({1,0,0});
    while(!q.empty())
    {
        int t=q.top().point,now=q.top().p;
        q.pop();
        if(vis[t][now]) continue;
        vis[t][now]=true;
        for(int i=0;i<way[t].size();i++)
        {
            int to=way[t][i].to;
            if(way[t][i].len==0)//如果是0边
            {
                if(now<k)//还有能用的0边
                {
                    if(dis[to][now+1]>dis[t][now])//其实就是正常转移的len=0,就不用取max了
                    {
                        dis[to][now+1]=dis[t][now];
                        q.push({to,dis[to][now+1],now+1});
                    }
                    else continue;
                }
            }
            else
            {
                if(dis[to][now]>max(dis[t][now],way[t][i].len))
                {
                    dis[to][now]=max(dis[t][now],way[t][i].len);
                    q.push({to,dis[to][now],now});//一定要注意是取最大值,此题只求最大值
                }
            }
        }
    }
}
int main()
{
    scanf("%d %d %d",&n,&m,&k);
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        scanf("%d %d %d",&u,&v,&w);
        way[u].push_back({v,w});
        way[v].push_back({u,w});
        way[u].push_back({v,0});//加入0边
        way[v].push_back({u,0});
    }
    dijkstra(1);
    if(dis[n][k]>1e9) puts("-1");
    else printf("%d",dis[n][k]);
    return 0;
}

2022年1月20日14:39:22



活动打卡代码 AcWing 1135. 新年好

解题思路

先从6个点(5个亲戚和家)分别为起点做dijkstra
把家记作0,5个亲戚分别记作1-5,存在r数组里
因为只有5个点,所以枚举它们的所有排列,依次加出总路程然后找最小值

#include <bits/stdc++.h>
using namespace std;
int n,m,minx=1e9,r[6]={1},dis[6][50010];//dis[u][i]表示从r[u]为起点到各个点的距离
bool vis[50010],mem[6];
struct node
{
    int to,len;
    bool operator<(const node &x)const
    {
        return x.len<len;
    }
};
vector<node> way[50010];
void dijkstra(int u,int start)//求r[u]为起点的最短路
{
    memset(vis,0,sizeof(vis));
    dis[u][start]=0;
    priority_queue<node> q;
    q.push({start,0});
    while(!q.empty())
    {
        int t=q.top().to;
        q.pop();
        if(vis[t]) continue;
        vis[t]=true;
        for(int i=0;i<way[t].size();i++)
        {
            int to=way[t][i].to;
            if(dis[u][to]>dis[u][t]+way[t][i].len)
            {
                dis[u][to]=dis[u][t]+way[t][i].len;
                q.push({to,dis[u][to]});
            }
        }
    }
}
void work(int u,int sum,int last)//u表示目前正枚举第u个到的点,sum为已经走的路程和,last记录上一个点对应的编号
{
    if(u>5)
    {
        minx=min(minx,sum);
        return;
    }
    for(int i=1;i<=5;i++)
        if(!mem[i])
        {
            mem[i]=true;
            work(u+1,sum+dis[last][r[i]],i);//last是0-5的编号值,而不是r[last]
            mem[i]=false;
        }
}
int main()
{
    memset(dis,0x3f,sizeof(dis));
    scanf("%d %d %d %d %d %d %d",&n,&m,&r[1],&r[2],&r[3],&r[4],&r[5]);
    for(int i=1;i<=m;i++)
    {
        int u,v,w;
        scanf("%d %d %d",&u,&v,&w);
        way[u].push_back({v,w});
        way[v].push_back({u,w});
    }
    for(int i=0;i<=5;i++) dijkstra(i,r[i]);//时刻分清i和r[i]的区别
    work(1,0,0);
    printf("%d",minx);
    return 0;
}

2022年1月19日16:34:48



活动打卡代码 AcWing 903. 昂贵的聘礼

解题思路

先不考虑等级问题,只是可以用别的物品和较低的价格来换物品
可以视作替代品向该物品连了一条权值为较低价格的有向边
对于直接原价购买物品,可以建立一个虚拟源点,向每个物品连一条边权为原价的有向边
最后再考虑等级问题,由于数据范围很小,我们用h[1]来表示1号物品的等级
等级区间的端点差是m,所以枚举该区间,区间左端点从h[1]-m一直左移到h[1],来保证1号物品可以得到
对于每个区间,都做一次dikstra,等级不符合的点不能走

#include <bits/stdc++.h>
using namespace std;
int m,n,h[110],dis[110],minx=1e9;
bool vis[110];
struct node
{
    int to,len;
    bool operator <(const node &x)const
    {
        return x.len<len;
    }
};
vector<node> way[110];
void dijkstra(int start,int l,int r)
{
    memset(dis,0x3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    dis[start]=0;
    priority_queue<node> q;
    q.push({start,0});
    while(!q.empty())
    {
        int t=q.top().to;
        q.pop();
        if(vis[t]) continue;
        vis[t]=true;
        for(int i=0;i<way[t].size();i++)
        {
            int to=way[t][i].to;
            if(h[to]<l||h[to]>r) continue;
            if(dis[to]>dis[t]+way[t][i].len)
            {
                dis[to]=dis[t]+way[t][i].len;
                q.push({to,dis[to]});
            }
        }
    }
}
int main()
{
    scanf("%d %d",&m,&n);
    for(int i=1;i<=n;i++)
    {
        int p,x;
        scanf("%d %d %d",&p,&h[i],&x);
        way[0].push_back({i,p});
        for(int j=1;j<=x;j++)
        {
            int u,w;
            scanf("%d %d",&u,&w);
            way[u].push_back({i,w});
        }
    }
    for(int i=0;i<=m;i++)
    {
        int l=h[1]-i;
        int r=l+m;
        dijkstra(0,l,r);
        minx=min(minx,dis[1]);
    }
    printf("%d",minx);
    return 0;
}

2022年1月19日15:59:45



活动打卡代码 AcWing 920. 最优乘车

题目大意

从1号点前往n号点;
有n辆不同路线的公交车,公交车只能以给定顺序行驶一次
求最少的换车次数

解题思路

在一条公交线路上,从前面的站牌向后面的站牌连一条有向边,边权都为1
跑一次dijkstra(因为边权是1,所以BFS也行),求出的是乘车数量的最小值
减去一然后输出

#include <bits/stdc++.h>
using namespace std;
int n,m,dis[510];
bool way[510][510],vis[510];
struct point
{
    int to,len;
    bool operator<(const point &x)const
    {
        return x.len<len;
    }
};
void dijkstra(int start)
{
    memset(dis,0x3f,sizeof(dis));
    dis[start]=0;
    priority_queue<point> q;
    q.push({start,0});
    while(!q.empty())
    {
        int t=q.top().to;
        q.pop();
        if(vis[t]) continue;
        vis[t]=true;
        for(int i=1;i<=n;i++)
            if(way[t][i])
            {
                if(dis[i]>dis[t]+1)
                {
                    dis[i]=dis[t]+1;
                    q.push({i,dis[i]});
                }
            }
    }
}
int work(string s,int &x)
{
    int sum=0;
    while(isdigit(s[x]))
    {
        sum*=10;
        sum+=s[x]-'0';
        x++;
    }
    return sum;
}//在字符串s中,从x的位置开始读出一个数字
int main()
{
    scanf("%d %d",&m,&n);
    string s;
    getline(cin,s);//读掉第一行最后的回车
    for(int i=1;i<=m;i++)
    {
        vector<int> stop;
        getline(cin,s);
        for(int i=0;i<s.length();i++)
            if(isdigit(s[i])) stop.push_back(work(s,i));//处理出该线路上的点
        for(int i=0;i<stop.size();i++)
            for(int j=i+1;j<stop.size();j++) way[stop[i]][stop[j]]=true;
    }
    dijkstra(1);
    if(dis[n]>1e9) puts("NO");
    else printf("%d",dis[n]-1);
    return 0;
}

2022年1月19日14:11:48



活动打卡代码 AcWing 2019. 拖拉机

解题思路

  1. 此题求要移走的草堆的最小值,在不移走草堆的情况下可以随便移动且对答案没有影响

  2. 可以使用双向队列BFS
    要转移到的点如果是空地,步数不加插入队头
    要转移到的点如果是草堆,步数加一插入队尾
    这样就可以保持BFS队列的单调性

#include <bits/stdc++.h>
using namespace std;
int n,beginx,beginy,dx[]={0,0,-1,1},dy[]={1,-1,0,0};
bool vis[1010][1010],g[1010][1010];//g数组记录该位置是否为草堆
struct point
{
    int x,y,temp;
};
void bfs()
{
    deque<point> q;
    q.push_front({beginx,beginy,0});
    vis[beginx][beginy]=true;
    while(!q.empty())
    {
        point t=q.front();
        q.pop_front();
        if(t.x==0&&t.y==0)
        {
            printf("%d",t.temp);
            return;
        }
        for(int i=0;i<4;i++)
        {
            int xx=t.x+dx[i],yy=t.y+dy[i];
            if(xx<0||xx>1001||yy<0||yy>1001||vis[xx][yy]) continue;
            if(g[xx][yy]) q.push_back({xx,yy,t.temp+1});
            else q.push_front({xx,yy,t.temp});
            vis[xx][yy]=true;
        }
    }
}
int main()
{
    scanf("%d %d %d",&n,&beginx,&beginy);
    for(int i=1;i<=n;i++)
    {
        int x,y;
        scanf("%d %d",&x,&y);
        g[x][y]=true;
    }
    bfs();
    return 0;
}

2022年1月17日13:34:44



活动打卡代码 AcWing 2060. 奶牛选美

算法:BFS

  1. 先做两次广搜,标记出两块斑点
  2. 将其中一块斑点的点都作为起点,另一块斑点的点在h数组上标记成2
  3. 再次bfs,到达标记是2的点就输出步数
#include <bits/stdc++.h>
using namespace std;
int n,m,h[60][60],dx[]={0,0,-1,1},dy[]={1,-1,0,0};
char g[60][60];
bool vis[60][60],mem[60][60];
struct point
{
    int x,y;
};
struct P
{
    int x,y,temp;
};
queue<P> Q;
void bfs(int beginx,int beginy,int &flag)
{
    queue<point> q;
    q.push({beginx,beginy});
    vis[beginx][beginy]=true;
    h[beginx][beginy]=flag;//起点标记成1,终点标记成2
    while(!q.empty())
    {
        point t=q.front();
        q.pop();
        if(flag==1)
        {
            Q.push((P){t.x,t.y,0});//如果是起点就加入队列
            mem[t.x][t.y]=true;
        }
        for(int i=0;i<4;i++)
        {
            int xx=t.x+dx[i],yy=t.y+dy[i];
            if(xx>0&&xx<=n&&yy>0&&yy<=m&&!vis[xx][yy]&&g[xx][yy]=='X')
            {
                q.push({xx,yy});
                h[xx][yy]=flag;
                vis[xx][yy]=true;
            }
        }
    }
    flag++;
}
int main()
{
    scanf("%d %d",&n,&m);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++) cin>>g[i][j];
    int t=1;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
            if(!vis[i][j]&&g[i][j]=='X') bfs(i,j,t);//标记起点斑块和终点斑块
    while(!Q.empty())
    {
        P t=Q.front();
        Q.pop();
        if(h[t.x][t.y]==2)
        {
            printf("%d",t.temp-1);
            return 0;
        }
        for(int i=0;i<4;i++)
        {
            int xx=t.x+dx[i],yy=t.y+dy[i];
            if(xx>0&&yy>0&&xx<=n&&yy<=m&&!mem[xx][yy])
            {
                Q.push({xx,yy,t.temp+1});
                mem[xx][yy]=true;
            }
        }
    }
    return 0;
}

2022年1月16日14:01:01




算法:差分约束

题目中求糖果总数的最小值,即每个小朋友分到糖果的最小值

所以是求图中到每个点的最长路,不等式为:$dis_j >= dis_t +len$,边为:t->j

当 x = 1 时,$x_A=x_B$ 变为 $ x_A > =x_B $ && $ x_A <= x_B $
当 x = 2 时,$x_A < x_B$ 变为 $ x_B >= x_A+1 $
当 x = 3 时,$x_A >= x_B$ 变为 $ x_A > =x_B+0 $
当 x = 4 时,$x_A > x_B$ 变为 $ x_A >= x_B+1 $
当 x = 5 时,$x_A <= x_B$ 变为 $ x_B >= x_A+0 $

注:从小于或大于通过+1变为大于等于或小于等于,只有整型变量才可以

SPFA求判断负环时,用栈来代替队列,因为在一些特殊情况下栈更快:

把刚入栈的点立刻弹出,可以优先检查这个点接下来的路径,很多情况下能更快找到负环

这种方法类似广搜变为深搜,但用栈的遍历顺序不完全是dfs序

#include <bits/stdc++.h>
using namespace std;
int n,m,idx,sum[100010];
long long dis[100010],ans;
bool vis[100010];
int to[300010],len[300010],nex[300010],head[300010];
void add(int a,int b,int c)
{
    to[idx]=b;
    len[idx]=c;
    nex[idx]=head[a];
    head[a]=idx++;
}//此题在时间上卡了用vector存边,恰好最后一个点TLE
bool spfa(int start)
{
    memset(dis,-0x3f,sizeof(dis));
    dis[start]=0;
    stack<int> q;
    q.push(start);
    vis[start]=true;
    while(!q.empty())
    {
        int t=q.top();
        q.pop();
        vis[t]=false;
        for(int i=head[t];i!=-1;i=nex[i])
            if(dis[to[i]]<dis[t]+len[i])
            {
                dis[to[i]]=dis[t]+len[i];
                sum[to[i]]=sum[t]+1;
                if(sum[to[i]]>n) return true;
                if(!vis[to[i]])
                {
                    q.push(to[i]);
                    vis[to[i]]=true;
                }
            }
    }
    return false;
}
int main()
{
    scanf("%d %d",&n,&m);
    memset(head,-1,sizeof(head));
    for(int i=1;i<=m;i++)
    {
        int op,a,b;
        scanf("%d %d %d",&op,&a,&b);
        if(op==1)
        {
            add(a,b,0);
            add(b,a,0);
        }
        else if(op==2) add(a,b,1);
        else if(op==3) add(b,a,0);
        else if(op==4) add(b,a,1);
        else add(a,b,0);
    }
    for(int i=1;i<=n;i++) add(0,i,1);
    if(spfa(0)) puts("-1");
    else
    {
        for(int i=1;i<=n;i++) ans+=dis[i];
        printf("%lld",ans);//最后最大的结果可能是n^2,所以用long long
    }
    return 0;
}

2021年11月7日15:43:37