信息
- ID
- 6642
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 1
- 标签
- (无)
- 递交数
- 4
- 已通过
- 3
- 上传者
把a
, b
作为边权,很容易想到图论算法。
上代码:
方法1:
#include<bits/stdc++.h>
using namespace std; //Dijkstra O(n^2)
int main(){
int a[3][3]={{2147483640,2147483640,2147483640},{2147483640,2147483640,2147483640},{2147483640,2147483640,2147483640}};
scanf("%d %d",&a[0][1],&a[1][2]);
for(int i=1;i<=2;i++){
for(int j=i;j<=2;j++)
if(a[0][i]+a[i][j]<a[0][j]&&a[i][j]<1000000001&&a[0][i]<1000000001)
a[0][j]=a[0][i]+a[i][j];
}
printf("%d\n",a[0][2]);
return 0;
}
方法2:
#include<bits/stdc++.h>
using namespace std;//Kruskal O(n^2)
struct Node{
int x1,x2,s;
}data[10];
int ans=0,dad[5],tot=2;
bool cmp(Node a,Node b){
return a.s>b.s;
}
int father(int a){
while(dad[a]!=a)a=dad[a];
return a;
}
int main() {
scanf("%d %d",&data[1].s,&data[2].s);
data[1].x1=1;data[1].x2=2;
data[2].x1=2;data[2].x2=3;
sort(data+1,data+tot+1,cmp);
for(int i=1;i<=tot+1;i++)dad[i]=i;
for(int i=1;i<=tot;i++){
if(father(data[i].x1)!=father(data[i].x2)){
dad[data[i].x1]=data[i].x2;
ans+=data[i].s;
}
}
printf("%d\n",ans);
return 0;
}
方法3:
#include<bits/stdc++.h>
using namespace std;//Floyd O(n^3)
int main() {
int n=3,a[3][3]={{2147483640,2147483640,2147483640},{2147483640,2147483640,2147483640},{2147483640,2147483640,2147483640}};
scanf("%d %d",&a[1][2],&a[2][3]);
a[2][1]=a[1][2];
a[3][2]=a[2][3];
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
for(int k=1;k<=n;k++){
if(a[j][k]<=1e9&&a[i][k]<=1e9&&i!=j&&k!=j&&i!=k){
if(a[i][j]>a[i][k]+a[j][k])a[i][j]=a[i][k]+a[j][k];
}
}
}
}
printf("%d\n",a[1][3]);
return 0;
}
大功告成。