Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

用Prim算法时间复杂度n^2,就可以做出来不需要枚举去掉各条边

Posted by qq2308091457 at 2017-07-12 09:29:19 on Problem 1679
大家可以看一下,用Prim算法扩充的时候,只要有一次扩充的点,有多种选择连接已经扩充的点,那么最小生成树不唯一,比如:
3 3
1 2 1
1 3 2
2 3 2
首先1 2点肯定先连接,这时候,连接第三个点的时候,发现他有两种选择连接已经扩充的点,故MST不唯一
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int dis[101];
int next[101];
int point[101];
int n,m;
typedef struct Node
{
    int y,l,p;
}Node;
Node maps[10001];
void push(int x,int y,int l,int s)
{
    maps[s].y=y;
    maps[s].l=l;
    maps[s].p=point[x];
    point[x]=s;
}
void updata(int x)
{
    int p;
    next[x]=0;
    for(p=point[x];p!=0;p=maps[p].p)
    {
        int y=maps[p].y;
        int l=maps[p].l;
        if(!next[y])
            continue;
        if(dis[y]>l)
        {
            dis[y]=l;
            next[y]=x;
        }
    }
}
int Prim()
{
    updata(1);
    int i,j;
    int ans=0;
    for(i=1;i<n;i++)
    {
        int p=0;
        for(j=1;j<=n;j++)
        {
            if(!next[j])
                continue;
            if(dis[j]<dis[p])
            {
                p=j;
            }
        }
        for(j=point[p];j;j=maps[j].p)
        {
            int y=maps[j].y;
            int l=maps[j].l;
            if(next[y])
                continue;
            if(l==dis[p]&&next[p]!=y)
                return -1;
        }
        ans+=dis[p];
        updata(p);
    }
   // printf("%d\n",ans);
    return ans;
}
int main()
{
    int T;
    scanf("%d",&T);
    int i;
    while(T--)
    {
        scanf("%d%d",&n,&m);
        memset(dis,9999999,sizeof(dis));
        memset(next,1,sizeof(next));
        memset(point,0,sizeof(point));
        for(i=1;i<=m;i++)
        {
            int x,y,c;
            scanf("%d%d%d",&x,&y,&c);
            push(x,y,c,i*2-1);
            push(y,x,c,i*2);
        }
        int ans=Prim();
        if(ans!=-1)
            printf("%d\n",ans);
        else
            printf("Not Unique!\n");
    }
    return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator