最小生成树 prim和kruskal 都是贪心
- prim类似dijkstra，每次选中不在已访问集合中的d最小的点u加入集合，这里面的d是与已访问集合的距离，dijkstra是与起点的距离
- 只通过u调整未访问点
- 注意因为写代码的时候初始化G为0，所以这里面要加上判断g不为0才能用于修改未访问的d
- 走n轮（因为第一次初始起点也要选择）（dijkstra也是n轮）
#include<stdio.h> #include<iostream> #include<string.h> using namespace std; const int INF=100000; const int maxn=1000; int G[maxn][maxn],d[maxn]; bool visit[maxn]; int n,m; int prim() { int ans=0; memset(visit,0,sizeof(visit)); fill(d,d+n,INF); d[0]=0; for(int i=0;i<n;i++) { int u=-1,minnum=INF; for(int j=0;j<n;j++) { if(visit[j]==false && d[j]<minnum) { u=j; minnum=d[j]; } } if(u==-1) return ans; //printf("u:%d du:%d ",u,d[u]); ans+=d[u]; visit[u]=true; for(int j=0;j<n;j++) { if(visit[j]==false && G[u][j]>0 &&G[u][j]<d[j]) { d[j]=G[u][j]; } } } return ans; } int main() { scanf("%d %d",&n,&m); memset(G,0,sizeof(G)); for(int i=1;i<=m;i++) { int temp1,temp2,temp3; scanf("%d %d %d",&temp1,&temp2,&temp3); G[temp1][temp2]=temp3; G[temp2][temp1]=temp3; } int ans=prim(); printf("%d",ans); return 0; }
- kruskal是把边存起来排序struct edge
- 排序以后从小到大，到成功加入n-1条边为止，但是这个需要并查集，不能简单用true和false。因为两个同时不在已访问集合的也是可以的
- 里面其实带上了union，没写函数而已哦。
- 或者每次选中最短的且两个点不在同一个集合里面的（一个是已访问一个是未访问）（实际上这个原理的本质是prim。。。尽管看起来是边，但是实际上是找到了dmin）（而且因为边比点多，这个VE还不如V^2）
- 一共要选n-1条边，走n-1轮（每次选中一条边加进来）[0,n-2]
- （bellman-ford也是n-1轮，因为n个点是n-1条边，每次松弛一层，n-1轮全部到位）
#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; const int INF=100000; const int maxn=10000; bool visit[maxn]={false}; int n,m; struct edge{ int u,v; int cost; }E[maxn]; bool cmp(edge a,edge b) { return a.cost<b.cost; } bool pd(edge a) { if(visit[a.u]==false && visit[a.v]==true) return true; if(visit[a.u]==true && visit[a.v]==false) return true; return false; } int kruskal() { int ans=0; sort(E,E+m,cmp); visit[0]=true; for(int i=0;i<n-1;i++) { int mincost=INF; edge temp; for(int j=0;j<=m-1;j++) { if(pd(E[j]) && E[j].cost<mincost) { temp=E[j]; mincost=temp.cost; } } visit[temp.u]=true; visit[temp.v]=true; ans+=temp.cost; } return ans; } int main() { scanf("%d %d",&n,&m); for(int i=0;i<m;i++) { scanf("%d%d%d",&E[i].u,&E[i].v,&E[i].cost); } int ans=kruskal(); printf("%d",ans); return 0; } kruskal
#include<stdio.h> #include<string.h> #include<algorithm> using namespace std; const int INF=100000; const int maxn=10000; int father[maxn]; int n,m; struct edge{ int u,v; int cost; }E[maxn]; bool cmp(edge a,edge b) { return a.cost<b.cost; } int findfather(int x) { int a=x; while(x!=father[x]) { x=father[x]; } int z=a; while(a!=father[a]) { z=a; a=father[a]; father[z]=x; } return x; } int samefather(int a,int b) { if(findfather(a)==findfather(b)) return true; return false; } int kruskal() { sort(E,E+m,cmp); int sumroute=0; int ans=0; for(int i=0;i<=n-1;i++) father[i]=i; for(int i=0;i<=m-1;i++) { if(sumroute==n-1) break; if(samefather(E[i].u,E[i].v)==false) { int fu=findfather(E[i].u); int fv=findfather(E[i].v); father[fu]=fv; sumroute++; ans+=E[i].cost; } } return ans; } int main() { scanf("%d %d",&n,&m); for(int i=0;i<m;i++) { scanf("%d%d%d",&E[i].u,&E[i].v,&E[i].cost); } int ans=kruskal(); printf("%d",ans); return 0; }