Highways(prim和Kruskal)

poj1751

本题的意思是找出生成树中两个城镇直接最短路径的最大值

KruskalAC代码

先把已经连接的城市用并查集(merge)并到一起,然后根据Kruskal算法输出其他未连通的最短路径即可
注意:本题数据过大用kruskal容易超时,注意调整存储

#include<iostream>
#include<algorithm>
#define N 750
using namespace std;
int f[N];
int n;
struct node
{
    int x,y;
}p[N];
struct edge
{
    int u,v,w;
}e[N*N];bool cmp(edge a, edge b)
{
    return a.w<b.w;
}int getf(int v)
{
    if(f[v]==v) return v;f[v] = getf(f[v]);return f[v];
}int merge(int v,int u)
{
    int t1,t2;t1 = getf(v);t2 = getf(u);if(t1!=t2){
    f[t2] = t1;return 1;}return 0;
}
int dis(int x1,int y1,int x2,int y2)
{
    return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2);
}int main()
{
    while(cin>>n){
    for(int i=1;i<=n;i++)cin>>p[i].x>>p[i].y;int k=0;for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++){
    e[k].u = i;e[k].v = j;e[k].w = dis(p[i].x,p[i].y,p[j].x,p[j].y);k++;}for(int i=1;i<=n;i++) f[i] = i;int a,b,m;cin>>m;for(int i=1;i<=m;i++){
    cin>>a>>b;merge(a,b);}sort(e,e+k,cmp);for(int i=0;i<k;i++){
    if(merge(e[i].u,e[i].v))cout<<e[i].u<<" "<<e[i].v<<endl;}}}

primAC代码

#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#define N 1000 
#define INF 0x3f3f3f3f
using namespace std;int mapp[N][N];
int dis[N],flag[N],p[N];
struct edge
{
    int x;int y;
};
struct edge e[1100];int main()
{
    int n,m;while(cin>>n){
    memset(flag,0,sizeof(flag));for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)if(i==j) mapp[i][j] = 0;else mapp[i][j] = INF;for(int i=1;i<=n;i++)cin>>e[i].x>>e[i].y;for(int i=1;i<=n;i++)for(int j=i;j<=n;j++){
    mapp[i][j] = mapp[j][i] = (e[i].x-e[j].x)*(e[i].x-e[j].x)+(e[i].y-e[j].y)*(e[i].y-e[j].y);}cin>>m;for(int i=1;i<=m;i++){
    int x,y;cin>>x>>y;mapp[x][y] = mapp[y][x] = 0;}for(int i=1;i<=n;i++){
    dis[i] = mapp[1][i];p[i] = 1;}flag[1] = 1;for(int i=1;i<n;i++){
    int minn = INF;int u;for(int j=1;j<=n;j++)if(flag[j]==0&&dis[j]<minn){
    minn = dis[j];u = j;}flag[u] = 1;if(mapp[p[u]][u])printf("%d %d\n",u,p[u]);for(int k=1;k<=n;k++)if(flag[k]==0&&dis[k]>mapp[u][k]){
    dis[k] = mapp[u][k];p[k] = u;}}}return 0;
}