hdu 1879 继续畅通工程

最小生成树入门题，和纯粹的裸题有些区别，题目中有些道路已经存在，不需要建造，答案是求最后建造的总费用，不要把已经有的道路的权值算进去

//kruskal算法已有的边权植赋为0
//用SORT排序，用并查集判断是否成环

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define INF 1236343242
#define MAX 110
bool vis[MAX][MAX];
int p[MAX];
int ans[MAX*MAX];

struct edge
{
    int b,e,w;
}a[MAX*MAX];
int n;

int cmp(struct edge p , struct edge q)
{
    return p.w<q.w;
}

int find(int x)
{
    return p[x]==x ? x : p[x]=find(p[x]);
}
void kruskal()
{
    int x,y,i,j,k,count;
    int sum;
    for(i=1; i<=n; i++)
        p[i]=i;

    for(sum=0,i=1; i<=n; i++)
    {
        x=find(a[i].b);
        y=find(a[i].e);
        if(x!=y)
        {
            p[x]=y;
            sum+=a[i].w;
        }
    }
    printf("%d\n",sum);
    return ;
}
void init()
{
    int i,j,t;
    for(i=1; i<=n; i++)
    {
        scanf("%d%d%d%d",&a[i].b,&a[i].e,&a[i].w,&t);
        if(t)
            a[i].w=0;   //权值改为0
    }
}
int main()
{
    int i,j,t;
    while(scanf("%d",&n)!=EOF && n)
    {
        n=n*(n-1)/2;
        init();
        sort(a+1 , a+n+1 , cmp);
        kruskal();
    }
    return 0;
}

//Prim算法实现

#include <stdio.h>
#include <string.h>
#define MAX 110
#define INF 1232145125
bool vis[MAX][MAX];
int G[MAX][MAX];
int adj[MAX];
int lowcoat[MAX];
int n;

void init()
{
    int i,j,a,b,c,d;
    memset(vis , 0 ,sizeof(vis));
    for(i=0; i<=n; i++)
        for(j=0; j<=n; j++)
            G[i][j]=INF;
    for(i=0; i<=n; i++)
        G[i][i]=0;

    for(i=1; i<=n*(n-1)/2; i++)
    {
        scanf("%d%d%d%d",&a,&b,&c,&d);
        G[a][b]=G[b][a]=c;
        if(d)
        {
            vis[a][b]=vis[b][a]=1;
            G[a][b]=G[b][a]=-1;  //已经有的道路我们假设它的权值为-1
        }
//        printf("G[%d][%d]=G[%d][%d]=%d\n",a,b,b,a,G[a][b],G[b][a]);
    }
}

void prim()
{
    int v,i,j,k,min,ans;


    for(i=1; i<=n; i++)
    {
        adj[i]=1;
        lowcoat[i]=G[1][i];
    }
    lowcoat[1]=0;

    for(v=1; v<n; v++)
    {
        min=INF; k=1;
        for(i=1; i<=n; i++)
            if(lowcoat[i] && lowcoat[i]<min)
            {
                min=lowcoat[i];
                k=i;
            }
        lowcoat[k]=0;
//        printf("min=%d\n",min);
//        printf("k=%d\n",k);

        for(i=1; i<=n; i++)
            if(lowcoat[i] && G[k][i]<lowcoat[i])
            {
                lowcoat[i]=G[k][i];
                adj[i]=k;
            }
    }

//    printf("lowcoat:  "); 
//      for(i=1; i<=n; i++) printf("%d ",lowcoat[i]); printf("\n");
//    printf("adj:  "); 
//      for(i=1; i<=n; i++) printf("%d ",adj[i]);     printf("\n");

    for(ans=0,v=2; v<=n; v++)
    {
        i=adj[v];
        if(G[i][v]!=-1)  //如果这条路本身存在则不要算它的费用，不存在的才要算
        ans+=G[i][v];
    }
    printf("%d\n",ans);
}
int main()
{
    while(scanf("%d",&n)!=EOF && n)
    {
        init();
        prim();
    }
    return 0;
}