Java Out Of Memory Jetson Nano https cocoa autocomplete Skeljs Echojs 后台模板 java运行软件 oracle给表增加字段 python计算器 python随机函数 python中time python怎么调用函数 javasubstring java环境搭建 java使用正则表达式 java文档 java单继承 javaabstract java安装 linuxtar命令 volist 神龙kms crazytalk python输入数字 只狼鬼佛 网络工程师教程 虚拟打印机安装 脚本错误怎么解决 findall 数组删除指定元素 js切割字符串 qq游戏黑名单 cad文件 dnf风神加点 lol世界第一 水之td合成 浣海之核 kms工具
当前位置: 首页 > 学习教程  > 编程语言

HDU6763 Total Eclipse(并查集+思维+贪心)

2020/8/11 19:43:40 文章标签:

HDU6763 Total Eclipse(并查集+思维+贪心)

Description
There are n cities and m bidirectional roads in Byteland. These cities are labeled by 1,2,…,n, the brightness of the i-th city is bi.
Magician Sunset wants to play a joke on Byteland by making a total eclipse such that the brightness of every city becomes zero. Sunset can do the following operations for arbitrary number of times:
· Select an integer k (1≤k≤n).
· Select k distinct cities c1,c2,…,ck (1≤ci≤n) such that they are connected with each other. In other words, for every pair of distinct selected cities ci and cj (1≤i<j≤k), if you are at city ci, you can reach city cj without visiting cities not in {c1,c2,…,ck}.
· For every selected city ci (1≤i≤k), decrease bci by 1.
Note that Sunset will always choose k with the maximum possible value. Now Sunset is wondering what is the minimum number of operations he needs to do, please write a program to help him.
Input
The first line of the input contains a single integer T (1≤T≤10), the number of test cases.
For each case, the first line of the input contains two integers n and m (1≤n≤100000, 1≤m≤200000), denoting the number of cities and the number of roads.
The second line of the input contains n integers b1,b2,…,bn (1≤bi≤109), denoting the brightness of each city.
Each of the following m lines contains two integers ui and vi (1≤ui,vi≤n,ui≠vi), denoting an bidirectional road between the ui-th city and the vi-th city. Note that there may be multiple roads between the same pair of cities.
Output
For each test case, output a single line containing an integer, the minimum number of operations.
Sample Input
1
3 2
3 2 3
1 2
2 3
Sample Output
4

题意

有n个城市,通过m条道路连接,每个城市有一个亮度值,选择一个连通块的城市一起将亮度-1,请问需要减多少次1才能将所有城市的亮度值清零。
我先用结构体存入城市的亮度值和城市的下标,并通过城市的亮度值降序sort排序。再采用链式前向星的方法建图用道路连接城市。接下来从亮度值最大的城市开始一个个遍历,遍历到的城市(标记为u)的vis标记为true。然后再查找这个城市连接的城市(标记为v)。接下来我们再用并查集中的find函数寻找查找v的祖先是否是u,若是则跳过此次循环(这里其实是处理重边)。若城市v是我们先前没有作为u遍历到的城市,则跳过此次循环。若以上的条件都符合,没有被跳过循环,则我们就用v的祖先的亮度值减去u的亮度值(因为没有被跳过循环的城市v都是先前已经遍历到过的(也就是作为u过的),则其包括其祖先的亮度值必然要大于目前遍历到的城市u的亮度值,这里就是贪心思想的体现)并将这个差值加入ans中,并且将v的祖先更新为u的家族中。
结束这个大循环后,我们只要查找祖先没有被更新过的的点其实也就是各个连通块中亮度值最小的那个点(经过上面那个大循环后,连通块中最小的点,也是作为这个连通块中所有点的最大的祖先),将其亮度值加入ans中,这个ans就是答案了。

#include<iostream>
#include<string>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<queue>
#include<stack>
#include<vector>
#include<algorithm>
#include<functional>
#include<map>
#include<unordered_map>
#define lowbit(x) ((x)&-(x))
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll N=1e6+10,NN=2e3+10,INF=0x3f3f3f3f,LEN=20;
const ll MOD=1e9+7;
const ull seed=31;
inline ll read(){
    ll x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9'){
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}
struct Node{
	ll bright;
	ll id;
	bool friend operator<(const Node &a,const Node &b){
		return a.bright>b.bright;
	}
}b[N];
struct Edge{
	ll next,to;
}edge[N];
ll n,m,num_edge;
ll ans;
ll fa[N],head[N],bright[N];
bool vis[N];
void add_edge(ll from,ll to){
	edge[num_edge].next=head[from];
	edge[num_edge].to=to;
	head[from]=num_edge++;
}
ll find(ll x){
	return x==fa[x]?x:fa[x]=find(fa[x]);
}
void merge(ll x,ll y){
	ll f1=find(x);
	ll f2=find(y);
	fa[f1]=f2;
}
void init(){
	ans=0;
	num_edge=0;
	memset(head,-1,sizeof head);
	memset(vis,false,sizeof vis);
	for(ll i=1;i<=n;i++) fa[i]=i;
}
int main(){
	ll t;
	t=read();
	while(t--){
		n=read();
		m=read();
		init();
		for(ll i=1;i<=n;i++){
			bright[i]=read();
			b[i].bright=bright[i];
			b[i].id=i;
		}
		sort(b+1,b+1+n);
		for(ll i=1;i<=m;i++){
			ll u,v;
			u=read();
			v=read();
			add_edge(u,v);
			add_edge(v,u);
		}
		for(ll i=1;i<=n;i++){
			ll u=b[i].id;
			vis[u]=true;
			for(ll j=head[u];j!=-1;j=edge[j].next){
				ll v=edge[j].to;
				if(!vis[v]) continue;
				ll rt=find(v);
				if(rt==u) continue;//处理重边的作用
				ans+=(bright[rt]-bright[u]);
				merge(rt,u);
			}
		}
		for(ll i=1;i<=n;i++) if(fa[i]==i) ans+=bright[i];
		printf("%lld\n",ans);
	}
}

本文链接: http://www.dtmao.cc/news_show_100163.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?