继续畅通工程

Kruskall求最小生成树的改版，题目已经提前提供了一些边

import java.util.Scanner;
import java.util.Arrays;
import java.util.Comparator;

class edge{
    private int u;
    private int v;
    private int w;
    
    public edge(int u, int v, int w) {
        this.u = u;
        this.v = v;
        this.w = w;
    }
    public int getU() {
        return u;
    }
    public int getV() {
        return v;
    }
    public int getW() {
        return w;
    }
    public void setW(int w){
        this.w = w;
    }
}
public class Main {
    static int f[] = new int[100];
    public static void main(String[] args) {
        Scanner input=new Scanner(System.in);
        int n = input.nextInt();    //顶点数
        int m = n*(n-1)/2;    //边数
        edge e[] = new edge[m];
        for(int i=0;i<m;i++){
            int u = input.nextInt();
            int v = input.nextInt();
            int w = input.nextInt();
            e[i] = new edge(u,v,w);
            int status = input.nextInt();
            if(status == 1){
                e[i].setW(0);
            }
        }
        //按边的权值从小到大排序
        Arrays.sort(e, new Comparator<edge>(){
            public int compare(edge o1, edge o2) {
                if(o1.getW()>o2.getW()){
                    return 1;
                }else if(o1.getW()<o2.getW()){
                    return -1;
                }else{
                    return 0;
                }
            }
        });
        //并查集初始化，数组里存的是自己数组的下标编号
        for(int i=0;i<n;i++){
            f[i] = i;
        }
        //Kruskal算法核心部分
        int count = 0,sum = 0;
        for(int i=0;i<m;i++){        //从小到大枚举每一条边
            if(merge(e[i].getU(),e[i].getV())){        //判断两个点是否联通，不连通则用这条边
                count++;
                sum += e[i].getW();
            }
            if(count == n-1){
                break;
            }
        }
        System.out.println(sum);
    }
    //并查集合并两个子集合
    public static boolean merge(int u,int v){
        int t1 = getf(u);
        int t2 = getf(v);
        if(t1 != t2){    //判断两个点是否在同一个集合中
            f[t2] = t1;
            return true;
        }
        return false;
    }
    //并查集寻找祖先
    public static int getf(int v){
        if(f[v]==v){
            return v;
        }else{
            f[v] = getf(f[v]);        //路径压缩
            return f[v];
        }
    }
}

/**
这题使用了并查集的思想，造了最小生成树，因为事先按花费排序，所以这棵树一旦生成，就是代价最小
**/
#include<iostream>
#include<string.h>
#include<queue>
#include<algorithm>
using namespace std;
int tree[101];
int findroot(int x) {
    if (tree[x] == -1)
        return x;
    else {
        int tmp = findroot(tree[x]);
        tree[x] = tmp;
        return tmp;
    }
}
struct e{
    int l,r,fee;
     bool operator<(const e &a) const {
       return fee < a.fee;
    }
} e[5000];
int main() {
    int n=0;

    int left,right,fee,status;
    while(cin >>n && n) {

        for (int i = 1; i <= n * (n - 1) / 2; ++i){
             cin>>left>>right>>fee>>status;
        if(status == 1) {
            e[i].l = left;
            e[i].r = right;
            e[i].fee = 0;
        } else {
           e[i].l = left;
           e[i].r = right;
           e[i].fee = fee;
        }
        }
        sort(e + 1, e + 1 + n * (n - 1) / 2);
        for (int i = 1; i <= n; ++i)
            tree[i] = -1;

        int ans = 0;
        for (int i = 1; i <= n * (n - 1) / 2; ++i) {
            int a = findroot(e[i].l);
            int b = findroot(e[i].r);
            if (a != b) {
                tree[a] = b;
                ans += e[i].fee;
            }
        }

        cout<<ans<<endl;
    }


}

	

/*
*
*克鲁斯卡尔最小生成树，重点是边的排序，这里是否建立优先，其次是花费(能不花就不花)。
*但是，是否已经建立的情况下，花费的排序就多余了，可以再增加一个距离(花费优先)。
*/

#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e4;
struct edge
{
    int u, v, f, w;
    edge(int _u=0,int _v=0,int _w=0,int _f=0):u(_u),v(_v),w(_w),f(_f){}
};
vector<edge> edges;      //边集
int father[maxn+5];      //并查集表征连通分量
int n, m;

bool cmp(edge a, edge b)   //当然是能不花钱就不花钱  但是貌似f==1时，w的大小比较没啥用(可以再增加一个距离,花费优先)
{
    if(a.f == b.f) return a.w < b.w;
    else return a.f > b.f;
}

void Initial()   //初始化并查集
{
    for(int i = 1;i <= n; i++) father[i] = i;
}

int getFather(int x)   //找根
{
    int a = x;
    while(x != father[x]) x = father[x];
    //路径压缩
    while(a != father[a])
    {
        int z = a; a = father[a]; father[z] = x;
    }
    return x;
}

void Create()    //建图
{
    int u, v, w, f;
    for(int i = 0;i < m; i++)
    {
        cin >> u >> v >> w >> f;
        edges.push_back(edge(u, v, w, f));
    }
}

int Kruskal()     //克鲁斯卡尔
{
    Initial();
    sort(edges.begin(), edges.end(), cmp);
    int ans = 0, num = 0;
    for(int i = 0;i < edges.size(); i++)
    {
        int fu = getFather(edges[i].u);
        int fv = getFather(edges[i].v);
        if(fu != fv)     //u  和  v  不连通则连通   如果连通相连就会形成环(×) 
        {
            father[fu] = fv;
            ans += edges[i].f ? 0 : edges[i].w; num++;
            if(num == n-1) break;
        }
    }
    //if(num != n-1) return -1;   //图非连通 
    return ans;
}

int main()
{
    ios::sync_with_stdio(false);    
    while(cin >> n && n)
    {
        m = n*(n-1)/2;
        Create();
        int ans = Kruskal();
        //if(ans == -1) cout << "Error" << '\n';   //图非连通
        cout << ans << '\n';
    }
    return 0;
}

#include<iostream>
#include<vector>
#include<map>
#include<algorithm>
using namespace std;
struct edge
{
	int start, end, cost, built;
	edge(int s, int e, int c, int b) :start(s), end(e), cost(c), built(b) {};
};

int find_root(map<int, int>& V, int x)//查找x所在集合的根
{
	if (V.find(x) != V.end() && V[x] != x)
		V[x] = find_root(V, V[x]);//递归进行路径压缩
	else
		return x;
	return V[x];
}

int kruskal(vector<edge>& E, int n)
{
	int cost = 0, count = 0;
	map<int, int> V;
	vector<edge>::iterator it = E.begin();
	while (count != n - 1)
	{
		while (it != E.end())
		{			
			int a = find_root(V, it->start);
			int b = find_root(V, it->end);
			//注意要保证不在集合内，因为可能已建成的形成了环路
			if (a != b)
			{
				if (it->built == 1)
				{
					V[b] = a;
					it++;
					break;
				}
				else
				{
					V[b] = a;
					cost += it->cost;
					it++;
					break;
				}
			}
			else
				it++;
		}
		count++;
	}
	return cost;
}
bool comp(edge e1, edge e2)//排序函数
{
	if (e1.built == e2.built)
		return e1.cost < e2.cost;
	else
		return e1.built > e2.built;
}
int main()
{
	int n;
	vector<edge> E;
	while (cin>>n && n != 0)
	{
		int edge_num = n * (n - 1) / 2;
		for (int i = 0; i < edge_num; i++)
		{
			int s, e, c, b;
			cin >> s >> e >> c >> b;
			E.push_back(edge(s, e, c, b));
		}
		sort(E.begin(), E.end(), comp);
		cout << kruskal(E, n) << endl;
		E.clear();
	}
	return 0;
}

#include<iostream>//并查集思想，此题有考虑到MST不存在的情况，要自己构造
#include<cmath>//先将flag=1的节点加入到集合中
#include<algorithm>
#include<iomanip>
using namespace std;
#define N 101
int tree[N];//保存各个节点的根节点
struct e//结构体保存两个节点之间的cost(距离，时间，建路建桥花费之类的)
{
	int a, b;
	int cost;
	bool flag;//此题有标志，1表示已修了路，0表示没修
	bool operator<(const e& s)const//重载<号
	{
		if (flag != s.flag)//flag=1的排在最前面，以便等下遍历的时候，把已经修了路的节点先放入一个集合中
			return flag > s.flag;
		else
		{
			if (cost != s.cost)//flag=0时，按照修路花费最少的排在前面
				return cost < s.cost;
			else//这个随便 你a小排前还是b小排前不影响
				return  a < s.a;
		}
	}
}edg[5500];
int findroot(int x)//找各个节点所在树的根节点
{
	if (tree[x] == -1)return x;//找到根节点，输出根节点
	else//路径压缩，比如1-2-3，3的祖先节点是2，进行路径压缩，递归查找2的祖先节点=1，
	{	//将3的祖先节点设为1，即1-2，1-3，此时1-3这条边的权值=以前2-3的权值，其实只是移动了边；
		int tmp = findroot(tree[x]);
		tree[x] = tmp;
		return tmp;
	}
}
int main()
{
	int n;
	while (cin >> n && n != 0)
	{
		for (int i = 1; i <= n; i++)//一开始的节点都是单独的连通分量
			tree[i] = -1;
		for (int i = 1; i <= n * (n - 1) / 2; i++)//输入数据
			cin >> edg[i].a >> edg[i].b >> edg[i].cost >> edg[i].flag;
		sort(edg + 1, edg + 1 + n * (n - 1) / 2);//排序
		int ans = 0;
		for (int i = 1; i <= n * (n - 1) / 2; i++)
		{
				int a = findroot(edg[i].a);//查找两个点的根节点
				int b = findroot(edg[i].b);
				if (a != b)//a!=b，说明两点不是在同一棵树上，要将其合并成同一个集合
				{
					tree[a] = b;// 将其合并成同一个集合，一棵树变成另一棵树根节点的子树
					if (edg[i].flag != 1)//判断，如果flag=1,则路已修不用再花费，反之，flag=0,要修路ans+=edg[i].cost,因为当flag=0时，我们的
						//edg数组是按cost的升序排列的，所以先修花费小的路,
					{
						ans += edg[i].cost;
					}
				}
		}//当所有的节点都在一棵树的时候，ans保持不变，直至循环退出，ans即为最小花费
		cout << ans << endl;
	}
	return 0;
}

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

const int maxn=10005;
int root[maxn];
struct edge
{
	int a,b,w,flag;
}r[maxn];
bool cmp(edge a,edge b)
{
	return a.w<b.w;
}
int getroot(int x)
{
	if(x!=root[x])
		root[x]=getroot(root[x]);
	return root[x];
}
int kruskal(int m)
{
	int ans=0;
	for(int i=0;i<maxn;++i)		root[i]=i;
	sort(r,r+m,cmp);
	for(int i=0;i<m;++i)
	{
		int ra=getroot(r[i].a), rb=getroot(r[i].b);
		if(ra!=rb)
		{
			root[ra]=rb;
			ans+=r[i].w;
		}
	}
	return ans;
}
int main()
{
	int n;
	while (cin>>n&&n)
	{
		int m=n*(n-1)/2;
		for(int i=0;i<m;++i)
		{
			cin>>r[i].a>>r[i].b>>r[i].w>>r[i].flag;
			if(r[i].flag)	r[i].w=0;			  //已修的路权值视为0
		}
		cout<<kruskal(m)<<endl;
	}
	return 0;
}

在输入时就对已建好的路进行树的生成，且不保存，而后只保存未开始修建的路，然后进行排序和树的继续生成。

def findRoot(village):
    global villages
    if villages[village] == -1:
        return village
    else:
        temp = findRoot(villages[village])
        villages[village] = temp
        return temp
while True:
    try:
        n = int(input())
        if n == 0:
            break
        villages = [-1 for i in range(n+1)]
        nodeNum = 1
        roads = []
        for i in range(n*(n-1)//2):
            temp = list(map(int, input().split()))
            if temp[3] == 1:
                a = findRoot(temp[0])
                b = findRoot(temp[1])
                if a != b:
                    villages[a] = b
                    nodeNum += 1
            else:
                roads.append(temp)
        costs = 0
        roads.sort(key=lambda x:x[2])
        for i in range(len(roads)):
            a = findRoot(roads[i][0])
            b = findRoot(roads[i][1])
            if a != b:
                villages[a] = b
                costs += roads[i][2]
                nodeNum += 1
            if nodeNum == n:
                break
        print(costs)
    except Exception:
        break

#include<stdio.h>
#include<algorithm>
#define N 100
using namespace std;
typedef struct Edge{
    int a,b;
    int cost;
    int flag;
}Edge;
int Tree[N];
int FindRoot(int x){
    if(Tree[x]==-1) return x;
    else{
        Tree[x]=FindRoot(Tree[x]);
        return Tree[x];
    }
}
bool cmp(Edge a,Edge b){
    if(a.flag!=b.flag)
        return a.flag>b.flag;
    else
        return a.cost<b.cost;
}
int main(){
    int n;
    while(scanf("%d",&n)!=EOF&&n!=0){
        Edge e[N*(N-1)/2];
        int i;
        for(i=1;i<=n;i++)
            Tree[i]=-1;
        for(i=0;i<n*(n-1)/2;i++)
            scanf("%d%d%d%d",&e[i].a,&e[i].b,&e[i].cost,&e[i].flag);
        sort(e,e+n*(n-1)/2,cmp);
        int ans=0;
        int a,b;
        for(i=0;i<n*(n-1)/2;i++){
            a=FindRoot(e[i].a);
            b=FindRoot(e[i].b);
            if(a!=b){
                Tree[b]=a;
                if(e[i].flag==0)
                    ans+=e[i].cost;
            }
        }
        printf("%d\n",ans); 
    }
    return 0;
}

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int MAX = 101;
struct Edge{
    int from;
    int to;
    int cost;
    bool operator< (const Edge a) const {
        return cost < a.cost;
    }
};
int father[MAX];
int height[MAX];
vector<Edge> edge0, edge1;
void Initial(){
    for(int i=0; i<MAX; ++i){
        father[i] = i;
        height[i] = 0;
    }
    return;
}
int Find(int x){
    if(x!=father[x]) return Find(father[x]);
    else return x;
}
void Union(int x, int y){
    x = Find(x);
    y = Find(y);
    if(x != y){
        if(height[x] > height[y]){
            father[y] = x;
        }else if(height[x] < height[y]){
            father[x] = y;
        }else{
            father[x] = y;
            height[y]++;
        }
    }
    return;
}
int main(){
    int n;
    while (cin >> n && n!=0){
        Initial();
        int edgenum = n*(n-1)/2;
        for(int i=0; i<edgenum; ++i){
            Edge temp;
            int status;
            cin >> temp.from >> temp.to >> temp.cost >> status;
            if(status == 0) edge0.push_back(temp);
            else edge1.push_back(temp);
        }
        sort(edge0.begin(), edge0.end());
        int ans = 0;
        for(int i=0; i<edge1.size(); ++i){
            if(Find(edge1[i].from) != Find(edge1[i].to)) Union(edge1[i].from, edge1[i].to);
        }
        for(int i=0; i<edge0.size(); ++i){
            if(Find(edge0[i].from) != Find(edge0[i].to)){
                Union(edge0[i].from, edge0[i].to);
                ans+=edge0[i].cost;
            }
        }
        cout << ans << endl;
    }
}

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
const int MAX = 101;
struct Edge{
    int from;
    int to;
    int cost;
    bool operator< (const Edge a) const {
        return cost < a.cost;
    }
};
int father[MAX];
int height[MAX];
vector<Edge> edge0, edge1;
void Initial(){
    for(int i=0; i<MAX; ++i){
        father[i] = i;
        height[i] = 0;
    }
    return;
}
int Find(int x){
    if(x!=father[x]) return Find(father[x]);
    else return x;
}
void Union(int x, int y){
    x = Find(x);
    y = Find(y);
    if(x != y){
        if(height[x] > height[y]){
            father[y] = x;
        }else if(height[x] < height[y]){
            father[x] = y;
        }else{
            father[x] = y;
            height[y]++;
        }
    }
    return;
}
int main(){
    int n;
    while (cin >> n && n!=0){
        Initial();
        int edgenum = n*(n-1)/2;
        for(int i=0; i<edgenum; ++i){
            Edge temp;
            int status;
            cin >> temp.from >> temp.to >> temp.cost >> status;
            if(status == 0) edge0.push_back(temp);
            else edge1.push_back(temp);
        }
        sort(edge0.begin(), edge0.end());
        int ans = 0;
        for(int i=0; i<edge1.size(); ++i){
            if(Find(edge1[i].from) != Find(edge1[i].to)) Union(edge1[i].from, edge1[i].to);
        }
        for(int i=0; i<edge0.size(); ++i){
            if(Find(edge0[i].from) != Find(edge0[i].to)){
                Union(edge0[i].from, edge0[i].to);
                ans+=edge0[i].cost;
            }
        }
        cout << ans << endl;
    }
}

#include <stdio.h>
#include <stdlib.h>

struct Edge {
    int from;
    int to;
    int cost;
    int build;
};

int father[100];
struct Edge e[100 * 100];
int height[100];

void initial(int n) {
    for (int i = 1; i <= n; i++) {
        father[i] = i;
        height[i] = 0;
    }
}



int Find(int x) {
    if (x != father[x]) {
        father[x] = Find(father[x]);
    }
    return father[x];
}

void Union(int a, int b) {
    a = Find(a);
    b = Find(b);
    if (a != b) {
        if (height[a] < height[b])
            father[a] = b;
        else if (height[a] > height[b])
            father[b] = a;
        else {
            father[a] = b;
            height[b]++;
        }
    }
}

int cmp(const void* a, const void* b) {
    const struct Edge* a1 = (const struct Edge*)a;
    const struct Edge* b1 = (const struct Edge*)b;
    if (a1->cost > b1->cost)
        return 1;
    if (a1->cost < b1->cost)
        return -1;
    return 0;
}

void initialF(struct Edge e[], int m){
    for(int i = 0; i < m; i++){
        if (e[i].build == 1){
            Union(e[i].from, e[i].to);
        }
    }
}

int KrusKal(struct Edge e[], int m) {
    initialF(e, m);
    int ans = 0;
    qsort(e, m, sizeof(struct Edge), cmp);
    for (int i = 0; i < m; i++) {
        if (Find(e[i].to) != Find(e[i].from) && e[i].build == 0) {
            Union(e[i].to, e[i].from);
            ans += e[i].cost;
        }
    }
    return ans;
}

int main() {
    int n, m, count = 0, f, t, c, bui;
    while (scanf("%d", &n) != EOF) {
        if (n == 0) {
            break;
        }
        initial(n);
        m = n * (n - 1) / 2;
        for (int i = 0; i < m; i++) {
            scanf("%d %d %d %d", &f, &t, &c, &bui);
            e[i].to = t;
            e[i].from = f;
            e[i].cost = c;
            e[i].build = bui; // 初始化build值
        }
        // for (int i = 0; i < m; i++){
        //     printf("%d", e[i].build);
        // }
        int res = KrusKal(e, m);
        printf("%d\n", res);
    }
    return 0;
}

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

const int MAXN = 100;

struct Edge {
    int from;   //边的起点
    int to;     //边的终点
    int length; //边的长度
    bool operator<(const Edge& e)const {    //重载小于号
        return length < e.length;
    }
};

vector<Edge>edge(MAXN* MAXN);   //边集
vector<int>father(MAXN);        //父亲结点
vector<int>height(MAXN);        //结点高度

void Initial(int n) {               //初始化
    for (int i = 0; i <= n; i++) {
        father[i] = i;
        height[i] = 0;
    }
}

int Find(int x) {                       //查找根结点
    if (x != father[x]) {               //路径压缩
        father[x] = Find(father[x]);
    }
    return father[x];
}

void Union(int x, int y) {              //合并集合
    x = Find(x);
    y = Find(y);
    if (x != y) {
        //矮树作为高树的子树
        if (height[x] < height[y]) {
            father[x] = y;
        } else if (height[y] < height[x]) {
            father[y] = x;
        } else {
            father[y] = x;
            height[x]++;
        }
    }
}

int Kruskal(int n, int edgeNum) {   //最小生成树的克鲁斯卡尔算法
    Initial(n);
    sort(edge.begin(), edge.begin() + edgeNum); //边按权值排序
    int sum = 0;
    for (int i = 0; i < edgeNum; i++) {
        Edge current = edge[i];
        if (Find(current.from) != Find(current.to)) {
            Union(current.from, current.to);
            sum += current.length;
        }
    }
    return sum; //返回最小总长度
}

int main() {
    int n;
    while (cin >> n && n != 0) {
        Initial(n);
        int edgeNum = n * (n - 1) / 2;
        for (int i = 0; i < edgeNum; i++) {
            int status; //修建状态
            cin >> edge[i].from >> edge[i].to >> edge[i].length >> status;
            if (status == 1) {
                edge[i].length = 0;
            }
        }
        int answer = Kruskal(n, edgeNum);
        cout << answer << endl;
    }
    return 0;
}