hdu 1879 有的边已存在（MST）

Sample Input
3
1 2 1 0 //u v w 是否已建
1 3 2 0
2 3 4 0
3
1 2 1 0
1 3 2 0
2 3 4 1
3
1 2 1 0
1 3 2 1
2 3 4 1
0

Sample Output
3
1
0

将已经建好的路的权值设为0

 1 # include <iostream>
 2 # include <cstdio>
 3 # include <cstring>
 4 # include <algorithm>
 5 # include <cmath>
 6 # define LL long long
 7 using namespace std ;
 8 
 9 int n ;
10 const int MAXN=110;//最大点数
11 const int MAXM=10000;//最大边数
12 int F[MAXN];//并查集使用
13 struct Edge
14 {
15     int u,v,w;
16 }edge[MAXM];//存储边的信息，包括起点/终点/权值
17 
18 int tol;//边数，加边前赋值为0
19 void addedge(int u,int v,int w)
20 {
21 
22     edge[tol].u=u;
23     edge[tol].v=v;
24     edge[tol++].w=w;
25 }
26 bool cmp(Edge a,Edge b)
27 {//排序函数，讲边按照权值从小到大排序
28     return a.w<b.w;
29 }
30 int find(int x)
31 {
32     if(F[x]==-1)return x;
33     else return F[x]=find(F[x]);
34 }
35 int Kruskal()//传入点数，返回最小生成树的权值，如果不连通返回-1
36 {
37     memset(F,-1,sizeof(F));
38     sort(edge,edge+tol,cmp);
39     int cnt=0;//计算加入的边数
40     int ans=0;
41     for(int i=0;i<tol;i++)
42     {
43         int u=edge[i].u;
44         int v=edge[i].v;
45         int w=edge[i].w;
46         int t1=find(u);
47         int t2=find(v);
48         if(t1!=t2)
49         {
50             ans+=w;
51             F[t1]=t2;
52             cnt++;
53         }
54         if(cnt==n-1)break;
55     }
56     if(cnt<n-1)return -1;//不连通
57     else return ans;
58 }
59 
60 int main()
61 {
62 
63     //freopen("in.txt","r",stdin) ;
64     while(scanf("%d" , &n) != EOF)
65     {
66         if (n == 0)
67             break ;
68         int u , v , w , ok ;
69         int i ;
70         tol = 0 ;
71         for (i = 1 ; i <= n*(n-1)/2 ; i++)
72         {
73             scanf("%d %d %d %d" , &u , &v , &w , &ok) ;
74             if (ok == 1)
75                 addedge(u,v,0) ;
76             else
77                 addedge(u,v,w) ;
78         }
79         printf("%d
" , Kruskal()) ;
80 
81 
82     }
83     return 0 ;
84 }

View Code

hdu 1879 有的边已存在 （MST）

hdu 1879 有的边已存在（MST）