2019 ICPC Asia Nanchang Regional E-Bob's Problem（图论、贪心）

本文网址：https://blog.csdn.net/xiaomaolin2/article/details/103496715

传送门：https://nanti.jisuanke.com/t/42580

首先这是个图论题，但是完全可以不用图论算法做，用简单的分析加上贪心即可 。

题意：N个点、M条带权边，其中有一部分（c == 1）为白边，一部分为（c == 0）为黑边，问在限制选择白边的最大数量为k的前  提下能不能完全连接这N个点，能连接时的最大被选中边权和为多少。

解题思路：黑边全选了，看有多少点没有被连接，然后在能到未连接点的白边中选择最长的。

具体实现，先上代码：

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <cstdio>
#include <queue>
#include <cmath>
#include <map>
#include <set>
using namespace std;
typedef long long ll;

const int maxn=5e5+10;
set<int>ss;
int T;
int n,m,k;

struct edge{
	int l;
	int r;
	int len;
	int flag;
}edge[maxn];

int cmp(struct edge a,struct edge b){
	return a.len > b.len;
}

int main(){
	scanf("%d",&T);
	while(T--){
		ll sum = 0;
		ss.clear();
		scanf("%d%d%d",&n,&m,&k);
		int flag[n + 1] = {0};
		int white = 0;
		int l,r,len,flag1;
		for(int i = 0;i < m;i++){
			edge[i].flag = 0;
			scanf("%d%d%d%d",&l,&r,&len,&flag1);
			if(flag1){
				edge[white].l = l;
				edge[white].r = r;
				edge[white++].len = len;
			}
			else{
				flag[l]++;
				flag[r]++;
				sum += len; 
			}
		}
		for(int i = 1;i <= n;i++){
			if(flag[i] < 1) ss.insert(i);
		}
	/*/(*)	for(set<int>::iterator it = ss.begin();it != ss.end();it++){
			printf("%d\n",*it);
		}*/
		sort(edge,edge + white,cmp);
		for(int i = 0;i < white;i++){
			if(ss.find(edge[i].l) != ss.end() || ss.find(edge[i].r) != ss.end()){
				ss.erase(edge[i].l);
				ss.erase(edge[i].r);
				sum += edge[i].len;
				edge[i].flag = 1;
				k--;
				//printf("添加边%d-%d-%d\n",edge[i].l,edge[i].r,edge[i].len);
			}
			if(ss.empty() || !k) break;
		}
		if(ss.empty()) {
			for(int i = 0;i < m;i++){
				if(k <= 0) break;
				if(edge[i].flag == 0){
					sum += edge[i].len;
					edge[i].flag = 1;
					k--;
				}	
			}
			printf("%lld\n",sum);
		}
		else{
			printf("-1\n");
			//printf("%lld\n",sum);
		}
	}
	return 0;
}

 有问题可以联系2339814485（QQ）、17781101461（微信），希望与大家多多交流。