MST

poj 2031 题意：三维空间中n个球要相连。。。通路的代价是距离。。。如果球相交（切）或者包含那么不用建通路就能联系。。。问联系所有球的最小代价。。。 思路：裸的最小生成树。。。。先预处理球和球表面的距离。。。距离是负数的处理成0.。。然后mst搞之。。。不算CE的话是1A….

poj1789题目链接 题意：其实题目不难理解。。。直接按照定义去搞就行了。。。 思路：由于距离在分母上。。所以要quality最大。。。就是要分母最小。。。 然后由于题目中说每一种类型的type只能由其他一种派生出来。。。我们可以把这个派生关系看做一条边。。。把每种类型看成点。。

Poj2349题目链接 题意：给出n个点坐标。。。然后可以建s个卫星基站。。。有卫星基站的地方之间可以互相免费通信。。现在要建一些无线电通讯线路（不同于卫星基站，是另一种通信方式），两个点之间线路的代价是他们的距离。。。问最小距离是多少。。。使得任意两个点之间都可以直接或者间接联系。。。

poj1751题目链接 题意：一开始有一些边，然后添加一些边，使得代价之和最小。 思路：先把给定的边merge掉。。然后计算其余可以添加的边。。。接下来就是最小生成树。。。 然而因为多开了一个750*750的数组空间被卡了常。。。毫无人性。。。。

poj1679 题意：问最小生成树是否唯一。。 思路：求一下次小生成树。。。如果无解，或者次小生成树的权值之和和最小生成树的权值之和不同，那么唯一，否则不唯一。1A 代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2016年07月12日 星期二 16时16分52秒 4File Name :code/poj/1679.cpp 5************************************************ */ 6#include <cstdio> 7#include <cstring> 8#include <iostream> 9#include <algorithm> 10#include <vector> 11#include <queue> 12#include <set> 13#include <map> 14#include <string> 15#include <cmath> 16#include <cstdlib> 17#include <ctime> 18#define fst first 19#define sec second 20#define lson l,m,rt<<1 21#define rson m+1,r,rt<<1|1 22#define ms(a,x) memset(a,x,sizeof(a)) 23typedef long long LL; 24#define pi pair < int ,int > 25#define MP make_pair 26using namespace std; 27const double eps = 1E-8; 28const int dx4[4]={1,0,0,-1}; 29const int dy4[4]={0,-1,1,0}; 30const int inf = 0x3f3f3f3f; 31const int N=105; 32int n,m; 33int ans; 34int f[N]; 35struct Edge 36{ 37 int u,v,w; 38 int in; 39 void input() 40 { 41 scanf("%d%d%d",&u,&v,&w); 42 } 43 bool operator < (Edge b)const 44 { 45 return w<b.w; 46 } 47}edge[N*N]; 48void init() 49{ 50 for ( int i = 1 ; i <= n ; i++) f[i] = i; 51} 52int root ( int x) 53{ 54 if (x!=f[x]) f[x] = root(f[x]); 55 return f[x]; 56} 57void merge( int x,int y) 58{ 59 int rx = root(x); 60 int ry = root(y); 61 if (rx==ry) return ; 62 f[rx] = ry; 63} 64void kruskal( int k) 65{ 66 for ( int i = 1 ; i <= n; i++) f[i] = i; 67 int cnt = 0 ; 68 int cur = 0 ; 69 for ( int i = 1; i <= m ; i++) 70 { 71 int u = edge[i].u; 72 int v = edge[i].v; 73 int w = edge[i].w; 74 if (i==k) continue; 75 if (root(u)==root(v)) continue; 76 merge(u,v); 77 cnt++; 78 cur+=w; 79 if (cnt>=n-1) break; 80 } 81 // cout<<"cnt:"<<cnt<<endl; 82 if (cnt<n-1) return ; 83 ans = min(ans,cur); 84} 85int main() 86{ 87 #ifndef ONLINE_JUDGE 88 freopen("code/in.txt","r",stdin); 89 #endif 90 int T; 91 scanf("%d",&T); 92 while (T--) 93 { 94 scanf("%d%d",&n,&m); 95 init(); 96 for ( int i = 1; i <= m ; i++) edge[i].input(); 97 sort(edge+1,edge+m+1); 98 int cnt = 0 ; 99 int mst = 0 ; 100 for ( int i = 1 ; i <= m ; i++) 101 { 102 int u = edge[i].u; 103 int v = edge[i].v; 104 int w = edge[i].w; 105 if (root(u)==root(v)) continue; 106 edge[i].in = 1; 107 merge(u,v); 108 cnt++; 109 mst+=w; 110 } 111 ans = inf; 112 for ( int i = 1 ; i <= m ; i++) 113 { 114 if (edge[i].in==0) continue; 115 //cout<<"i:"<<i<<endl; 116 kruskal(i); 117 } 118 // cout<<"mst:"<<mst<<endl; 119 // cout<<"ans:"<<ans<<endl; 120 if (ans==inf) 121 { 122 printf("%d\n",mst); 123 }else 124 { 125 if (ans==mst) puts("Not Unique!"); 126 else printf("%d\n",mst); 127 } 128 } 129 #ifndef ONLINE_JUDGE 130 fclose(stdin); 131 #endif 132 return 0; 133}

URAL1416 题意：次小生成树模板题 思路：用Kruskal求最小生成树，标记用过的边。求次小生成树时，依次枚举用过的边，将其去除后再求最小生成树，得出所有情况下的最小的生成树就是次小的生成树。复杂度o(m2)。。。貌似有其他优化。。。