次小生成树模板（poj1679）

时间：2022-11-23 22:32:35

prim

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <algorithm>

#include <cstring>

#include <stack>

#include <cctype>

#include <queue>

#include <string>

#include <vector>

#include <set>

#include <map>

#include <climits>

#define lson root<<1,l,mid

#define rson root<<1|1,mid+1,r

#define fi first

#define se second

#define ping(x,y) ((x-y)*(x-y))

#define mst(x,y) memset(x,y,sizeof(x))

#define mcp(x,y) memcpy(x,y,sizeof(y))

#define Min(x,y) (x<y?x:y)

#define Max(x,y) (x>y?x:y)

using namespace std;

#define gamma 0.5772156649015328606065120 //欧拉常数

#define MOD 100000007

#define inf 0x3f3f3f3f

#define N 205

#define maxn 10001000

typedef long long LL;

typedef pair<int,int> PII;

int vis[],d[],pic[][],used[][],path[][];

int ans,n,pre[];

int prim()

{

    for(int i=; i<=n; ++i) pre[i]=;

    mst(vis,);

    vis[]=;

    int res=;

    int i,j;

    for(i=; i<=n; ++i) d[i]=pic[][i];

    for(i=; i<n; ++i)

    {

        int m=inf,u;

        for(j=; j<=n; ++j)

            if(!vis[j]&&d[j]<m)

                m=d[u=j];

        res+=m;

        vis[u]=;

        used[u][pre[u]]=used[pre[u]][u]=;

        for(j=; j<=n; ++j)

            if(!vis[j]&&pic[u][j]<d[j])

            {d[j]=pic[u][j];pre[j]=u;}

            else if(vis[j]&&j!=u)

            path[j][u]=path[u][j]=Max(m,path[j][pre[u]]);

    }

    int temp=inf;

    for(int i=; i<=n; ++i)

        for(int j=i+; j<=n; ++j)

        {

            if(!used[i][j])

                temp=Min(temp,res+pic[i][j]-path[i][j]);

        }

    if(temp==res) return ;

    ans=res;

    return ;

}

int main()

{

    //freopen("in.txt","r",stdin);

    int i,j,x,y,v,group,m;

    scanf("%d",&group);

    while(group--)

    {

        scanf("%d%d",&n,&m);

        mst(path,);

        mst(pic,inf);

        mst(used,);

        for(i=; i<m; ++i)

        {

            scanf("%d%d%d",&x,&y,&v);

            pic[x][y]=pic[y][x]=v;

        }

        ans=;

        if(prim()) printf("%d\n",ans);

        else printf("Not Unique!\n");

    }

    return ;

}

kruskal:

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <stack>
#include <cctype>
#include <queue>
#include <string>
#include <vector>
#include <set>
#include <map>
#include <climits>
#define lson root<<1,l,mid
#define rson root<<1|1,mid+1,r
#define fi first
#define se second
#define ping(x,y) ((x-y)*(x-y))
#define mst(x,y) memset(x,y,sizeof(x))
#define mcp(x,y) memcpy(x,y,sizeof(y))
#define Min(x,y) (x<y?x:y)
#define Max(x,y) (x>y?x:y)
using namespace std;
#define gamma 0.5772156649015328606065120
#define MOD 100000007
#define inf 0x3f3f3f3f
#define N 100005
#define maxn 1000050
typedef long long LL;
typedef pair<int,int> PII;

int n,m,cnt,vis[6000],fp[105]; ///vis[]是标记第一次求mst时用过哪些边(后面枚举删边时用到)
struct Node{
    int x,y,v;
    bool operator<(const Node&a)const{
        return v<a.v;
    }
    Node(){}
    Node(int a,int b,int c):x(a),y(b),v(c){}
}node[6000];
int findp(int x){return fp[x]==x?x:fp[x]=findp(fp[x]);}

int kus(int xx){      ///xx表示删除哪条边
    int res=0;
    for(int i=0;i<=n;++i)fp[i]=i;
    int num=1;
    for(int i=0;i<cnt;++i){
        if(i==xx)continue;
        int x=findp(node[i].x);
        int y=findp(node[i].y);
        if(x==y)continue;
        res+=node[i].v;
        fp[x]=y;
        if(xx==inf)vis[i]=1;
        if(++num==n)break;
    }
    if(num<n)return inf;
    else return res;
}

int main(){
    int x,y,v,i,j,group,Case=0,m;
    //freopen("in.txt","r",stdin);
    scanf("%d",&group);
    while(group--){
        mst(vis,0);
        scanf("%d%d",&n,&m);
        cnt=0;
        while(m--){
            scanf("%d%d%d",&x,&y,&v);
            node[cnt++]=Node(x,y,v);
        }
        sort(node,node+cnt);
        int res=kus(inf),ans=inf;
        for(i=0;i<cnt;++i){
            if(vis[i])
                ans=Min(ans,kus(i));
        }
        if(ans==res)printf("Not Unique!\n");
        else printf("%d\n",res);
    }
    return 0;
}

相关文章