风萧萧兮易水寒，壮士要去敲代码。本女子开学后再敲了。。
poj1258 Agri-Net(最小生成树)水题。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int inf=0x3f3f3f3f;
const int N=;
int n,m;
int g[N][N],low[N];
void prim(int u0){
int i,j,mi,v,ans=;
for(i=;i<n;++i){
low[i]=g[u0][i];
}
low[u0]=-;
for(i=;i<n;++i){
mi=inf;
v=-;
for(j=;j<n;++j)
if(low[j]!=-&&low[j]<mi){
v=j; mi=low[j];
}
ans+=low[v];
low[v]=-;
for(j=;j<n;++j){
if(g[v][j]<low[j]){
low[j]=g[v][j];
}
}
}
printf("%d\n",ans);
}
int main(){
int t,i,j;
while(scanf("%d",&n)==){
memset(g,inf,sizeof(inf));
for(i=;i<n;++i)
for(j=;j<n;++j)
scanf("%d",&g[i][j]);
prim();
}
return ;
}
poj1751 Highways(最小生成树)水题。已修好的路赋值为0。不用sqrt计算距离，因为题目没要求。做完这题后把自学时的模板改了一点，因为一开始的模板太挫。。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int inf=0x3f3f3f3f;
const int N=;
int n,m;
int g[N][N],low[N],near[N],x[N],y[N];
void prim(int u0){
int i,j,mi,v;
for(i=;i<=n;++i){
low[i]=g[u0][i];
near[i]=u0;
}
low[u0]=-;
for(i=;i<n;++i){
mi=inf;
v=-;
for(j=;j<=n;++j)
if(low[j]!=-&&low[j]<mi){
v=j; mi=low[j];
}
if(mi!=)printf("%d %d\n",near[v],v);
low[v]=-;
for(j=;j<=n;++j){
if(g[v][j]<low[j]){
low[j]=g[v][j];
near[j]=v;
}
}
}
}
int main(){
int t,i,j;
scanf("%d",&n);
memset(g,inf,sizeof(g));
for(i=;i<=n;++i) scanf("%d%d",&x[i],&y[i]);
for(i=;i<=n;++i){
for(j=i+;j<=n;++j){
g[i][j]=g[j][i]=(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);
}
}
scanf("%d",&m);
while(m--){
scanf("%d%d",&i,&j);
g[i][j]=g[j][i]=;
}
prim();
return ;
}
poj1789 Truck History（最小生成树）每种卡车类型都是由其他卡车类型派生出来，第一种除外。理解：顶点为卡车类型，边的权值为类型对（t0，d0）的距离（编码中不同字符的位置数目）。。看懂题看得头疼，其实不难做。
#include<cstdio>
#include<cstring>
using namespace std;
const int inf=0x3f3f3f3f;
const int N=;
int n;
char code[N][];
int g[N][N],low[N],a[N],ans;
void prim(int u0){
int i,j,mi,v;
ans=;
for(i=;i<n;++i){
low[i]=g[u0][i];
}
low[u0]=-;
for(i=;i<n;++i){
mi=inf;
v=-;
for(j=;j<n;++j)
if(low[j]!=-&&low[j]<mi){
v=j; mi=low[j];
}
ans+=low[v];
low[v]=-;
for(j=;j<n;++j){
if(g[v][j]<low[j])
low[j]=g[v][j];
}
}
printf("The highest possible quality is 1/%d.\n",ans);
}
int main(){
int i,j,k,d;
while(scanf("%d",&n),n){
memset(g,inf,sizeof(g));
for(i=;i<n;++i) scanf("%s",code[i]);
for(i=;i<n-;++i){
for(j=i+;j<n;++j){
d=;
for(k=;k<;++k)
d+=(code[i][k]!=code[j][k]);
g[i][j]=g[j][i]=d;
}
}
prim();
}
return ;
}
poj2349 Arctic Network（最小生成树）求出最小生成树，将边从大到小排序，前s-1条用s个卫星通信，第s大边即为答案。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
const int inf=0x3f3f3f3f;
const int N=;
int n,s;
double g[N][N],low[N],d[N],x[N],y[N];
int cmp(int a,int b){
return a > b;
}
void prim(int u0){
int i,j,mi,v;
int cnt=;
for(i=;i<n;++i){
low[i]=g[u0][i];
}
low[u0]=-;
for(i=;i<n;++i){
mi=inf;
v=-;
for(j=;j<n;++j)
if(low[j]!=-&&low[j]<mi){
v=j; mi=low[j];
}
d[cnt++]=low[v];
low[v]=-;
for(j=;j<n;++j){
if(g[v][j]<low[j])
low[j]=g[v][j];
}
}
sort(d,d+cnt,cmp);
printf("%.2f\n",d[s-]);
}
int main(){
int t,i,j;
double d;
scanf("%d",&t);
while(t--){
memset(g,inf,sizeof(g));
scanf("%d%d",&s,&n);
for(i=;i<n;++i) scanf("%lf%lf",&x[i],&y[i]);
for(i=;i<n;++i){
for(j=i+;j<n;++j){
d=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]));
g[i][j]=g[j][i]=d;
}
}
prim();
}
return ;
}
poj3026 Borg Maze（最小生成树，bfs预处理）因为这题我几天没打码了，今天做出来感觉也不是很难。还是深感基础之弱内心痛苦。。对了，记得看discuss哦，如果你不想多挥霍青春的话。。。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int inf=0x3f3f3f3f;
const int N=;
const int M=;
int x,y;
int n;
int dir[][]={,,,-,,,-,};
int g[M][M],low[M];
char mp[N][N];
int G[N][N];
int vd[N][N];
void bfs(int sx,int sy){
queue<pair<int,int> >q;
while(!q.empty())q.pop();
memset(vd,-,sizeof(vd));
vd[sx][sy]=;
q.push(make_pair(sx,sy));
while(!q.empty()){
pair<int,int>u=q.front(); q.pop();
if(G[u.first][u.second]>)
g[G[sx][sy]][G[u.first][u.second]]=vd[u.first][u.second];
for(int i=;i<;++i){
int xx=u.first+dir[i][];
int yy=u.second+dir[i][];
if(mp[xx][yy]=='#'||vd[xx][yy]!=-)continue;
vd[xx][yy]=vd[u.first][u.second]+;
q.push(make_pair(xx,yy));
}
}
}
void prim(int u0){
int i,j,mi,v,ans=;
for(i=;i<n;++i) low[i]=g[u0][i];
low[u0]=-;
for(i=;i<n-;++i){
mi=inf;
v=-;
for(j=;j<n;++j)
if(low[j]!=-&&low[j]<mi){
v=j; mi=low[j];
}
ans+=low[v];
low[v]=-;
for(j=;j<n;++j){
if(g[v][j]<low[j]){
low[j]=g[v][j];
}
}
}
printf("%d\n",ans);
}
int main(){
int t,i,j;
scanf("%d",&t);
while(t--){
scanf("%d%d",&x,&y);
gets(mp[]);
for(i=;i<y;++i) gets(mp[i]);
n=;
for(i=;i<y;++i){
for(j=;j<x;++j){
if(mp[i][j]=='A'||mp[i][j]=='S')
G[i][j]=n++;
else G[i][j]=-;
}
}
for(i=;i<y;++i)
for(j=;j<x;++j)
if(G[i][j]>) bfs(i,j);
prim();
}
return ;
}