本文共 1228 字，大约阅读时间需要 4 分钟。

题意：

n个点m条无向边的连通图，要求你给尽可能小的边的权值加1，使得图的最小生成树唯一。

题解：

1.造成多种最小生成的冲突边是权值相同且连通块相同的边。

2.kruskal的思路做：

(1)把边按权值排序。

(2)找出边权值相同的区间[i,j)，遍历[i,j)记录连接两个连通块的边的数目cnt，然后再遍历一遍[i,j)，若边连接两个连通块，那么用这条边连接两个连通块，并且cnt --，与该边权值相同且连接的两个连通块相同的冲突边就被算进去了。

(3)将cnt累加起来即为答案。

#include
   
    #define N 200005using namespace std ;struct Edge{	int u , v , w ;} edge[N] ;int n , m ;bool vis[N] ;int pre[N] ;int find(int x){	if(x == pre[x])	   return pre[x] ;	pre[x] = find(pre[x]) ;	return pre[x] ;}bool cmp(Edge a , Edge b){	return a.w < b.w ;}int main(){	int i , j , k ;	int u , v , w ;	Edge a ;	int cnt ;	int ans = 0 ;	scanf("%d%d" , &n , &m) ;	for(i = 0 ; i < m ; i ++)	{       scanf("%d%d%d" , &u , &v , &w) ;       a.u = u ;       a.v = v ;       a.w = w ;       edge[i] = a ;	}	sort(edge , edge + m , cmp) ;	for(i = 1 ; i <= n ; i ++)	   pre[i] = i ;	for(i = 0 ; i < m ; i ++)	{		j = i ;		while(edge[j].w == edge[i].w && j < m)		      j ++ ;	    cnt = 0 ;	    for(k = i ; k < j ; k ++)		    if(find(edge[k].u) != find(edge[k].v))			   cnt ++ ; 		for(k = i ; k < j ; k ++)		    if(find(edge[k].u) != find(edge[k].v))	        {	        	pre[find(edge[k].u)] = find(edge[k].v) ;	        	cnt -- ;			}	    ans += cnt ; 		i = j - 1 ;   	}	printf("%d\n" , ans) ;}