★ 夢想生活 ｜成長記事本 ★

解題：Partial 'Minimum' Spanning Tree 將固定邊連接，再做Kruskal Code：   1  #include<stdio.h>   2  #include<stdlib.h>   3  #include<iostream>   4  #include<algorithm>   5  #include<vector>   6  #include<queue>   7  #include<math.h>   8  #include<utility>   9  #include<string.h>  10  #define MAXN 800  11  using namespace std ;  12  typedef pair < double , double > ii ;  13  int g [ MAXN ]={ 0 };  14  vector < ii > ans ;  15  int initial ()  16  {  17      for ( int i = 0 ; i < MAXN ; i ++) g [ i ]= i ;  18  }  19  int Find ( int a )  20  {  21      if ( g [ a ]!= a )  22      {  23   ...

解題： Kruskal 變化題：窮舉所有最小邊做Kruskal (從原來邊1~m,2~m,3~m直到無法形成MST(總編數不夠) Code： #include<stdio.h> #include<stdlib.h> #include<iostream> #include<algorithm> #include<queue> #define MAXN 10005 using namespace std ; typedef pair < int , int > ii ; priority_queue < ii , vector < ii >, greater < ii > > edges [ 5000 ]; int n , m ; int g [ MAXN ]; int initial () {     for ( int i = 1 ; i <= n ; i ++)     {         g [ i ]= i ;     } } int Find ( int a ) {     if ( a != g [ a ])     {         g [ a ]= Find ( g [ a ]);     }     return g [ a ]; } void Union ( int a , int b ) {     if ( Find ( a )!= Find ( b ))     {         g [ g [ a ]]= g [ b ]; ...