首先是最小樹形圖的介紹。
看這個博客。最小樹形圖
上面介紹的很詳細了,我就講一下這道題的題意。
首先給出一些二維點坐標,這些坐標之間構成一些有向圖,根據題意,假設兩個點a(x1 ,y1) ,b(x2 ,y2) .當y1 <= y2時,他們之間可以連一條有向邊,即a -> b。
就是每個點只能連y坐標大於他的點,然後就構成了一張有向圖。
最後求出最少的距離可以使得所有的點都連起來。
剛開始以為直接求出兩兩之間的距離,然後用kruskal求一遍MST就可以了。但是仔細想了一下,這裡有向邊的限制就使得一些連邊的情況是不可行的。
這道題的正解是最小樹形圖,而且是最裸的。
因為這道題他的根是不確定的,那麼我們可以用一個超級源點,作為他的根,將他和所有的點都連起來,邊是inf。
#include <set> #include <map> #include <stack> #include <cmath> #include <queue> #include <cstdio> #include <string> #include <vector> #include <iomanip> #include <cstring> #include <iostream> #include <algorithm> #define Max 2505 #define FI first #define SE second #define ll long long #define PI acos(-1.0) #define inf 0x3fffffff #define LL(x) ( x << 1 ) #define bug puts("here") #define PII pair<int,int> #define RR(x) ( x << 1 | 1 ) #define mp(a,b) make_pair(a,b) #define mem(a,b) memset(a,b,sizeof(a)) #define REP(i,s,t) for( int i = ( s ) ; i <= ( t ) ; ++ i ) using namespace std; inline void RD(int &ret) { char c; int flag = 1 ; do { c = getchar(); if(c == '-')flag = -1 ; } while(c < '0' || c > '9') ; ret = c - '0'; while((c=getchar()) >= '0' && c <= '9') ret = ret * 10 + ( c - '0' ); ret *= flag ; } inline void OT(int a) { if(a >= 10)OT(a / 10) ; putchar(a % 10 + '0') ; } inline void RD(double &ret) { char c ; int flag = 1 ; do { c = getchar() ; if(c == '-')flag = -1 ; } while(c < '0' || c > '9') ; ll n1 = c - '0' ; while((c = getchar()) >= '0' && c <= '9') { n1 = n1 * 10 + c - '0' ; } ll n2 = 1 ; while((c = getchar()) >= '0' && c <= '9') { n1 = n1 * 10 + c - '0' ; n2 *= 10 ; } ret = flag * (double)n1 / (double)(n2) ; } /*********************************************/ #define N 1005 struct PP{ double x , y ; }P[N] ; double getdis(int i ,int j){ return sqrt((P[i].x - P[j].x) * (P[i].x - P[j].x) + (P[i].y - P[j].y) * (P[i].y - P[j].y)) ; } struct kdq{ int s , e ; double l ; }ed[N * N] ; int num ; void add(int s ,int e ,double l){ ed[num].s = s ; ed[num].e = e ; ed[num].l = l ; num ++ ; } void init(){ num = 0 ; } int n ; int S ; int pre[N] , id[N] , vis[N] ; double in[N] ; double Directed_MST(int root ,int NV , int NE){ double ret = 0 ; while(1){ for (int i = 0 ; i < NV ; i ++ )in[i] = inf ; //找到每個點的最小入邊 for (int i = 0 ; i < NE ; i ++ ){ int s = ed[i].s ; int e = ed[i].e ; if(ed[i].l < in[e] && s != e){ pre[e] = s ; in[e] = ed[i].l ; } } //最小入邊 // for (int i = 1 ; i < NV ; i ++ ){ // cout << i << " : " << in[i] << endl; // } for (int i = 0 ; i < NV ; i ++ ){//除根節點外所有點都找到一條入邊 if(i == root)continue ; if(in[i] == inf)return -1 ; } //找環 int cntnode = 0 ; mem(vis ,-1) ; mem(id ,-1) ; in[root] = 0 ; for (int i = 0 ; i < NV ; i ++ ){ ret += in[i] ; int v = i ; while(vis[v] != i && id[v] == -1 && v != root){ vis[v] = i ; v = pre[v] ; } if(v != root && id[v] == -1){ for (int u = pre[v] ; u != v ; u = pre[u]){ id[u] = cntnode ; } id[v] = cntnode ++ ; } } if(cntnode == 0)break ;//無環 for (int i = 0 ; i < NV ; i ++ ){ if(id[i] == -1)id[i] = cntnode ++ ; } //縮點 for (int i = 0 ; i < NE ; i ++ ){ int s = ed[i].s ; int e = ed[i].e ; ed[i].s = id[s] ; ed[i].e = id[e] ; if(ed[i].s != ed[i].e){ ed[i].l -= in[e] ; } } NV = cntnode ; root = id[root] ; } return ret ; } int main() { while(cin >> n , n ){ int a , b ; for (int i = 1 ; i <= n ; i ++ ){ scanf("%lf %lf",&P[i].x ,&P[i].y) ; } init() ; double dis_sum = 0 ; for (int i = 1 ; i <= n ;i ++ ){ for (int j = 1 ; j <= n ;j ++ ){ if(i == j)continue ; double dis = getdis(i , j) ; if(P[i].y <= P[j].y){ add(i , j , dis) ; // cout << dis << endl; dis_sum += dis ; } } } S = 0 ; for (int i = 1 ; i <= n ; i ++ ){ add(S , i , inf - 1 ) ; } printf("%.2f\n",Directed_MST(0 , n + 1 , num ) - inf + 1) ; } return 0 ; } #include <set> #include <map> #include <stack> #include <cmath> #include <queue> #include <cstdio> #include <string> #include <vector> #include <iomanip> #include <cstring> #include <iostream> #include <algorithm> #define Max 2505 #define FI first #define SE second #define ll long long #define PI acos(-1.0) #define inf 0x3fffffff #define LL(x) ( x << 1 ) #define bug puts("here") #define PII pair<int,int> #define RR(x) ( x << 1 | 1 ) #define mp(a,b) make_pair(a,b) #define mem(a,b) memset(a,b,sizeof(a)) #define REP(i,s,t) for( int i = ( s ) ; i <= ( t ) ; ++ i ) using namespace std; inline void RD(int &ret) { char c; int flag = 1 ; do { c = getchar(); if(c == '-')flag = -1 ; } while(c < '0' || c > '9') ; ret = c - '0'; while((c=getchar()) >= '0' && c <= '9') ret = ret * 10 + ( c - '0' ); ret *= flag ; } inline void OT(int a) { if(a >= 10)OT(a / 10) ; putchar(a % 10 + '0') ; } inline void RD(double &ret) { char c ; int flag = 1 ; do { c = getchar() ; if(c == '-')flag = -1 ; } while(c < '0' || c > '9') ; ll n1 = c - '0' ; while((c = getchar()) >= '0' && c <= '9') { n1 = n1 * 10 + c - '0' ; } ll n2 = 1 ; while((c = getchar()) >= '0' && c <= '9') { n1 = n1 * 10 + c - '0' ; n2 *= 10 ; } ret = flag * (double)n1 / (double)(n2) ; } /*********************************************/ #define N 1005 struct PP{ double x , y ; }P[N] ; double getdis(int i ,int j){ return sqrt((P[i].x - P[j].x) * (P[i].x - P[j].x) + (P[i].y - P[j].y) * (P[i].y - P[j].y)) ; } struct kdq{ int s , e ; double l ; }ed[N * N] ; int num ; void add(int s ,int e ,double l){ ed[num].s = s ; ed[num].e = e ; ed[num].l = l ; num ++ ; } void init(){ num = 0 ; } int n ; int S ; int pre[N] , id[N] , vis[N] ; double in[N] ; double Directed_MST(int root ,int NV , int NE){ double ret = 0 ; while(1){ for (int i = 0 ; i < NV ; i ++ )in[i] = inf ; //找到每個點的最小入邊 for (int i = 0 ; i < NE ; i ++ ){ int s = ed[i].s ; int e = ed[i].e ; if(ed[i].l < in[e] && s != e){ pre[e] = s ; in[e] = ed[i].l ; } } //最小入邊 // for (int i = 1 ; i < NV ; i ++ ){ // cout << i << " : " << in[i] << endl; // } for (int i = 0 ; i < NV ; i ++ ){//除根節點外所有點都找到一條入邊 if(i == root)continue ; if(in[i] == inf)return -1 ; } //找環 int cntnode = 0 ; mem(vis ,-1) ; mem(id ,-1) ; in[root] = 0 ; for (int i = 0 ; i < NV ; i ++ ){ ret += in[i] ; int v = i ; while(vis[v] != i && id[v] == -1 && v != root){ vis[v] = i ; v = pre[v] ; } if(v != root && id[v] == -1){ for (int u = pre[v] ; u != v ; u = pre[u]){ id[u] = cntnode ; } id[v] = cntnode ++ ; } } if(cntnode == 0)break ;//無環 for (int i = 0 ; i < NV ; i ++ ){ if(id[i] == -1)id[i] = cntnode ++ ; } //縮點 for (int i = 0 ; i < NE ; i ++ ){ int s = ed[i].s ; int e = ed[i].e ; ed[i].s = id[s] ; ed[i].e = id[e] ; if(ed[i].s != ed[i].e){ ed[i].l -= in[e] ; } } NV = cntnode ; root = id[root] ; } return ret ; } int main() { while(cin >> n , n ){ int a , b ; for (int i = 1 ; i <= n ; i ++ ){ scanf("%lf %lf",&P[i].x ,&P[i].y) ; } init() ; double dis_sum = 0 ; for (int i = 1 ; i <= n ;i ++ ){ for (int j = 1 ; j <= n ;j ++ ){ if(i == j)continue ; double dis = getdis(i , j) ; if(P[i].y <= P[j].y){ add(i , j , dis) ; // cout << dis << endl; dis_sum += dis ; } } } S = 0 ; for (int i = 1 ; i <= n ; i ++ ){ add(S , i , inf - 1 ) ; } printf("%.2f\n",Directed_MST(0 , n + 1 , num ) - inf + 1) ; } return 0 ; }