naoqi机器人总结23

基础算法

P1195 口袋的天空 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

/* 如果n个点被n-k条边连接的话，这一定是k棵树。选择代价最小的边连起来。所以给每条可以连的边按代价从小到大排个序，然后连n-k条边造k个最小生成树就可以了。
*/
#include
#include
#include
#include
#include
#define N 1005
using namespace std;
int n,m,k,x,y,l,sum,ans;
int fa[N];struct Edge
{int u,v,w;
}edge[N*10];bool operator <(Edge a,Edge b) //重置运算符的函数
{return a.w}int find(int x)
{return fa[x]==x?fa[x]:fa[x]=find(fa[x]);
}int main()
{scanf("%d%d%d",&n,&m,&k);for(int i=1;i<=n;i++) fa[i]=i;for(int i=1;i<=m;i++){scanf("%d%d%d",&edge[i].u,&edge[i].v,&edge[i].w);}sort(edge+1,edge+m+1); //按代价升序排列 for(int i=1;i<=m;i++){int fx=find(edge[i].u),fy=find(edge[i].v);if(fx!=fy) //如果这两个点不在同一棵树中 {fa[fx]=fy;sum++; //连一条边，让它们合并成为一棵树 ans+=edge[i].w; //加上合并的代价 }if(sum==n-k) //已经连好了k棵树 {printf("%d",ans);return 0;}}puts("No Answer"); //不可能连好 return 0;
}


P1396 营救 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

#include
using namespace std;int n,m,s,t,a[20001];struct each
{int x,y,cost;
}b[20001];//存边bool com(each x,each y)
{return x.cost}int find(int x)//并查集基本操作
{if(a[x]==0)return x;a[x]=find(a[x]);return a[x];
}
int main()
{cin>>n>>m>>s>>t;for(int i=1;i<=m;i++){cin>>b[i].x>>b[i].y>>b[i].cost;}sort(b+1,b+m+1,com);//排序for(int i=1;i<=m;i++)//克鲁斯卡尔最小生成树连边{int X=find(b[i].x),Y=find(b[i].y);if(X!=Y)a[X]=Y;if(find(s)==find(t))//如果联通直接输出退出{cout<}