HDU1233 还是畅通工程（最小生成树）

March 30, 2016

题目链接

今天正式开始搞图论了。

MST 裸题，prim 搞的。

#include<cstring>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;

const int INF = 0x3f3f3f3f;
const int MAXN = 110;
bool vis[MAXN];
int lowc[MAXN];
int cost[MAXN][MAXN];
int Prim(int cost[][MAXN], int n){
    int ans = 0;
    memset(vis, false, sizeof(vis));
    vis[0] = true;
    for(int i = 1; i < n; i++)
        lowc[i] = cost[0][i];
    for(int i = 1; i < n; i++){
        int minc = INF;
        int p = -1;
        for(int j = 0; j < n; j++){
            if(!vis[j] && minc>lowc[j]){
                minc = lowc[j];
                p = j;
            }
        }
        if(minc == INF) return -1;
        ans += minc;
        vis[p] = true;
        for(int j = 0; j < n; j++){
            if(!vis[j] && lowc[j]>cost[p][j])
                lowc[j] = cost[p][j];
        }

    }
    return ans;
}

int main(){
//    freopen("a.txt", "r", stdin);
    int n;
    while(scanf("%d", &n) && n){
        memset(cost, 0x3f, sizeof(cost));
        int a, b, c;
        for(int i = 1; i <= n*(n-1)/2; i++){
            scanf("%d %d %d", &a, &b, &c);
            a--; b--;
            cost[a][b] = cost[b][a] = c;
        }
        cout << Prim(cost, n) << endl;
    }
    return 0;
}

Kruskal:

#include<cstring>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<vector>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;

const int MAXN = 110;   //最大点数
const int MAXM = 10000; //最大边数
int F[MAXN];    //并查集使用
struct Edge{
    int u, v, w;
}edge[MAXM];    //存储边的信息，包括起点/终点/权值
int tol;    //边数，加边前赋值为0
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 findfa(int x){
    if(F[x] == -1)return x;
    else return F[x] = findfa(F[x]);
}
int Kruskal(int n){ //传入点数，返回最小生成树的权值，如果不连通返回-1
    memset(F, -1, sizeof(F));
    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 = findfa(u);
        int t2 = findfa(v);
        if(t1 != t2){
            ans += w;
            F[t1] = t2;
            cnt++;
        }
        if(cnt == n-1)break;
}
    if(cnt < n-1)return -1;//不连通
    else return ans;
}


int main(){
    //freopen("a.txt", "r", stdin);
    int n;
    while(~scanf("%d", &n) && n){
        int k = n*(n-1)/2;
        for(tol = 0; tol < k; ){
            int a, b, c;
            scanf("%d %d %d", &a, &b, &c);
            addedge(a, b, c);
        }
        cout << Kruskal(n) << endl;
    }
    return 0;
}