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;
}