继续畅通工程

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 <cstdio>
#include <iostream>
#include<vector>
#include<algorithm>
using namespace std;
int father[10001];
void InitSet(int n) {
    for (int i = 0; i < n; i++) {
        father[i] = i;
    }
}
int FindFather(int u) {
    if (u == father[u]) {
        return u;
    } else {
        father[u] = FindFather(father[u]);
        return father[u];
    }
}
void UnionSet(int r, int t) {
    r = FindFather(r);
    t = FindFather(t);
    father[r] = t;
}
struct edge {
    int u;//边的两个结点、权值
    int v;
    int w;
    int live;//表示是否修建
    edge(int _u, int _v, int _w, int _live) {
        u = _u;
        v = _v;
        w = _w;
        live = _live;
    }
};
bool cmp(edge a, edge b) {
    if (a.live != b.live) {
        return a.live >
               b.live; //不花费钱的优先级最高先加入到并查集，从小到大最小生成树
    } else {
        return a.w < b.w;
    }
}
int main() {
    int n;
    while (scanf("%d", &n) != EOF) {
        vector<edge> edgev;//存储边的向量
        if (0 == n) {
            break;
        }
        for (int i = 0; i < (n - 1)*n / 2; i++) {
            int u, v, w, live;
            scanf("%d %d %d %d", &u, &v, &w, &live);
            edge e(u, v, w, live);
            edgev.push_back(e);
        }
        InitSet(10001);
        sort(edgev.begin(), edgev.end(), cmp);
        int edgenum = 0, totaledgesum = 0; //边的数量与权值之和
        for (int i = 0; i < edgev.size(); i++) {
            int u = edgev[i].u, v = edgev[i].v, w = edgev[i].w, live = edgev[i].live;
            if (1 == live) {
                if (FindFather(u) != FindFather(v)) {
                    edgenum++; //只有不在同一个并查集的已有路才算边
                }
                UnionSet(u, v);
            } else {
                if (FindFather(u) != FindFather(v)) {
                    edgenum++;
                    UnionSet(u, v);
                    totaledgesum += w;
                }
            }
            if (edgenum == n - 1) { //最小树已经生成完毕
                break;
            }
        }
        printf("%d\n", totaledgesum);

    }
}
// 64 位输出请用 printf("%lld")

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <vector>

using namespace std;

const int MAXN = 100;

struct Edge {
    int form;
    int to;
    int length;
};

int father[MAXN];
int height[MAXN];
vector<Edge> edge1(MAXN* MAXN);

bool operator < (Edge lhs, Edge rhs) {
    return lhs.length < rhs.length;
}

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

int Find(int u) {
    if (father[u] == u) {
        return u;
    } else {
        father[u] = Find(father[u]);
    }
    return father[u];
}

void Union(int u, int v) {
    int uroot = Find(u);
    int vroot = Find(v);
    if (uroot != vroot) {
        if (height[u] < height[v]) {
            father[uroot] = vroot;
        } else if (height[u] > height[v]) {
            father[vroot] = uroot;
        } else {
            father[vroot] = uroot;
            height[u]++;
        }
    }
}

int Kruskal(int n, int edgeNumber) {
    Init(n);
    sort(edge1.begin(), edge1.begin() + edgeNumber);
    int sum = 0;
    for (int i = 0; i < edgeNumber; ++i) {
        Edge current = edge1[i];
        if (Find(current.form) != Find(current.to)) {
            Union(current.form, current.to);
            sum += current.length;
        }
    }
    return sum;
}

int main() {
    int n;
    while (cin >> n) {
        if (n == 0) {
            break;
        }
        int edgeNumber = n * (n - 1) / 2;
        int statue;
        for (int i = 0; i < edgeNumber; ++i) {
            cin >> edge1[i].form >> edge1[i].to >> edge1[i].length >> statue;
            if (statue == 1) {
                edge1[i].length = 0;
            }
        }
        int sum = Kruskal(n, edgeNumber);
        cout << sum << endl;
    }
    return 0;
}

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
struct road{
	int townA;
	int townB;
	int cost;
	bool build;
};
bool compare(road lhs,road rhs){
	return lhs.cost<rhs.cost;
}
int findset(vector<int> &vec,int a){
	while(vec[vec[a]]!=vec[a]){//路径压缩，如果a父亲不是根结点，则无限循环直到找到根结点
		vec[a]=vec[vec[a]];
	}
	return vec[a];
}
void unionset(vector<int> &vec, int a, int b) {
    int rootA = findset(vec, a);
    int rootB = findset(vec, b);
    if (rootA != rootB) {
        vec[rootA] = rootB;
    }
}
int main(){
	int n;//n表示村庄数目
	while(cin >> n && n!=0){
		vector<road> vec(n*(n-1)/2+1);//存放道路情况
		for(int i=1;i<=(n*(n-1)/2);i++){//输入道路情况
			cin >> vec[i].townA >> vec[i].townB >> vec[i].cost >> vec[i].build;
		}
		vector<int> connected_set(n+1);//并查集
		for(int i=1;i<=n;i++){
			connected_set[i]=i;//初始化，每个集合元素的父结点都是自己
		}
		//kruskal算法
		sort(vec.begin()+1,vec.end(),compare);//把所有道路按照从小到大排序
		for(int i=1;i<=n*(n-1)/2;i++){
			if(vec[i].build==true){//将已有道路的连接到并查集
				unionset(connected_set,vec[i].townA,vec[i].townB);
			}
		}
		int need=-1;//还需修建need条路
		for(int i=1;i<=n;i++){
			if(findset(connected_set,i)==i){
				need++;
			}
		}
		int money=0;
		for(int i=1;i<=n*(n-1)/2 && need>0;i++){
			//如果没有修建过且未连通，则修建
			if(!vec[i].build && (findset(connected_set,vec[i].townA)!=findset(connected_set,vec[i].townB))){
				vec[i].build=true;
				unionset(connected_set,vec[i].townA,vec[i].townB);
				money+=vec[i].cost;
				need--;
			}
		}
		cout << money << endl;
	}
}

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
int village[100];
struct edge{
    int start;
    int end;
    int fare;
    int flag;
};
void Initset(int n){
     for(int i=0;i<n;i++){
         village[i]=i;
     }
}
bool compare(edge lhs,edge rhs){
    if(lhs.flag>rhs.flag){
        return true;
    }
    else if(lhs.flag==rhs.flag&&(lhs.fare<rhs.fare)){
        return true;
    }
    else return false;
}
int findfather(int n){
    if(village[n]==n){
        return n;
    }
    else return findfather(village[n]);
}
int main(){
    int n;
    while(cin>>n) {
        if(n==0){
            break;
        }
        vector<edge> v(n * (n - 1 / 2));
//        int village[n];
        Initset(n + 1);//初始化并查集
        for (int i = 0; i < n * (n - 1) / 2; i++) {
            cin >> v[i].start >> v[i].end >> v[i].fare >> v[i].flag;
        }
        sort(v.begin(), v.end(), compare);
        vector<edge>::iterator it;
        int weight = 0;
        int setnode = n;
        for (it = v.begin(); it != v.end(); it++) {
            int a = (*it).start;
            int b = (*it).end;
            int aroot = findfather(a);
            int broot = findfather(b);
            if (aroot != broot) {
                village[broot] = aroot;
                setnode--;
                if ((*it).flag == 0) {
                    weight += (*it).fare;
                }
                if (setnode == 1) {
                    break;
                }
            }
        }
        cout << weight << endl;
    }
    return 0;
}