POJ 2421 最小生成树

简介:

题意:给出每两个城市间建路的花费和已经拥有的路,求最小花费让图连通。

最小生成树。。

#include <iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxv=105,maxe=10005;
struct node
{
    int w,to,next,f;
} e[maxe];
int head[maxv],dis[maxv],p[maxv],edge,n;

void add(int u,int v,int c)
{
    e[edge].f=v,e[edge].to=u,e[edge].w=c,e[edge].next=head[u],head[u]=edge++;
}
int cmp(node a,node b)
{
    return a.w<b.w;
}
int find(int x)
{
    return p[x]==x?x:p[x]=find(p[x]);
}
int kru()
{
    int ans=0;
    for(int i=0; i<n; i++) p[i]=i;
    sort(e,e+edge,cmp);
    for(int i=0; i<edge; i++)
    {
        int x=find(e[i].f),y=find(e[i].to);
        if(x!=y)ans+=e[i].w,p[x]=y;
    }
    return ans;
}
int main()
{
    int q,val;
    while(~scanf("%d",&n))
    {
        edge=0;
        for(int i=0; i<n; i++)
            for(int j=0; j<n; j++)
            {
                scanf("%d",&val);
                if(i!=j)
                    add(i,j,val);
            }
        scanf("%d",&q);
        for(int i=0; i<q; i++)
        {
            int u,v;
            scanf("%d%d",&u,&v);
            for(int j=0; j<edge; j++)
                if((e[j].f==u-1&&e[j].to==v-1)||(e[j].f==v-1&&e[j].to==u-1))
                    e[j].w=0;
        }
        printf("%d\n",kru());
    }
    return 0;
}


目录
相关文章
|
存储 算法 C++
对最小生成树的认识及模板题
一周前对 树 这个词从新认识了一下,之前一直有听说过,但是很显然,仅仅是听说。。
对最小生成树的认识及模板题
|
算法 机器学习/深度学习
并查集-poj-1182
poj-1182-食物链 //2014.4.11 HDOJ携程编程大赛预赛第二场第一题 Description 动物王国中有三类动物A,B,C,这三类动物的食物链构成了有趣的环形。A吃B, B吃C,C吃A。  现有N个动物,以1-N编号。每个动物都是A,B,C中的一种,但是我们并不知道它到底是哪一种。  有人用两种说法对这N个动物所构成的食物链关系进行描述:  第一种说法是"1
1039 0