题解 | #还是畅通工程#

还是畅通工程

http://www.nowcoder.com/practice/d6bd75dbb36e410995f8673a6a2e2229

Kruskal

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

const int MAXN = 100;

struct Edge {
    int a;
    int b;
    int weight;
    Edge(int _a, int _b, int _weight) : a(_a), b(_b), weight(_weight) {}
    friend bool operator < (const Edge& e1, const Edge& e2) {
        return e1.weight < e2.weight;  
    }
};

int Find(vector<int>& s, int x) {
    int root = x;
    while (s[root] >= 0) {
        root = s[root];
    }
    while (x != root) {
        int t = s[x];
        s[x] = root;
        x = t;
    }
    return root;
}

void Union(vector<int>& s, int roota, int rootb) {
    if (s[roota] <= s[rootb]) {
        s[roota] += s[rootb];
        s[rootb] = roota;
    }
    else {
        s[rootb] += s[roota];
        s[roota] = rootb;
    }
}

int main() 
{
    int N;
    while (cin >> N) {
        if (N == 0) break;
        vector<Edge> Edges;
        vector<int> s(MAXN,-1);
        int a, b, w;
        int cnt = N*(N-1)/2;
        while (cnt--) {
            cin >> a >> b >> w;   
            Edges.push_back(Edge(a,b,w));
        }
        sort(Edges.begin(), Edges.end());
        int result = 0;
        for (int i = 0; i < Edges.size(); i++) {
            Edge e = Edges[i];
            int roota = Find(s, e.a);
            int rootb = Find(s, e.b);
            if (roota != rootb) {
                result += e.weight;
                Union(s, roota, rootb);
            }
        }
        cout << result << endl;
    }
    return 0;
}

priority_queue + kruskal

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

struct Edge {
	int a;
	int b;
	int weight;
	Edge(int a, int b, int w) : a(a), b(b), weight(w) { }
	friend bool operator < (const Edge& e1, const Edge& e2) {
		return e1.weight > e2.weight;
	}
};

int Find(vector<int>& s, int x) {
	int root = x;
	while (s[root] >= 0) {
		root = s[root];
	}
	while (x != root) {
		int t = s[x];
		s[x] = root;
		x = t;
	}
	return root;
}

void Union(vector<int>& s, int roota, int rootb) {
	if (s[roota] <= s[rootb]) {
		s[roota] += s[rootb];
		s[rootb] = roota;
	}
	else {
		s[rootb] += s[roota];
		s[roota] = rootb;
	}
}

const int MAXN = 100;

int main()
{
	int N;
	while (cin >> N) {
		if (N == 0) break;
		priority_queue<Edge> pq;
		//vector<int> s(N, -1);
        vector<int> s(MAXN, -1);
		int a, b, w;
		int cnt = N * (N - 1) / 2;
		while (cnt--) {
			cin >> a >> b >> w;
			pq.push(Edge(a, b, w));
		}
		int result = 0;
		while (!pq.empty()) {
			Edge e = pq.top();
			pq.pop();
			int roota = Find(s, e.a);
			int rootb = Find(s, e.b);
			if (roota != rootb) {
				result += e.weight;
				Union(s, roota, rootb);
			}
		}
		cout << result << endl;
	}
	return 0;
}

Prim算法邻接矩阵

#include <iostream>
#include <vector>
#include <queue>
#include <limits.h>
using namespace std;

const int MAXN = 100;

int Prim(vector<vector<int>>& G, int s) {
//lowcost数组存储的是一个顶点v到最小生成树集MST中所有顶点的代价最小的值，初始化为cost(s,v)或者正无穷    
    vector<int> lowCost(MAXN, INT_MAX); 
//将图中的顶点分为了两个集合，collected[i] == true, 表示该顶点已经收录于MST中
    vector<bool> collected(MAXN, false);
// s->w  ---- path[w] = s   初始化为源点s
    vector<int> path(MAXN, s);
    collected[s] = true;
    for (int i = 0; i < G[s].size(); i++) {
        if (G[s][i] == 0) continue;
        lowCost[i] = G[s][i];
    }
    int result = 0;
    while (true) {
        int min = INT_MAX;
        int v;
        for (int i = 0; i < MAXN; i++) {
            if (!collected[i] && lowCost[i] < min) {
                min = lowCost[i];
                v = i;
            }
        }
// 1、顶点全部被收录 
// 2、所有没收录的顶点cost都是无穷大，表明剩下的顶点到最小生成树没有边，图不连通
        if (min == INT_MAX) break;
// 将顶点v收录进入最小生成树集合
        collected[v] = true;
        result += G[path[v]][v];
        for (int i = 0; i < G[v].size(); i++) {
            if (G[v][i] == 0 || collected[i]) continue;
            if (G[v][i] < lowCost[i]) {
                lowCost[i] = G[v][i];
                path[i] = v;
            }
        }
    }
    return result;
}

int main() 
{
    int N;
    while (cin >> N) {
        if (N == 0) break;
        int cnt = N*(N-1)/2;
        vector<vector<int>> G(MAXN, vector<int>(MAXN, 0));
        int a, b, w;
        int s;
        bool flag = true;
        while (cnt--) {
            cin >> a >> b >> w;
            if (flag == true) {
                s = a;
                flag = false;
            }
            G[a][b] = w;
            G[b][a] = w;
        }
        int res = Prim(G, s);
        cout << res << endl;
    }
    return 0;
}

Prim算法邻接表

#include <iostream>
#include <vector>
#include <queue>
#include <limits.h>
using namespace std;

const int MAXN = 100;

struct Node {
    int v;     //边的终点编号
    int w;     //边权
    Node(int _v, int _w) : v(_v), w(_w) { }
};

int Prim(vector<vector<Node>>& G, int s) {
//lowcost数组存储的是一个顶点v到最小生成树集MST中所有顶点的代价最小的值，初始化为cost(s,v)或者正无穷    
    vector<int> lowCost(MAXN, INT_MAX); 
//将图中的顶点分为了两个集合，collected[i] == true, 表示该顶点已经收录于MST中
    vector<bool> collected(MAXN, false);
    collected[s] = true;
    for (int i = 0; i < G[s].size(); i++) {
        int v = G[s][i].v;
        int w = G[s][i].w;
        lowCost[v] = w;
    }
    int result = 0;
    while (true) {
        int min = INT_MAX;
        int v;
        for (int i = 0; i < MAXN; i++) {
            if (!collected[i] && lowCost[i] < min) {
                min = lowCost[i];
                v = i;
            }
        }
// 1、顶点全部被收录 
// 2、所有没收录的顶点cost都是无穷大，表明剩下的顶点到最小生成树没有边，图不连通
        if (min == INT_MAX) break;
// 将顶点v收录进入最小生成树集合
        collected[v] = true;
        result += min;
        for (int i = 0; i < G[v].size(); i++) {
            int _w = G[v][i].v;
            if (collected[_w]) continue;
            if (G[v][i].w < lowCost[_w]) {
                lowCost[_w] = G[v][i].w;
            }
        }
    }
    return result;
}

int main() 
{
    int N;
    while (cin >> N) {
        if (N == 0) break;
        int cnt = N*(N-1)/2;
        vector<vector<Node>> Adj(MAXN);
        int a, b, w;
        int s;
        bool flag = true;
        while (cnt--) {
            cin >> a >> b >> w;
            if (flag == true) {
                s = a;
                flag = false;
            }
            Adj[a].push_back(Node(b, w));
            Adj[b].push_back(Node(a, w));
        }
        int res = Prim(Adj, s);
        cout << res << endl;
    }
    return 0;
}

prim 邻接表 priority_queue

#include <iostream>
#include <vector>
#include <queue>
#include <limits.h>
using namespace std;

const int MAXN = 100;

struct Node {
    int v;     //边的终点编号
    int w;     //边权
    Node(int _v, int _w) : v(_v), w(_w) { }
};
struct Edge {
    int a;
    int b;
    int weight;
    Edge(int _a, int _b, int _weight) : a(_a), b(_b), weight(_weight) {}
};
struct cmp {
    bool operator()(const Edge& e1, const Edge& e2) {
        return e1.weight > e2.weight;   //按照value从小到大排列
    }
};

int Prim(vector<vector<Node>>& G, int s) {
    vector<int> lowCost(MAXN, INT_MAX); 
    vector<bool> collected(MAXN, false);
    priority_queue<Edge, vector<Edge>, cmp> pq;
    pq.push(Edge(s,s,0));
    int result = 0;
    while (!pq.empty()) {
        Edge e = pq.top();
        pq.pop();
        if (collected[e.b]) continue;
        collected[e.b] = true;
        result += e.weight;
        for (int i = 0; i < G[e.b].size(); i++) {
            int v = G[e.b][i].v;
            int wgt = G[e.b][i].w;
            if (!collected[v] && wgt < lowCost[v]) {
                lowCost[v] = wgt;
                pq.push(Edge(e.b, v, wgt));
            }
        }
    }
    return result;
}

int main() 
{
    int N;
    while (cin >> N) {
        if (N == 0) break;
        int cnt = N*(N-1)/2;
        vector<vector<Node>> Adj(MAXN);
        int a, b, w;
        int s;
        bool flag = true;
        while (cnt--) {
            cin >> a >> b >> w;
            if (flag == true) {
                s = a;
                flag = false;
            }
            Adj[a].push_back(Node(b, w));
            Adj[b].push_back(Node(a, w));
        }
        int res = Prim(Adj, s);
        cout << res << endl;
    }
    return 0;
}