P1001 A+B Problem 题解

GWBailang · 2023-08-23 17:08:47 · 个人记录

原题传送

上次我们用二进制的运算来解决了 A+B 问题，但是那个思路可能不太容易想到，所以我们再换一种方法。

其实这道题可以用最短路来做，假设现在我们有一个图，图上有 3 个点，编号依次为 1 到 3 ，和 2 条边，权值分别为 a 和 b，a 和 b 是输入的两个数。然后就不难发现，从点 1 走到点 3 的最短路（权值）就是 a+b 的和。

有各种算法可以来求最短路，这里选择用 SPFA，因为 SPFA 可以计算负数加法。

时间复杂度为O(1)。

可以说这是道图论的模版题的模版题了（比模版题还模版的题）。而且最短路算法不仅可以计算 a+b 的值，有几个加数（只要能存的下）都可以计算。比之前那两种算法要好用多了。

代码：

#include<bits/stdc++.h>
using namespace std;
#define N 2
//要相加的数的个数
//可以更改这个值，然后就能让多个数相加
struct Node{
    long long v,w,nxt;
}bian[N+5];//存边
long long bnt;
long long head[N+5];
void add(long long u,long long v,long long w){
    bian[++bnt]={v,w,head[u]};
    head[u]=bnt;
}//加边的函数
long long dis[500005];//从1号点到i号点的最短路
bool sf[500005];
long long vis[500005];
queue<long long>q;
bool spfa(long long s){//SPFA模版
    memset(dis,0x3f,sizeof(dis));
    memset(vis,0,sizeof(vis));
    dis[s]=0;
    sf[s]=true;
    vis[s]=1;
    q.push(s);
    while(!q.empty()){
        long long s=q.front();q.pop();
        sf[s]=false;
        for(long long j=head[s];j;j=bian[j].nxt){
            long long v=bian[j].v,w=bian[j].w;
            if(dis[v]>dis[s]+w){
                dis[v]=dis[s]+w;
                if(!sf[v]){
                    sf[v]=1;
                    vis[v]++;
                    if(vis[v]>=N)return false;
                    q.push(v);
                }
            }
        }
    }
    return true;
}
int main(){
    long long w;
    for(long long i=1;i<=N;i++){
        cin>>w;
        add(i,i+1,w);//存图要存成有向图
    }
    spfa(1);
    cout<<dis[N+1]<<endl;//两个加数，3个点，所以是N+1号点
    return 0;
}

最后，由于这个程序改一下开头的 #define N 2，就能计算很多个数相加的和，所以还是开了 long long。