hdu 1102 Constructing Roads

1. 题目链接

2. 给你一个含有n*n个元素的矩阵，如果当前元素为0则代表此边不连通，如果当前元素不为0则代表此边的权值为当前元素的值。再给你Q条已经连通的边，让你选择其中的一些边使的能够让这n个顶点都可以直接或间接的连通。问达到这个条件最少需要花费的费用为多少。

3. 就很简单的一个最小生成树，稍微一个不同的地方就是一些边已经是给过的，但是不难想出，只要把它已经给过的边先合并，用kruskal就很好的解决了。但是这个题唯一的坑点就是，题目没说清楚是多组还是一组测试数据，如果知道用多组，记得初始化，还有记得把vector清空就好了。
4. AC code:

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
const int N=1e2+6;
struct node{
    int u,v,w;
    friend bool operator<(node a,node b){return a.w<b.w;}
};
int fa[N],a[N][N],n,m,ans;vector<node>e;
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
void kruskal(){
    sort(e.begin(),e.end());
    for(int i=1;i<=n;i++)fa[i]=i;
    for(int i=1;i<=m;i++){
        int x,y;cin>>x>>y;
        if(find(x)==find(y))continue; 
        fa[find(x)]=find(y);
    }
    for(int i=0;i<e.size();i++){
        int p=e[i].u,q=e[i].v;
        if(find(p)==find(q))continue;
        fa[find(p)]=find(q);
        ans+=e[i].w;
    }
    cout<<ans<<endl;
}
int main(){
    ios::sync_with_stdio(false);cin.tie(0);
    while(cin>>n){
        ans=0;
        for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)cin>>a[i][j];
        for(int i=1;i<=n;i++)for(int j=i+1;j<=n;j++)
        if(a[i][j]){
            node b;b.u=i;b.v=j;b.w=a[i][j];
            e.push_back(b);
        }
        cin>>m;kruskal();
        e.clear();
    }   
}