看卿学姐视频学到的题目
kruskal算法实现最小生成树
#include<bits/stdc++.h>
using namespace std;
const int maxn = ;
typedef long long ll;
int n,m;
struct edge{
int from ,to;
ll cost;
}E[maxn*maxn];
bool cmp(edge a,edge b)
{
return a.cost < b.cost;
}
int fa[maxn];
void init()
{
for(int i=; i <= maxn; i++)
fa[i] = i;
}
int fi(int x)
{
return fa[x] == x? x :fa[x] = fi(fa[x]);
} void Union(int x,int y)
{
int f1=fi(x);
int f2=fi(y);
if(f1 != f2)
fa[f1] = f2;
} bool check(int x,int y)
{
return fi(x) == fi(y);
} ll kruskal()
{
ll cnt = ;
sort(E+,E++m,cmp);
for(int i=;i <= m;i++)
{
if(check(E[i].from,E[i].to)) continue;
Union(E[i].from,E[i].to);
cnt += E[i].cost;
}
return cnt;
} int main ()
{
while (~scanf("%d %d",&m,&n) && m){
init();
for(int i=;i <= m;i++)
{
scanf("%d %d %lld",&E[i].from,&E[i].to,&E[i].cost);
}
ll res = kruskal();
for(int i=; i <=n;i++)
if(!check(i,))
res = -;
if(res == -)
puts("?");
else
printf("%lld\n",res);
}
return ;
}
prim 算法实现 （坑点好多 还要多写写 熟练一些
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = ;
int n,m;
struct edge{
int to;
ll cost;
edge(){}
edge(int tt,ll cc):to(tt),cost(cc){}
bool operator < (const edge &l)const{
return l.cost < cost;
}
}; priority_queue<edge> que;
vector <edge> G[maxn];
bool vis[maxn]; void init()
{
memset(vis,,sizeof(vis));
while (que.size())
que.pop();
for(int i=;i <= n;i++)
G[i].clear();
} ll prim()
{
vis[] = ;//要把1先加进去
ll cnt = ;
for(int i=; i < G[].size();i++)//从第一个顶点取出最短的边
que.push( G[][i] );
while(que.size())
{
edge e = que.top();
que.pop();
if(vis[e.to])
continue;
vis[e.to] = ;
cnt += e.cost;
for(int i=;i< G[e.to].size();i++)
que.push(G[e.to][i]);
//cout << cnt<<endl;
}
return cnt;
} int main ()
{
while (~scanf("%d %d",&m,&n) && m){
init();
for(int i=;i <= m;i++)
{
int u,v;
ll cost;
scanf("%d %d %lld",&u,&v,&cost);
G[u].push_back(edge(v,cost));
G[v].push_back(edge(u,cost));
} ll res = prim();
for(int i=; i <= n;i++)
if( vis[i] == )
res = -;
// for(int i=1; i <= n;i++)
// printf("%d",vis[i]);
if(res == -)
puts("?");
else
printf("%lld\n",res);
}
return ;
}