kuangbin 最小生成树

A & M - Jungle Roads HDU - 1301

题意：字母之间的路，求最小生成树

题解：处理好建边以后就是一个Prime

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

#include<sstream>

#include<cmath>

#include<stack>

#include<cstdlib>

#include <vector>

#include <set>

#include<queue>

#include<map>

using namespace std;

#define ll long long

#define llu unsigned long long

#define INF 0x3f3f3f3f

#define PI acos(-1.0)

const int maxn =  ;

const ll mod = 1e9+;

const double eps = 1e-;

bool vis[maxn];

int lowc[maxn];

int Prim(int cost[][maxn],int n)

{

    int ans = ;

    memset(vis,false,sizeof vis);

    vis[] = true;

    for(int i=;i<n;i++)

        lowc[i] = cost[][i];

    for(int i=;i<n;i++)

    {

        int minc = INF;

        int p = -;

        for(int j=;j<n;j++)

        {

            if(!vis[j] && minc > lowc[j])

            {

                minc = lowc[j];

                p = j;

            }

        }

        if(minc == INF)

            return -;

        ans += minc;

        vis[p] = true;

        for(int j=;j<n;j++)

            if(!vis[j] && lowc[j] > cost[p][j])

                lowc[j] = cost[p][j];

    }

    return ans;

}

int main()

{

    int n;

    while(scanf("%d",&n) && n)

    {

        int cost[maxn][maxn];

        for(int i=;i<maxn;i++)

        {

            for(int j=;j<maxn;j++)

                if(i == j)

                    cost[i][j] = ;

                else

                    cost[i][j] = INF;

        }

        for(int i=;i<n;i++)

        {

            char a;

            cin>>a;

            int num;

            cin>>num;

            for(int i=;i<num;i++)

            {

                char ch;

                int len;

                cin>>ch>>len;

                cost[a-'A'][ch-'A'] = len;

                cost[ch-'A'][a-'A'] = len;

            }

        }

        int ans = Prim(cost,n);

        cout<<ans<<endl;

    }

}

B - Networking POJ - 1287

题意：有重复边的跑最小生成树

题解：边取小跑Prime

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

#include<sstream>

#include<cmath>

#include<stack>

#include<cstdlib>

#include <vector>

#include <set>

#include<queue>

using namespace std;

#define ll long long

#define llu unsigned long long

#define INF 0x3f3f3f3f

#define PI acos(-1.0)

const int maxn = 1e2+;

bool vis[maxn];

int lowc[maxn];

int Prim(int cost[][maxn],int n)

{

    int ans = ;

    memset(vis,false,sizeof vis);

    vis[] = true;

    for(int i=;i<=n;i++)

        lowc[i] = cost[][i];

    for(int i=;i<=n;i++)

    {

        int minc = INF;

        int p = -;

        for(int j=;j<=n;j++)

            if(!vis[j] && minc > lowc[j])

            {

                minc = lowc[j];

                p = j;

            }

        if(minc == INF)

            return -;

        ans += minc;

        vis[p] = true;

        for(int j=;j<=n;j++)

            if(!vis[j] && lowc[j] > cost[p][j])

                lowc[j] = cost[p][j];

    }

    return ans;

}

int main()

{

    int n,m;

    while(scanf("%d",&n) && n)

    {

        scanf("%d",&m);

        int cost[maxn][maxn];

        for(int i=;i<=n;i++)

            for(int j=;j<=n;j++)

                if(i == j)

                    cost[i][j] = ;

                else

                    cost[i][j] = INF;

        for(int i=;i<m;i++)

        {

            int a,b,c;

            scanf("%d%d%d",&a,&b,&c);

            cost[a][b] = min(cost[a][b],c);

            cost[b][a] = min(cost[b][a],c);

            cost[a][b] = cost[b][a] = min(cost[a][b],cost[b][a]);

        }

        int ans = Prim(cost,n);

        printf("%d\n",ans);

    }

}

C - Building a Space Station POJ - 2031

题意：三维上的球上建最小生成树

题解：处理边即可

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

#include<sstream>

#include<cmath>

#include<stack>

#include<cstdlib>

#include <vector>

#include <set>

#include<queue>

using namespace std;

#define ll long long

#define llu unsigned long long

#define INF 0x3f3f3f3f

#define PI acos(-1.0)

const int maxn = 1e2+;

struct node

{

    double x,y,z,r;

}a[maxn];

double dis(double x1,double y1,double z1,double r1,double x2,double y2,double z2,double r2)

{

    double len = (x1-x2)*(x1-x2) + (y1-y2)*(y1-y2) + (z1-z2)*(z1-z2);

    double ans = sqrt(len) - r1 - r2;

    return max(0.0,ans);

}

bool vis[maxn];

double lowc[maxn];

double Prime(double cost[][maxn],int n)

{

    double ans = ;

    memset(vis,,sizeof vis);

    vis[] = true;

    for(int i=;i<n;i++)

        lowc[i] = cost[][i];

    for(int i=;i<n;i++)

    {

        double minc = 9999999999.9;

        int p = -;

        for(int j=;j<n;j++)

            if(!vis[j] && minc > lowc[j])

            {

                p = j;

                minc = lowc[j];

            }

        ans += minc;

        vis[p] = true;

        for(int j=;j<n;j++)

            if(!vis[j] && lowc[j] > cost[p][j])

                lowc[j] = cost[p][j];

    }

    return ans;

}

int main()

{

    int n;

    while(scanf("%d",&n) && n)

    {

        double cost[maxn][maxn];

        for(int i=;i<n;i++)

            scanf("%lf %lf %lf %lf",&a[i].x,&a[i].y,&a[i].z,&a[i].r);

        for(int i=;i<n;i++)

            for(int j=;j<n;j++)

                cost[i][j] = dis(a[i].x,a[i].y,a[i].z,a[i].r,a[j].x,a[j].y,a[j].z,a[j].r);

        double ans = Prime(cost,n);

        printf("%.3f\n",ans);

    }

}

D - Constructing Roads POJ - 2421

题意：邻接矩阵有些边权值为0，求最小生成树

题解：Prim

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

#include<sstream>

#include<cmath>

#include<stack>

#include<cstdlib>

#include <vector>

#include <set>

#include<queue>

using namespace std;

#define ll long long

#define llu unsigned long long

#define INF 0x3f3f3f3f

#define PI acos(-1.0)

const int maxn = 1e2+;

int vis[maxn];

int lowc[maxn];

int cost[maxn][maxn];

int Prim(int cost[][maxn],int n)

{

    int ans = ;

    memset(vis,,sizeof vis);

    vis[] = true;

    for(int i=;i<=n;i++)

        lowc[i] = cost[][i];

    for(int i=;i<=n;i++)

    {

        int minc = INF;

        int p = -;

        for(int j=;j<=n;j++)

            if(!vis[j] && minc > lowc[j])

            {

                minc = lowc[j];

                p = j;

            }

        ans += minc;

        vis[p] = true;

        for(int j=;j<=n;j++)

            if(!vis[j] && lowc[j] > cost[p][j])

                lowc[j] = cost[p][j];

    }

    return ans;

}

int main()

{

    int n;

    scanf("%d",&n);

    for(int i=;i<=n;i++)

        for(int j=;j<=n;j++)

            scanf("%d",&cost[i][j]);

    int q;

    scanf("%d",&q);

    for(int i=;i<q;i++)

    {

        int a,b;

        scanf("%d%d",&a,&b);

        cost[a][b] = cost[b][a] = ;

    }

    int ans = Prim(cost,n);

    printf("%d\n",ans);

}

E - QS Network ZOJ - 1586

题意：最小生出树，边的值还需要加上两个顶点的值

题解：只需要将顶点的值加到其权值上即可

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

#include<sstream>

#include<cmath>

#include<stack>

#include<cstdlib>

#include <vector>

#include <set>

#include<queue>

using namespace std;

#define ll long long

#define llu unsigned long long

#define INF 0x3f3f3f3f

#define PI acos(-1.0)

const int maxn = 1e3+;

bool vis[maxn];

int lowc[maxn];

int cost[maxn][maxn];

int a[maxn];

int prim(int cost[][maxn],int n)

{

    int ans =  ;

    memset(vis,false,sizeof vis);

    vis[] = true;

    for(int i=;i<=n;i++)

        lowc[i] = cost[][i];

    for(int i=;i<=n;i++)

    {

        int minc = INF;

        int p = -;

        for(int j=;j<=n;j++)

        {

            if(!vis[j] && minc > lowc[j])

            {

                minc = lowc[j];

                p = j;

            }

        }

        ans += minc;

        vis[p] = true;

        for(int j=;j<=n;j++)

            if(!vis[j] && lowc[j] > cost[p][j])

                lowc[j] = cost[p][j];

    }

    return ans;

}

int main()

{

    int t;

    scanf("%d",&t);

    while(t--)

    {

        int n;

        int ans = ;

        scanf("%d",&n);

        for(int i=;i<=n;i++)

            scanf("%d",&a[i]);

        for(int i=;i<=n;i++)

            for(int j=;j<=n;j++) {

                scanf("%d", &cost[i][j]);

                cost[i][j] += a[i] + a[j];

            }

        ans += prim(cost,n);

        printf("%d\n",ans);

    }

}

F - Truck History POJ - 1789

题意：两个字符串之间不同的个数为边的权值，跑最小生成树

题解：处理边之后跑最小生成树

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

#include<sstream>

#include<cmath>

#include<stack>

#include<cstdlib>

#include <vector>

#include <set>

#include<queue>

using namespace std;

#define ll long long

#define llu unsigned long long

#define INF 0x3f3f3f3f

#define PI acos(-1.0)

const int maxn = 2e3+;

bool vis[maxn];

int lowc[maxn];

int cost[maxn][maxn];

int a[maxn];

int prim(int cost[][maxn],int n)

{

    int ans =  ;

    memset(vis,false,sizeof vis);

    vis[] = true;

    for(int i=;i<=n;i++)

        lowc[i] = cost[][i];

    for(int i=;i<=n;i++)

    {

        int minc = INF;

        int p = -;

        for(int j=;j<=n;j++)

        {

            if(!vis[j] && minc > lowc[j])

            {

                minc = lowc[j];

                p = j;

            }

        }

        ans += minc;

        vis[p] = true;

        for(int j=;j<=n;j++)

            if(!vis[j] && lowc[j] > cost[p][j])

                lowc[j] = cost[p][j];

    }

    return ans;

}

int main()

{

    int n;

    while(scanf("%d",&n) && n)

    {

        char str[maxn][];

        for(int i=;i<=n;i++)

            scanf("%s",str[i]);

        for(int i=;i<=n;i++)

            for(int j=;j<=n;j++)

            {

                int tmp = ;

                for(int k=;k<;k++)

                    if(str[i][k] != str[j][k])

                        tmp++;

                cost[i][j]  = cost[j][i] = tmp;

            }

        int ans  = prim(cost,n);

        printf("The highest possible quality is 1/%d.\n",ans);

    }

}

J - Borg Maze POJ - 3026

题意：迷宫之中的MST

题解：先bfs预处理，之后在进行MST，输入的时候有坑点，wa了好几次

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

#include<sstream>

#include<cmath>

#include<stack>

#include<cstdlib>

#include <vector>

#include <set>

#include<queue>

using namespace std;

#define ll long long

#define llu unsigned long long

#define INF 0x3f3f3f3f

#define PI acos(-1.0)

const int maxn = ;

int tree[maxn][maxn],id[maxn][maxn],dis[maxn][maxn],n,m,tot;

bool vis[maxn][maxn];

int lowc[maxn],visit[maxn];

char mp[maxn][maxn];

int dx[] = {,,,-};

int dy[] = {,,-,};

struct node

{

    int x,y;

};

bool check(int x,int y)

{

    if(x >=  && x <= n && y >=  && y <= m && !vis[x][y] && mp[x][y] != '#')

        return true;

    return false;

}

void bfs(int x,int y)

{

    memset(vis,false,sizeof vis);

    memset(dis,,sizeof dis);

    queue<node>que;

    node temp;

    temp.x = x;

    temp.y = y;

    que.push(temp);

    vis[x][y] = true;

    while(!que.empty())

    {

        temp = que.front();

        que.pop();

        for(int i=;i<;i++)

        {

            int nx = temp.x + dx[i];

            int ny = temp.y + dy[i];

            if(check(nx,ny))

            {

                vis[nx][ny] = true;

                dis[nx][ny] = dis[temp.x][temp.y] + ;

                if(mp[nx][ny] == 'A' || mp[nx][ny] == 'S')

                    tree[id[x][y]][id[nx][ny]] = tree[id[nx][ny]][id[x][y]] = dis[nx][ny];

                que.push(node{nx,ny});

            }

        }

    }

}

int Prime(int cost[][maxn],int n)

{

    int ans = ;

    memset(visit,false,sizeof visit);

    visit[] = true;

    for(int i=;i<=n;i++)

        lowc[i] = cost[][i];

    for(int i=;i<=n;i++)

    {

        int minc = INF;

        int p = -;

        for(int j=;j<=n;j++)

            if(!visit[j] && minc > lowc[j])

            {

                minc = lowc[j];

                p = j;

            }

        ans += minc;

        visit[p] = true;

        for(int j=;j<=n;j++)

            if(!visit[j] && lowc[j] > cost[p][j])

                lowc[j] = cost[p][j];

    }

    return ans;

}

int main()

{

    int t;

    scanf("%d",&t);

    while(t--)

    {

        int tot = ;

        scanf("%d%d ",&m,&n);

        for(int i=;i<=n;i++)

            gets(mp[i] + );

        for(int i=;i<=n;i++)

            for(int j=;j<=n;j++)

                if(mp[i][j] == 'A' || mp[i][j] == 'S')

                    id[i][j] = ++tot;

        for(int i=;i<=tot;i++)

            for(int j=;j<=tot;j++)

                if(i == j)

                    tree[i][j] = ;

                else

                    tree[i][j] = INF;

        for(int i=;i<=n;i++)

            for(int j=;j<=n;j++)

                if(mp[i][j] == 'A' || mp[i][j] == 'S')

                    bfs(i,j);

        int ans = Prime(tree,tot);

        printf("%d\n",ans);

    }

}

L - 还是畅通工程 HDU - 1233

题意：直接就是求最小生成树了

题解：板子

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

#include<sstream>

#include<cmath>

#include<stack>

#include<cstdlib>

#include <vector>

#include <set>

#include<queue>

#include<map>

using namespace std;

#define ll long long

#define llu unsigned long long

#define INF 0x3f3f3f3f

#define PI acos(-1.0)

const int maxn =  ;

const ll mod = 1e9+;

const double eps = 1e-;

int lowc[maxn];

bool vis[maxn];

int Prime(int cost[][maxn],int n)

{

    int ans = ;

    memset(vis,false,sizeof vis);

    vis[] = true;

    for(int i=;i<n;i++)

        lowc[i] = cost[][i];

    for(int i=;i<n;i++)

    {

        int minc = INF;

        int p = -;

        for(int j=;j<n;j++)

        {

            if(!vis[j] && minc > lowc[j])

            {

                minc = lowc[j];

                p = j;

            }

        }

        if(minc == INF)

            return -;

        ans += minc;

        vis[p] = true;

        for(int j=;j<n;j++)

            if(!vis[j] && lowc[j] > cost[p][j])

                lowc[j] = cost[p][j];

    }

    return ans;

}

int main()

{

        int n;

        while(scanf("%d",&n) && n)

        {

            int cost[maxn][maxn];

            memset(cost,,sizeof cost);

            for (int i = ; i < n * (n - ) / ; i++)

            {

                int a, b, l;

                scanf("%d%d%d", &a, &b, &l);

                cost[a-][b-] = l;

                cost[b-][a-] = l;

            }

            int ans = Prime(cost, n);

            printf("%d\n", ans);

        }

}

N - 畅通工程再续 HDU - 1875

题意：岛之间造桥，只有长度在10～1000才可以造，问最少的花费，花费是桥的长度*100

题解：INF值的判定，INF是长度小于10或者长度大于1000，其余就是Prime的板子

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

#include<sstream>

#include<cmath>

#include<stack>

#include<cstdlib>

#include <vector>

#include <set>

#include<queue>

#include<map>

using namespace std;

#define ll long long

#define llu unsigned long long

#define INF 99999999999.9

#define PI acos(-1.0)

const int maxn =  ;

const ll mod = 1e9+;

const double eps = 1e-;

double lowc[maxn];

bool vis[maxn];

double dis(int x1,int y1,int x2,int y2)

{

    double ans = sqrt((double)(x2-x1)*(x2-x1)*1.0 + (y2-y1)*(y2-y1)*1.0);

    //cout<<ans<<endl;

    return ans;

}

bool check(double x)

{

    //cout<<x<<endl;

    if(x>=10.0 && x<=1000.0)

        return true;

    else

        return false;

}

double Prime(double cost[][maxn],int n)

{

    double ans = ;

    memset(vis,false,sizeof vis);

    vis[] = true;

    for(int i=;i<n;i++)

        lowc[i] = cost[][i];

    for(int i=;i<n;i++)

    {

        double minc = INF;

        int p = -;

        for(int j=;j<n;j++)

        {

            if(!vis[j] && minc > lowc[j])

            {

                minc = lowc[j];

                p = j;

            }

        }

        if(minc == INF)

            return -;

        ans += minc;

        vis[p] = true;

        for(int j=;j<n;j++)

            if(!vis[j] && lowc[j] > cost[p][j])

                lowc[j] = cost[p][j];

    }

    return ans;

}

int main()

{

    int t;

    scanf("%d",&t);

    while(t--)

    {

        int n;

        scanf("%d",&n);

        int x[maxn];

        int y[maxn];

        double cost[maxn][maxn];

        for(int i=;i<n;i++)

            scanf("%d %d",&x[i],&y[i]);

        for(int i=;i<n;i++)

        {

            for(int j=;j<n;j++)

            {

                if(i == j) {

                    cost[i][j] = ;

                    continue;

                }

                else if(check(dis(x[i],y[i],x[j],y[j]))) {

                    //cout<<dis(x[i], y[i], x[j], y[j])<<endl;

                    cost[i][j] = dis(x[i], y[i], x[j], y[j]);

                    cost[j][i] = dis(x[i], y[i], x[j], y[j]);

                }

                else if(!check(dis(x[i],y[i],x[j],y[j])))

                    cost[i][j] = INF;

            }

        }

        //cout<<cost[0][1]<<endl;

        double ans = Prime(cost,n);

        if(ans == -)

            puts("oh!");

        else

            printf("%.1f\n",ans * );

    }

}