1001 Battle Over Cities - Hard Version （35 分）

要求：在甲级1013. Battle Over Cities (25)的基础上，图为加权图，路径有好有坏，删掉一个节点，将剩下的节点连接起来，如果不是一个连通分量，则需要找一条最便宜的路径，修好该路将它们连接起来，注意：如果可能原来坏的路都没有，则没法将两个连通分量连接起来，这时费用就为无穷大，最后变为一个连通分量总的花费，如果该点花费最大，则为最应该保护的点，即输出的点。

方法：1）参考博客Bendaai的方法：即求删除每个点后对应的最小生成树，如果生成的树权值最大，则为输出点。首先在最开始读入数据是的操作是：输入的路径如果是好的，则改路径权值设为0，坏的则为该路的费用。则后面求最小生成树时，好的路径对花费没有影响。不得不说博主真聪明。

代码：

#include<iostream>
#include<vector>
#include<stdio.h>
#include<string.h>
using namespace std;
#pragma warning(disable:4996)
#define INF 0x7FFFFFFF

int gra[505][505],cost[505],dis[505];
bool vis[505];
int N, M;

void mintree(int v)  //最小生成树，Prim算法
{
	memset(vis, 0, N + 1);
	int i,next,r = N - 2,s=v==N?1:v+1; //找除去该点的其他点作为起点，
	for (i = 1; i <= N; ++i)dis[i] = gra[s][i];
	vis[v] = vis[s] = 1;
	while (r--) {
		int min = INF;
		for (i = 1; i <= N; ++i) {
			if (!vis[i] && min > dis[i]) {
				min = dis[i];
				next= i;
			}
		}
		if (min == INF) {  //该点原来就没有路，无法达到其他点
			cost[v] = INF;
			break;
		}
		cost[v] += min;vis[next]=1;
		for (i = 1; i <= N; ++i) {  //更新集合到未被访问的点的最短路径
			if (!vis[i]&&gra[next][i] < dis[i])dis[i] = gra[next][i];
		}
	}
}

int main()
{
    freopen("test.txt","r",stdin);
	int i, j, maxcost=0;
	scanf("%d %d", &N, &M);
	for (i = 1; i <= N; ++i) {
		for (j = 1; j <= N; ++j)
			gra[i][j] = INF;
	}
	while (M--) {
		int c1, c2, c, s;
		scanf("%d %d %d %d", &c1, &c2, &c, &s);
		if (s)gra[c1][c2] = gra[c2][c1] = 0;
		else gra[c1][c2] = gra[c2][c1] = c;
	}
	for (i = 1; i <= N; ++i) {
		cost[i] = 0; mintree(i);
		if (cost[i] > maxcost)maxcost = cost[i];
	}
	if (maxcost == 0)printf("0");
	else {
		bool flag = 0;
		for (i = 1; i <= N; ++i) {
			if (cost[i] == maxcost) {
				printf("%s%d", flag ? " " : "", i);
				flag = 1;
			}
		}
	}
	return 0;
}

2）再放上博主_Occult_的方法：保存路径，好的在前，坏的在后，并以权值递增。这样做的好处是遍历路径是先遍历的肯定是好的，可以将这些好路径连接的点并成一个集合，如果有点未并进来，则从最短的路径开始，合并集合，我感觉这种方法更像并查集。厉害啊！！！

代码如下：

#include<bits/stdc++.h>
using namespace std;
#define MAX 300000
#define INF 0x7fffffff
int root[505],costs[505];
struct route{
    int c1,c2,cost,status;
    void read(){scanf("%d%d%d%d",&c1,&c2,&cost,&status);}
    //重载小于，好的路径在前，cost递增
    bool operator <(const route& r){return r.status==status?cost<r.cost:status>r.status;}
}rou[MAX];

int getroot(int n)  //返回集合的根结点,并将路径上节点的父亲节点修改为根节点。
{
    return root[n]==n?n:root[n]=getroot(root[n]);
}

int main()
{
    //freopen("test.txt","r",stdin);
    int N,M,i,j,num;
    scanf("%d%d",&N,&M);
    for(i=0;i<M;++i)rou[i].read();
    sort(rou,rou+M);
    int ans=0;
    for(i=1;i<=N;++i){
        for(j=1;j<=N;++j)root[j]=j;
        costs[i]=0;num=N-2;//M-2条路
        for(j=0;j<M;++j){
            if(rou[j].c1==i||rou[j].c2==i)continue;//不计连接该点的所有路径
            int r1=getroot(rou[j].c1),r2=getroot(rou[j].c2);
            if(r1==r2)continue;//已经属于一个集合
            --num;  //集合个数减一
            root[r2]=r1;//合并两个集合
            if(!rou[j].status)costs[i]+=rou[j].cost;
        }
        if(num>0)costs[i]=INF;
        ans=max(ans,costs[i]);
    }
    if(ans){
        bool flag=0;
        for(i=1;i<=N;++i){
            if(costs[i]==ans){
                printf("%s%d",flag?" ":"",i);
                flag=1;
            }
        }
        return 0;
    }
    printf("0");
    return 0;
}

参考：https://blog.csdn.net/jtjy568805874/article/details/50759425

          https://blog.csdn.net/bendaai/article/details/60592390