首页 > 入门题:A+B题解
头像
亮亮201811121020926
编辑于 2020-08-23 21:05
+ 关注

入门题:A+B题解

题目描述
输入两个整数,求这两个整数的和是多少。

样例
样例输入:
3 4
样例输出:
7

算法一
广度优先搜索(宽度优先搜索)
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <algorithm>
#include <vector>
#include <deque>
#include <limits>
#include <string>
#include <sstream>
using namespace std;

const int oo_min=0xcfcfcfcf,oo_max=0x3f3f3f3f;

int n,m,t;
vector<int> f;
vector<int> e;
vector<int> u;
vector<int> pre;
vector<int> vis;
vector<vector<int> > c;
vector<vector<int> > p;
vector<vector<int> > ce;
vector<vector<int> > cw;
deque<int> q;

void add_edge_1(int x,int y,int c_v,int p_v)
{
    cw[x].push_back(y);
    c[x].push_back(c_v);
    p[x].push_back(p_v);
    ce[y].push_back(cw[x].size()-1);
    cw[y].push_back(x);
    c[y].push_back(0);
    p[y].push_back(-p_v);
    ce[x].push_back(cw[y].size()-1);
}

int bfs_1(int s,int t,int *flow,int *cost)
{
    f.resize(0);
    f.resize(cw.size(),0);
    f[s]=oo_max;
    e.resize(0);
    e.resize(cw.size(),-1);
    u.resize(0);
    u.resize(cw.size(),oo_max);
    u[s]=0;
    pre.resize(0);
    pre.resize(cw.size(),-1);
    pre[s]=s;
    vis.resize(0);
    vis.resize(cw.size(),0);
    for (q.resize(0),vis[s]=1,q.push_back(s);(!q.empty());vis[q.front()]=0,q.pop_front())
    {
        int now=q.front();
        for (int i=0;i<cw[now].size();i++)
            if (c[now][i]&&u[now]+p[now][i]<u[cw[now][i]])
            {
                f[cw[now][i]]=min(c[now][i],f[now]);
                e[cw[now][i]]=i;
                u[cw[now][i]]=u[now]+p[now][i];
                pre[cw[now][i]]=now;
                if (vis[cw[now][i]]==0)
                    vis[cw[now][i]]=1,q.push_back(cw[now][i]);
            }
    }
    (*flow)=f[t];
    (*cost)=u[t];
    return (pre[t]!=-1);
}

void min_cost_max_flow_1(int s,int t,int *flow,int *cost)
{
    int temp_flow,temp_cost;
    while (bfs_1(s,t,&temp_flow,&temp_cost))
    {
        for (int i=t;i!=s;i=pre[i])
            c[pre[i]][e[i]]-=temp_flow,c[i][ce[pre[i]][e[i]]]+=temp_flow;
        (*flow)+=temp_flow;
        (*cost)+=temp_cost;
    }
}

int a,b;

int main()
{
    scanf("%d%d",&a,&b);
    cw.resize(0);
    cw.resize(2);
    ce.resize(0);
    ce.resize(cw.size());
    c.resize(0);
    c.resize(cw.size());
    p.resize(0);
    p.resize(cw.size());
    add_edge_1(0,1,oo_max,a);
    add_edge_1(0,1,oo_max,b);
    int ans_flow=0,ans_cost=0;
    min_cost_max_flow_1(0,1,&ans_flow,&ans_cost);
    printf("%d\n",ans_cost);
}
算法二
深度优先搜索
#include <iostream>
#include <cstdio>

using namespace std;

typedef long long ll;

const int maxn = 1e6+10;

int a[maxn],n=2,res;

int dfs(int sum,int ii){
    if(ii>n)return -1;
    if(res==sum)return sum;
    int ans=dfs(sum+a[ii+1],ii+1);
    return ans==-1?res:ans;
}

int main(){
    for(int i=1;i<=n;i++){
        cin>>a[i];
        res+=a[i];
    }
    cout<<dfs(0,1)<<endl;
}
算法三
Dijkstra求最短路

#include<bits/stdc++.h>
using namespace std;
const int N=405;
struct Edge {
    int v,w;
};
vector<Edge> edge[N*N];
int n;
int dis[N*N];
bool vis[N*N];
struct cmp {
    bool operator()(int a,int b) {
        return dis[a]>dis[b];
    }
};
int Dijkstra(int start,int end)
{
    priority_queue<int,vector<int>,cmp> dijQue;
    memset(dis,-1,sizeof(dis));
    memset(vis,0,sizeof(vis));
    dijQue.push(start);
    dis[start]=0;
    while(!dijQue.empty()) {
        int u=dijQue.top();
        dijQue.pop();
        vis[u]=0;
        if(u==end)
            break;
        for(int i=0;i<edge[u].size();i++) {
            int v=edge[u][i].v;
            if(dis[v]==-1||dis[v]>dis[u]+edge[u][i].w) {
                dis[v]=dis[u]+edge[u][i].w;
                if(!vis[v]) {
                    vis[v]=true;
                    dijQue.push(v);
                }
            }
        }
    }
    return dis[end];
}
int main()
{
    int a,b;
    scanf("%d%d",&a,&b);
    Edge Qpush;
    Qpush.v=1;
    Qpush.w=a;
    edge[0].push_back(Qpush);
    Qpush.v=2;
    Qpush.w=b;
    edge[1].push_back(Qpush);
    printf("%d",Dijkstra(0,2));
    return 0;
}
算法四
Floyd算法
#include<bits/stdc++.h>
using namespace std;
long long n=3,a,b,dis[4][4];
int main()
{
    cin>>a>>b;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            dis[i][j]=2147483647;
    dis[1][2]=a,dis[2][3]=b;
    for(int k=1;k<=n;k++)
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
    cout<<dis[1][3];
    return 0;
}
转载....其他的不贴了...



全部评论

(3) 回帖
加载中...
话题 回帖

推荐话题

相关热帖

近期精华帖

热门推荐