输入两个整数,求这两个整数的和是多少。
样例
样例输入:
3 4
样例输出:
7
算法一
广度优先搜索(宽度优先搜索)
深度优先搜索
Dijkstra求最短路
Floyd算法
广度优先搜索(宽度优先搜索)
#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) 回帖