2015 ACM/ICPC Asia Regional Changchun Online Pro 1002 Ponds(拓扑排序+并查集)
Ponds
Time Limit: 1500/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 0 Accepted Submission(s): 0
owns a lot of ponds, some of them are connected with other ponds by
pipes, and there will not be more than one pipe between two ponds. Each
pond has a value v.
Now
Betty wants to remove some ponds because she does not have enough
money. But each time when she removes a pond, she can only remove the
ponds which are connected with less than two ponds, or the pond will
explode.
Note that Betty should keep removing ponds until no more
ponds can be removed. After that, please help her calculate the sum of
the value for each connected component consisting of a odd number of
ponds
For each test case, the first line contains two number separated by a blank. One is the number p(1≤p≤104) which represents the number of ponds she owns, and the other is the number m(1≤m≤105) which represents the number of pipes.
The next line contains p numbers v1,...,vp, where vi(1≤vi≤108) indicating the value of pond i.
Each of the last m lines contain two numbers a and b, which indicates that pond a and pond b are connected by a pipe.
each test case, output the sum of the value of all connected components
consisting of odd number of ponds after removing all the ponds
connected with less than two pipes.
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e4+,maxm = 2e5+;
int n,m;
int val[maxn];
int head[maxn],nxt[maxm],to[maxm];
int deg[maxn],ecnt;
bool rmvd[maxn]; void addEdge(int u,int v)
{
to[ecnt] = v;
nxt[ecnt] = head[u];
head[u] = ecnt++;
deg[u]++;
} void topo()
{
queue<int> q;
for(int i = ; i <= n; i++){
if(deg[i] <= ){
rmvd[i] = true;
q.push(i);
}
}
while(q.size()){
int u = q.front(); q.pop();
for(int i = head[u]; ~i; i = nxt[i]){
int v = to[i];
if(!rmvd[v] && --deg[v] == ){
q.push(v); rmvd[v] = true;
}
}
}
}
long long sum[maxn];
int pa[maxn],cnt[maxn];
int fdst(int x) { return x==pa[x]?x:pa[x]=fdst(pa[x]); } int main()
{
//freopen("in.txt","r",stdin);
int T; scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&m);
for(int i = ; i <= n; i++) scanf("%d",val+i);
memset(head,-,sizeof(head));
memset(deg,,sizeof(deg));
memset(rmvd,,sizeof(rmvd));
ecnt = ;
for(int i = ; i < m; i++){
int u,v; scanf("%d%d",&u,&v);
addEdge(u,v); addEdge(v,u);
}
topo();
for(int i = ; i <= n; i++) pa[i] = i,sum[i] = val[i],cnt[i] = ;
for(int i = ,M = *m; i < M; i += ){
int u = to[i], v = to[i^];
if(!rmvd[u] && !rmvd[v]){
int a = fdst(u), b = fdst(v);
if(a != b){
pa[a] = b;
sum[b] += sum[a];
cnt[b] += cnt[a];
}
}
}
long long ans = ;
for(int i = ; i <= n ;i++){
int f = fdst(i);
if(!rmvd[f]){
if(cnt[f]&){
ans += sum[f];
}
rmvd[f] = true;
}
}
printf("%I64d\n",ans);
}
return ;
}
最新文章
- 服务器asp.net 3.5 HTTP 错误 500.19 - Internal Server Error 无法访问请求的页面,因为该页的相关配置数据无效。
- [转]Mysql海量数据存储和解决方案之一—分布式DB方案
- Natural Language Toolkit
- nodejs weixin 笔记
- Ext Js学习之IIS理解
- Dubbo服务调用的动态代理和负载均衡
- 【VMware虚拟机】【克隆问题】在VMware 9.0下克隆CentOS6.5虚拟机无法识别eth网卡
- unity NGUI点击消息不传入到场景中去
- ubuntu登陆后一闪回到登陆界面
- Java反射机制深度剖析
- JavaScript函数与对象
- Nginx负载均衡的5种策略(转载)
- Python学习之路&mdash;&mdash;&mdash;&mdash;&mdash;day04
- linux中安装gcc
- js原生事件系统与坐标系统
- Django content-type 使用
- tcp协议下粘包问题的产生及解决方案
- [LeetCode] 255. Verify Preorder Sequence in Binary Search Tree_Medium tag: Preorder Traversal, tree
- [异常记录-12]Web Deploy部署:未能连接到远程计算机,请确保在远程计算机上安装了 Web Deploy 并启动了所需的进程(";Web Management Service";)
- “全栈2019”Java多线程第七章:等待线程死亡join()方法详解
热门文章
- JAVA基础学习-集合三-Map、HashMap,TreeMap与常用API
- Ext.net Calendar 控件在有模板页的时候,模板页定义了TD的样式造成日历控件的样式丢掉
- Halcon - 获取图像数据(灰度值)
- C++经典面试算法题
- Object Detection(RCNN, SPPNet, Fast RCNN, Faster RCNN, YOLO v1)
- SQL 截取字段空格之前的数据
- 51nod1255(栈)
- 洛谷P3182 [HAOI2016]放棋子
- HTML5新标签介绍
- 黑马学习JavaWeb入门总结