今天刷一下水题练手入门，明天继续。
poj1861 Network（最小生成树）新手入门题。
题意：输出连接方案中最长的单根网线长度（必须使这个值是所有方案中最小的），然后输出方案。
题解：本题没有直接求生成树，但如果连接n个集线器的方案多于n-1条边，那么必存在回路，因此去掉某些边剩下的边和所有顶点构成一个生成树。对于一个图的最小生成树来说，它的最大边满足所有生成树的最大边里最小，正和题意。
吐槽：题目样例是错的。。。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=;
struct edge{
int u,v,w;
}e[];
int f[N],a[N],ai;
int n,m,ma;
int cmp(edge a,edge b){
return a.w<b.w;
}
void init(){
for(int i=;i<=n;++i)
f[i]=i;
}
int fin(int x){
if(x!=f[x])f[x]=fin(f[x]);
return f[x];
}
void Kruskal(){
ma=ai=;
int u,v,i;
init();
for(i=;i<m;++i){
u=e[i].u;
v=e[i].v;
if((u=fin(u))!=(v=fin(v))){
f[u]=v;
a[ai++]=i;
ma=max(e[i].w,ma);
}
if(ai>=n-)break;
}
}
int main(){
int i,u,v,w;
scanf("%d%d",&n,&m);
for(i=;i<m;++i){
scanf("%d%d%d",&u,&v,&w);
e[i]=edge{u,v,w};
}
sort(e,e+m,cmp);
Kruskal();
printf("%d\n%d\n",ma,ai);
for(i=;i<ai;++i)
printf("%d %d\n",e[a[i]].u,e[a[i]].v);
return ;
}
poj1251 Jungle Roads（最小生成树）水题。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=;
struct edge{
int u,v,w;
}e[];
int f[N];
int n,m,ans;
int cmp(edge a,edge b){
return a.w<b.w;
}
void init(){
for(int i=;i<n;++i)
f[i]=i;
}
int fin(int x){
if(x!=f[x])f[x]=fin(f[x]);
return f[x];
}
void Kruskal(){
ans=;
int u,v,i;
init();
for(i=;i<m;++i){
u=e[i].u;
v=e[i].v;
if((u=fin(u))!=(v=fin(v))){
f[u]=v;
ans+=e[i].w;
}
}
}
int main(){
int i,j,w,k;
char u[],v[];
while(scanf("%d",&n),n){
m=;
for(i=;i<n-;++i){
scanf("%s %d",u,&k);
for(j=;j<k;++j){
scanf("%s %d",v,&w);
e[m++]={u[]-'A',v[]-'A',w};
}
}
sort(e,e+m,cmp);
Kruskal();
printf("%d\n",ans);
}
return ;
}
poj1287 Networking（最小生成树）水题。
用prim要注意两个地点之间的线路可能多条，即有重边。我这里练的是Kruskal，题目没给边数，但知道点数最多50，则边数最多50*49/2=1225条，有重边，开大点数组就行，因为数据弱，随便开个1500都过了，醉。。。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int M=;
struct edge{
int u,v,w;
}e[M];
int f[];
int n,m,ans;
int cmp(edge a,edge b){
return a.w<b.w;
}
void init(){
for(int i=;i<=n;++i)
f[i]=i;
}
int fin(int x){
if(x!=f[x])f[x]=fin(f[x]);
return f[x];
}
void Kruskal(){
ans=;
int u,v,i;
init();
for(i=;i<m;++i){
u=e[i].u;
v=e[i].v;
if((u=fin(u))!=(v=fin(v))){
f[u]=v;
ans+=e[i].w;
}
}
}
int main(){
int i,u,v,w;
while(scanf("%d",&n),n){
scanf("%d",&m);
for(i=;i<m;++i){
scanf("%d%d%d",&u,&v,&w);
e[i]={u,v,w};
}
sort(e,e+m,cmp);
Kruskal();
printf("%d\n",ans);
}
return ;
}
poj2031 Building a Space Station（最小生成树）题目看老久，其实挺水…空间站存在一些球形单间，如果单间之间接触，重叠或用走廊连接则连通。给出单间坐标和半径，求要使得所有单间相连通的走廊总长度的最小值。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int M=;
const int N=;
struct edge{
int u,v;
double w;
}e[M];
double a[N],b[N],c[N],r[N];
int f[N];
int n,m;
double ans;
int cmp(edge a,edge b){
return a.w<b.w;
}
double dist(int i,int j){
return sqrt((a[i]-a[j])*(a[i]-a[j])+(b[i]-b[j])*(b[i]-b[j])+(c[i]-c[j])*(c[i]-c[j]))-r[i]-r[j];
}
void init(){
for(int i=;i<n;++i) f[i]=i;
}
int fin(int x){
if(x!=f[x])f[x]=fin(f[x]);
return f[x];
}
void Kruskal(){
ans=;
int u,v,i,cnt=;
init();
for(i=;cnt<n-;++i){
u=e[i].u;
v=e[i].v;
if((u=fin(u))!=(v=fin(v))){
f[u]=v;
ans+=e[i].w;
cnt++;
}
}
}
int main(){
int i,j;
double w;
while(scanf("%d",&n),n){
for(i=;i<n;++i){
scanf("%lf%lf%lf%lf",&a[i],&b[i],&c[i],&r[i]);
}
for(m=i=;i<n-;++i){
for(j=i+;j<n;++j){
w=dist(i,j);
if(w<) w=;
e[m++]={i,j,w};
}
}
sort(e,e+m,cmp);
Kruskal();
printf("%.3f\n",ans);
}
return ;
}
poj2421 Constructing Roads（最小生成树）水题。有些点已经连边，进行标记，加边时将其边赋值为0即可。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int M=;
const int N=;
struct edge{
int u,v,w;
}e[M];
int f[N];
int g[N][N],vis[N][N];
int n,ans;
int cmp(edge a,edge b){
return a.w<b.w;
}
void init(){
for(int i=;i<=n;++i) f[i]=i;
}
int fin(int x){
if(x!=f[x])f[x]=fin(f[x]);
return f[x];
}
void Kruskal(){
ans=;
int u,v,i,cnt=;
init();
for(i=;cnt<n-;++i){
u=e[i].u;
v=e[i].v;
if((u=fin(u))!=(v=fin(v))){
f[u]=v;
ans+=e[i].w;
cnt++;
}
}
}
int main(){
int i,j,a,b,ei,m;
while(scanf("%d",&n)==){
for(i=;i<=n;++i)
for(j=;j<=n;++j)
scanf("%d",&g[i][j]);
memset(vis,,sizeof(vis));
scanf("%d",&m);
while(m--){
scanf("%d%d",&a,&b);
vis[a][b]=;
}
ei=;
for(i=;i<n;++i){
for(j=i+;j<=n;++j){
if(vis[i][j]) e[ei++]={i,j,};
else e[ei++]={i,j,g[i][j]};
}
}
sort(e,e+ei,cmp);
Kruskal();
printf("%d\n",ans);
}
return ;
}