看卿学姐视频学到的题目

 

kruskal算法实现最小生成树

#include
     
      using namespace std;const int maxn = 105;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=1; 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 = 0;    sort(E+1,E+1+m,cmp);    for(int i=1;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=1;i <= m;i++)        {            scanf("%d %d %lld",&E[i].from,&E[i].to,&E[i].cost);        }        ll res = kruskal();        for(int i=1; i <=n;i++)            if(!check(i,1))                res = -1;        if(res == -1)            puts("?");        else            printf("%lld\n",res);    }    return 0;}
     

 

 prim 算法实现  （坑点好多  还要多写写 熟练一些

#include 
      
       using namespace std;typedef long long ll;const int maxn = 105;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
       
         que;vector 
        
          G[maxn];bool vis[maxn];void init(){    memset(vis,0,sizeof(vis));    while (que.size())        que.pop();    for(int i=0;i <= n;i++)        G[i].clear();}ll prim(){    vis[1] = 1;//要把1先加进去    ll cnt = 0;    for(int i=0; i < G[1].size();i++)//从第一个顶点取出最短的边        que.push( G[1][i] );    while(que.size())    {        edge e = que.top();        que.pop();        if(vis[e.to])            continue;        vis[e.to] = 1;        cnt += e.cost;        for(int i=0;i< G[e.to].size();i++)            que.push(G[e.to][i]);        //cout << cnt<
         
          <= 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=1; i <= n;i++)            if( vis[i] == 0)                res = -1;      //  for(int i=1; i <= n;i++)           // printf("%d",vis[i]);        if(res == -1)            puts("?");        else            printf("%lld\n",res);    }    return 0;}