prim 알고리즘(프 림 알고리즘)

Prim 알고리즘:http://blog.chinaunix.net/uid-25324849-id-2182922.html

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=105;
const int INF=1<<29;
int nearvex[N],lowcost[N];
int edge[N][N];
int n,m;
void init()
{
    fill(nearvex,nearvex+N,1);
    fill(lowcost,lowcost+N,INF);
    lowcost[1]=0;
    for(int i=1;i<=n;i++)
    {
        if(edge[1][i])
        {
            lowcost[i]=edge[1][i];
        }
    }
    nearvex[1]=-1;
}
void Prim()
{
    int v;
    int lg=INF;
    for(int i=1;i<=n;i++)
    {
        if(nearvex[i]==-1) continue;
        if(lg>=edge[nearvex[i]][i])
        {
            v=i;
            lg=edge[nearvex[i]][i];
        }
    }
    cout<<nearvex[v]<<" "<<v<<" "<<edge[nearvex[v]][v]<<endl;
    nearvex[v]=-1;
    for(int i=1;i<=n;i++)
    {
        lowcost[i]=min(lowcost[i],edge[v][i]);
    }
    for(int i=1;i<=n;i++)
    {
        if(nearvex[i]==-1) continue;
        if(edge[v][i]<edge[nearvex[i]][i])
            nearvex[i]=v;
    }
}
int main()
{
    //freopen("in.txt","r",stdin);
    scanf("%d%d",&n,&m);
    int u,v;
    for(int i=0;i<N;i++)
        fill(edge[i],edge[i]+N,INF);
    for(int i=0;i<m;i++)
    {
        cin>>u>>v;
        scanf("%d",&edge[u][v]);
        edge[v][u]=edge[u][v];
    }
    init();
    for(int i=1;i<=n-1;i++)
        Prim();
    return 0;
}

zoj 1586(간단 한 문제)http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=586 lowcost 와 nearvex 배열 을 lowcost 배열 로 합 칩 니 다.만약 저가【i】=-1;이 정점 은 구조의 최소 생 성 트 리(최소 생 성 트 리 의 정점 집합 은 T 로 설정)에 있 음 을 나타 낸다.그렇지 않 으 면 lowcost 의 값 은 정점 i 에서 T 의 각 정점 값 의 최소 변 값 을 나타 낸다.사고:각 변 의 가중치=이 변 양쪽 어댑터 의 가격+네트워크 의 가격.그리고 템 플 릿 문제 로 전환 합 니 다.

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=1005;
const int INF=1<<29;
int lowcost[N];
int edge[N][N];
int n;
int cost[N];
int weight; //  
void init()
{
    weight=0;
    fill(lowcost,lowcost+N,INF);
    lowcost[1]=-1;
}
void prim(int num)
{
    for(int i=1;i<=n;i++)
    {
        if(lowcost[i]==-1) continue;
        lowcost[i]=edge[num][i]+cost[num]+cost[i];
    }
    for(int i=1;i<n;i++)
    {
        int lg=INF;
        int v=-1;
        for(int j=1;j<=n;j++)
        {
            if(lowcost[j]==-1) continue;
            if(lg>=lowcost[j])
            {
                v=j;
                lg=lowcost[j];
            }
        }
        if(v!=-1)
        {
            weight+=lg;
            //cout<<weight<<endl;
            lowcost[v]=-1;
            for(int j=1;j<=n;j++)
            {
                if(lowcost[j]==-1) continue;
                lowcost[j]=min(edge[v][j]+cost[v]+cost[j],lowcost[j]);
            }
        }
    }
}
int main()
{
    //freopen("in.txt","r",stdin);
    int Cas;
    cin>>Cas;
    while(Cas--)
    {
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            cin>>cost[i];
        }
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                cin>>edge[i][j];
            }
        }
        init();
        prim(1);
        cout<<weight<<endl;
    }
    return 0;
}

zoj 2158(물 문제):http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1158 모든 트럭 유형 간 의 거 리 를 계산 하여 엣 지 배열 에 저장 한 후 템 플 릿 문제 가 되 었 다.

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=7;
const int maxn=2005;
const int INF=1<<29;
char ch[maxn][N];
int lowcost[maxn];
int edge[maxn][maxn];
int n;
int weight;
void init()
{
    weight=0;
    memset(edge,0,sizeof(edge));
}
int compare(char s[],char c[])
{
    int ans=0;
    for(int i=0;i<7;i++)
    {
        if(s[i]!=c[i])
            ans++;
    }
    return ans;
}
void prim()
{
    for(int i=1;i<=n;i++)
    {
        lowcost[i]=edge[1][i];
    }
    lowcost[1]=-1;
    for(int j=1;j<n;j++)
    {
        int v=-1;
        int lg=INF;
        for(int i=1;i<=n;i++)
        {
            if(lowcost[i]==-1) continue;
            if(lg>lowcost[i])
            {
                lg=lowcost[i];
                v=i;
            }
        }
        weight+=lg;
        if(v!=-1)
        {
            lowcost[v]=-1;
            for(int i=1;i<=n;i++)
            {
                if(lowcost[i]==-1) continue;
                if(edge[v][i]<lowcost[i])
                {
                    lowcost[i]=edge[v][i];
                }
            }
        }
    }
}
int main()
{
    //freopen("in.txt","r",stdin);
    while(cin>>n)
    {
        if(!n) break;
        for(int i=1;i<=n;i++)
        {
            getchar();
            cin>>ch[i];
        }
        init();
        for(int i=1;i<n;i++)
        {
            for(int j=i+1;j<=n;j++)
            {
                int d=compare(ch[i],ch[j]);
                //cout<<d<<endl;
                edge[i][j]=edge[j][i]=d;
            }
        }
        prim();
        printf("The highest possible quality is 1/%d.
",weight);
    }
    return 0;
}