先说算法：解释算法思想，可以直接从底下的代码复制作为模版
2.Kruskal。http://baike.baidu.com/view/247951.htm
相信百度百科比我讲得绝对好多了。
图论最主要是建图的思想，然后就是上bin神的模版
A - Jungle Roads
裸最小生成树。注意：输入的时候用cin或者%s输入，不要读取字符之间的空格作为分隔符（有可能输入的时候输入的多个空格作为间隔导致出错）。无论用Prim还是Kruskal简直秒杀。
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <string>
#include <map>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <cctype>
using namespace std;
#define input freopen("input.txt","r",stdin)
#define output freopen("output.txt","w",stdout)
#define For1(i,a,b) for (i=a;i<b;i++)
#define For2(i,a,b) for (i=a;i<=b;i++)
#define Dec(i,a,b) for (i=a;i>b;i--)
#define Dec2(i,a,b) for (i=a;i>=b;i--)
#define Fill(x,a) memset(x,a,sizeof(x))
#define inf 1<<30
const int maxn=200;
const int maxm=20000;
int F[maxn];
struct Edge
{
int u,v,w;
}edge[maxm];
int tol;
void addedge(int u,int v,int w)
{
edge[tol].u=u;
edge[tol].v=v;
edge[tol++].w=w;
}
bool cmp(Edge a,Edge b)
{
return a.w<b.w;
}
int find(int x)
{
if (F[x]==-1) return x;
return F[x]=find(F[x]);
}
int Kruskal(int n)
{
Fill(F,-1);
sort(edge,edge+tol,cmp);
int cnt=0;
int ans=0;
for(int i=0;i<tol;i++)
{
int u=edge[i].u;
int v=edge[i].v;
int w=edge[i].w;
int t1=find(u);
int t2=find(v);
if (t1!=t2)
{
ans+=w;
F[t1]=t2;
cnt++;
}
if (cnt==n-1) break;
}
// (cnt<n-1) return -1;
return ans;
}
int main()
{
//input;
int i,n,m,x,y,z,ans,t,j,k;
char s[10],s0[10];
while(cin>>n,n)
{
ans=tol=0;
For2(i,1,n-1)
{
scanf("%s%d",s,&t);
if (t==0) continue;
while(t--)
{
scanf("%s%d",s0,&k);
addedge(s[0]-'A',s0[0]-'A',k);
addedge(s0[0]-'A',s[0]-'A',k);
}
//addedge(y,x,z);
}
ans=Kruskal(n);
cout<<ans<<endl;
}
return 0;
}B - Networking
注意点与点之间是多重边的问题。所以边的初始化应该是无穷大，之后每次选择最小的（Prim）。Kruskal建图更加方便，不管三七二十一全部扔进去排序，然后并查***自动帮助我们去重的。建图之后裸最小生成树
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <string>
#include <map>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <cctype>
using namespace std;
#define input freopen("input.txt","r",stdin)
#define output freopen("output.txt","w",stdout)
#define For1(i,a,b) for (i=a;i<b;i++)
#define For2(i,a,b) for (i=a;i<=b;i++)
#define Dec(i,a,b) for (i=a;i>b;i--)
#define Dec2(i,a,b) for (i=a;i>=b;i--)
#define Fill(x,a) memset(x,a,sizeof(x))
#define inf 1<<30
const int maxn=200;
const int maxm=20000;
int F[maxn];
struct Edge
{
int u,v,w;
}edge[maxm];
int tol;
void addedge(int u,int v,int w)
{
edge[tol].u=u;
edge[tol].v=v;
edge[tol++].w=w;
}
bool cmp(Edge a,Edge b)
{
return a.w<b.w;
}
int find(int x)
{
if (F[x]==-1) return x;
return F[x]=find(F[x]);
}
int Kruskal(int n)
{
Fill(F,-1);
sort(edge,edge+tol,cmp);
int cnt=0;
int ans=0;
for(int i=0;i<tol;i++)
{
int u=edge[i].u;
int v=edge[i].v;
int w=edge[i].w;
int t1=find(u);
int t2=find(v);
if (t1!=t2)
{
ans+=w;
F[t1]=t2;
cnt++;
}
if (cnt==n-1) break;
}
if (cnt<n-1) return 0;
return ans;
}
int main()
{
//input;
int i,n,m,x,y,z,ans,t,j,k;
char s[10],s0[10];
while(cin>>n,n)
{
cin>>m;
ans=tol=0;
For2(i,1,m)
{
scanf("%d%d%d",&x,&y,&z);
addedge(x,y,z);
addedge(y,x,z);
}
ans=Kruskal(n);
cout<<ans<<endl;
}
return 0;
}C - Building a Space Station
给的是n个点的坐标以及以该点为坐标的球的半径。
建图：两个for循环，求出两个球球面的距离。先算出两个球心之间的距离，若该距离<两个半径之和，则两个球面的距离=球心距离-两半径之和；否则，两个球面必定有交点，距离赋值为0
之后模版走起
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <string>
#include <map>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <cctype>
using namespace std;
#define input freopen("input.txt","r",stdin)
#define output freopen("output.txt","w",stdout)
#define For1(i,a,b) for (i=a;i<b;i++)
#define For2(i,a,b) for (i=a;i<=b;i++)
#define Dec(i,a,b) for (i=a;i>b;i--)
#define Dec2(i,a,b) for (i=a;i>=b;i--)
#define Fill(x,a) memset(x,a,sizeof(x))
#define inf 1<<30
const int maxn=200;
const int maxm=10050;
int F[maxn];
double x[maxn];
double y[maxn];
double z[maxn];
double r[maxn];
struct Edge
{
int u,v;
double w;
}edge[maxm];
int tol;
void addedge(int u,int v,double w)
{
edge[tol].u=u;
edge[tol].v=v;
edge[tol++].w=w;
}
bool cmp(Edge a,Edge b)
{
return a.w<b.w;
}
int find(int x)
{
if (F[x]==-1) return x;
return F[x]=find(F[x]);
}
double Kruskal(int n)
{
Fill(F,-1);
sort(edge,edge+tol,cmp);
int cnt=0;
double ans=0;
for(int i=0;i<tol;i++)
{
int u=edge[i].u;
int v=edge[i].v;
double w=edge[i].w;
int t1=find(u);
int t2=find(v);
if (t1!=t2)
{
ans+=w;
F[t1]=t2;
cnt++;
}
if (cnt==n-1) break;
}
// (cnt<n-1) return -1;
return ans;
}
int main()
{
//input;
int i,n,m,t,j,k;
double ans;
while(cin>>n)
{
if (n<=0) break;
ans=tol=0;
For2(i,1,n)
{
scanf("%lf%lf%lf%lf",&x[i],&y[i],&z[i],&r[i]);
For2(j,1,i-1)
{
double dist=sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])+(z[i]-z[j])*(z[i]-z[j]))-r[i]-r[j];
if (dist<=0) addedge(i,j,0);
else addedge(i,j,dist);
}
}
ans=Kruskal(n);
//cout<<ans<<endl;
printf("%.3lf\n",ans);
}
return 0;
}D - Constructing Roads
题中给了n*n的矩阵，值是i点到j点的建边的花费，其中已经建好了m条边，题中求还需要花费多少才能使该图连通
思路：Kruskal更好做（并查集）。初始化之后，将m条边依次加入并查集，只要能合并及时合并。
剪枝：一个小的剪枝就是并查集的合并只需要合并n-1次就必然的已经有解，因此用一个全局变量cnt统计次数，及时退出
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <string>
#include <map>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <cctype>
using namespace std;
#define input freopen("input.txt","r",stdin)
#define output freopen("output.txt","w",stdout)
#define For1(i,a,b) for (i=a;i<b;i++)
#define For2(i,a,b) for (i=a;i<=b;i++)
#define Dec(i,a,b) for (i=a;i>b;i--)
#define Dec2(i,a,b) for (i=a;i>=b;i--)
#define Fill(x,a) memset(x,a,sizeof(x))
#define inf 1<<30
const int maxn=1000;
const int maxm=500000;
int F[maxn];
int cnt;
struct Edge
{
int u,v,w;
}edge[maxm];
int tol;
int Map[maxn][maxn];
void addedge(int u,int v,int w)
{
edge[tol].u=u;
edge[tol].v=v;
edge[tol++].w=w;
}
bool cmp(Edge a,Edge b)
{
return a.w<b.w;
}
int find(int x)
{
if (F[x]==-1) return x;
return F[x]=find(F[x]);
}
int Kruskal(int n)
{
sort(edge,edge+tol,cmp);
int ans=0;
for(int i=0;i<tol;i++)
{
int u=edge[i].u;
int v=edge[i].v;
int w=edge[i].w;
int t1=find(u);
int t2=find(v);
if (t1!=t2)
{
ans+=w;
F[t1]=t2;
cnt++;
}
if (cnt==n-1) break;
}
if (cnt<n-1) return 0;
return ans;
}
int main()
{
//input;
int i,n,m,x,y,z,ans,t,j,k;
while(cin>>n)
{
cnt=ans=tol=0;
Fill(Map,0);
Fill(F,-1);
For2(i,1,n)For2(j,1,n)scanf("%d",&Map[i][j]);
For2(i,1,n-1)
For2(j,i+1,n)
{
addedge(i,j,Map[i][j]);
//addedge(j,i,Map[i][j]);
}
cin>>m;
For2(i,1,m)
{
scanf("%d%d",&x,&y);
int u=find(x);
int v=find(y);
if (u!=v)
{
F[u]=v;
cnt++;
}
//F[x]=y;
}
ans=Kruskal(n);
cout<<ans<<endl;
}
return 0;
}E - QS Network
这个题读题特别费劲，其实还是模版题
建图：给你的n*n矩阵不是直接的花费，而是边花费，总花费=边花费+两个端点的花费。之后模版走起
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <string>
#include <map>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <cctype>
using namespace std;
#define input freopen("input.txt","r",stdin)
#define output freopen("output.txt","w",stdout)
#define For1(i,a,b) for (i=a;i<b;i++)
#define For2(i,a,b) for (i=a;i<=b;i++)
#define Dec(i,a,b) for (i=a;i>b;i--)
#define Dec2(i,a,b) for (i=a;i>=b;i--)
#define Fill(x,a) memset(x,a,sizeof(x))
#define inf 1<<30
const int maxn=600;
const int maxm=300000;
int F[maxn];
int cost[maxn];
int Cost[maxn][maxn];
struct Edge
{
int u,v,w;
}edge[maxm];
int tol;
void addedge(int u,int v,int w)
{
edge[tol].u=u;
edge[tol].v=v;
edge[tol++].w=w;
}
bool cmp(Edge a,Edge b)
{
return a.w<b.w;
}
int find(int x)
{
if (F[x]==-1) return x;
return F[x]=find(F[x]);
}
int Kruskal(int n)
{
Fill(F,-1);
sort(edge,edge+tol,cmp);
int cnt=0;
int ans=0;
for(int i=0;i<tol;i++)
{
int u=edge[i].u;
int v=edge[i].v;
int w=edge[i].w;
int t1=find(u);
int t2=find(v);
if (t1!=t2)
{
ans+=w;
F[t1]=t2;
cnt++;
}
if (cnt==n-1) break;
}
// (cnt<n-1) return -1;
return ans;
}
int main()
{
//input;
int i,n,m,x,y,z,ans,t,j,k;
cin>>t;
while(t--)
{
Fill(cost,0);
Fill(Cost,0);
ans=tol=0;
cin>>n;
For2(i,1,n) scanf("%d",&cost[i]);
For2(i,1,n)For2(j,1,n) scanf("%d",&Cost[i][j]);
For2(i,1,n-1)
For2(j,i+1,n)
{
addedge(i,j,cost[i]+cost[j]+Cost[i][j]);
//addedge(j,i,cost[i]+cost[j]+Cost[i][j]);
}
ans=Kruskal(n);
cout<<ans<<endl;
}
return 0;
}PS：代码的逻辑性都是一样的，之后为了大家的阅读方便（不要揭穿我，其实是我懒），就不贴代码了
F - Truck History
建图：每两个字符串之间的相同位置不同字符的个数为其权值模版走起
G - Arctic Network
Kruskal建图
求最小生成树第K大（小）边的题目。
一般这种题目都是一个原本的连通图分割成s个连通分量，求这些连通分量中最长边。
那么这就是求原图中最小生成树中第s大的边的长度。
因为连接这s个连通分量的边肯定要求是前s-1长的边，这些边有s-1个。
用Kruskal更方便，直接在返回的时候return所求边即可
H - Highways
模版题。但是注意输出时与权值无关，而是在图中需要建立那些边
I - Agri-Net
模版题
J - Borg Maze
这个专题里面仅有的一道综合题：最小生成树+BFS
题意：n*m的矩阵，空格代表可以走，#表示墙，A和S代表其中的点
建图：把图中各个字母之间的BFS的路径值存为边权值，跑最小生成树模版
思路：在输入时，把读入的读全部改掉：字母改为该点的数字编号，依次递增；空格和#改为自己习惯的搜索分隔符
细节：此题用Kruskal更方便，因为在添加边的时候，在图中便已知了起点和终点，权值便是BFS跑出的值
模版走起AC（其中的原理好懂，代码不太好写，祝大家1A）
（就是不给代码，你来打我啊）
K - The Unique MST
次小生成树http://www.cnblogs.com/hxsyl/p/3290832.html
我的理解就是：把属于最小生成树的每一条边都试着从不属于的交换一条边，若仍然满足是生成树则记录其权值，所有可行的情况中权值最小的就是次小生成树
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <string>
#include <map>
#include <vector>
#include <set>
#include <queue>
#include <stack>
#include <cctype>
using namespace std;
#define input freopen("input.txt","r",stdin)
#define output freopen("output.txt","w",stdout)
#define For1(i,a,b) for (i=a;i<b;i++)
#define For2(i,a,b) for (i=a;i<=b;i++)
#define Dec(i,a,b) for (i=a;i>b;i--)
#define Dec2(i,a,b) for (i=a;i>=b;i--)
#define Fill(x,a) memset(x,a,sizeof(x))
#define inf 1<<30
const int maxn=200;
const int maxm=20000;
bool vis[maxn];
int lowc[maxn];
int pre[maxn];
int Max[maxn][maxn];
bool used[maxn][maxn];
int cost[maxn][maxn];
int Prim(int cost[][maxn],int n)
{
int ans=0,i,j;
Fill(vis,0);
Fill(Max,0);
Fill(used,0);
vis[1]=true;
pre[1]=-1;
For2(i,2,n)
{
lowc[i]=cost[1][i];
pre[i]=1;
}
lowc[1]=0;
For2(i,2,n)
{
int minc=inf;
int p=-1;
For2(j,2,n)
if (!vis[j]&&minc>lowc[j])
{
minc=lowc[j];
p=j;
}
if (minc==inf) return -1;
ans+=minc;
vis[p]=true;
used[p][pre[p]]=used[pre[p]][p]=true;
For2(j,1,n)
{
if (vis[j]&&used[p][j]) Max[p][j]=Max[j][p]=cost[j][p];
else if (vis[j]) Max[j][p]=Max[p][j]=max(Max[j][pre[p]],lowc[p]);
if (!vis[j]&&lowc[j]>cost[p][j])
{
lowc[j]=cost[p][j];
pre[j]=p;
}
}
}
return ans;
}
int main()
{
//input;
int t;
int n,m,i,j,x,y,z;
cin>>t;
while(t--)
{
scanf("%d%d",&n,&m);
For2(i,1,n)For2(j,1,n)cost[i][j]=inf;
For2(i,1,n) cost[i][i]=0;
For2(i,1,m)
{
scanf("%d%d%d",&x,&y,&z);cost[x][y]=cost[y][x]=z;
}
int ans=Prim(cost,n);
//if (ans>0) cout<<ans<<endl;
//else puts("Not Unique!");
int second=inf,temp=inf;
For2(i,1,n)
For2(j,1,n)
if (!used[i][j]&&cost[i][j]!=0&&cost[i][j]!=inf)
{
temp=ans-Max[i][j]+cost[i][j];
second=min(second,temp);
}
if (second==ans) puts("Not Unique!");
else cout<<ans<<endl;
}
return 0;
}Max[i][j]表示的是在最小生成树中，点i到点j经过的所有的边中，权值最大的一条
used[i][j]为真，代表它属于最小生成树；否则，不属于
Prim的之后那段代码，本质上就是对Dijkstra中的两点权值的更改与重新记录，各位大神画个图就可以明白啦
L
M
N
都是跟前面非常类似的，看懂了题自己去刷吧，本弱不管了
祝：大家早日AK此专题，还有希望各位大神刷完别的专题也能写份题解让本弱学习学习！
谢谢bin神对本弱的大力支持！
京公网安备 11010502036488号