hdu 5438(类似拓扑排序)
Ponds
Time Limit: 1500/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 3178 Accepted Submission(s): 988
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.
7 7
1 2 3 4 5 6 7
1 4
1 5
4 5
2 3
2 6
3 6
2 7
#include<stdio.h>
#include<iostream>
#include<string.h>
#include <stdlib.h>
#include<math.h>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long LL;
const int N = ;
const int M = ;
struct Edge{
int v,next;
}edge[*M];
int head[N];
LL value[N];
int indegree[N];
int tot;
int vis[N];
queue<int> q;
void init(){
while(!q.empty()) q.pop();
memset(indegree,,sizeof(indegree));
memset(head,-,sizeof(head));
memset(vis,,sizeof(vis));
tot=;
}
void addEdge(int u,int v,int &k){
edge[k].v = v,edge[k].next = head[u],head[u]=k++;
}
LL weight;
int cnt;
void dfs(int u){
vis[u]=;
cnt++;
weight+=value[u];
for(int k=head[u];k!=-;k=edge[k].next){
int v=edge[k].v;
if(!vis[v]){
dfs(v);
}
}
}
int main()
{
int tcase;
scanf("%d",&tcase);
while(tcase--)
{
init();
int n,m;
scanf("%d%d",&n,&m);
for(int i=;i<=n;i++) {
scanf("%lld",&value[i]);
}
for(int i=;i<=m;i++){
int a,b;
scanf("%d%d",&a,&b);
indegree[a]++,indegree[b]++;
addEdge(a,b,tot);
addEdge(b,a,tot);
}
for(int i=;i<=n;i++){
if(indegree[i]==) q.push(i);
}
while(!q.empty()){
int u = q.front();
vis[u]=;
q.pop();
for(int k = head[u];k!=-;k=edge[k].next){
int v = edge[k].v;
if(!vis[v]){
indegree[v]--;
indegree[u]--;
if(indegree[v]==) q.push(v);
}
}
}
LL res = ;
for(int i=;i<=n;i++){
weight=,cnt=;
if(!vis[i])
dfs(i);
if(cnt&&&cnt>){
res+=weight;
}
}
printf("%lld\n",res);
}
return ;
}
最新文章
- homework-02
- C#更改文件访问权限所有者(适用于各个Windows版本)
- python中的函数以及递归
- myeclipse+tomcat内存溢出
- Java 生产者模式 消费者模式
- 【PHP】基于ThinkPHP框架搭建OAuth2.0服务
- 项目评价及第五周PSP的发布
- lpad rpad
- inode-软链接与硬链接
- 遍历Javascript数组的一种方法!
- rhel 6.7 离线安装docker
- 一次日语翻译的Chrome插件开发经历
- koa2--delegates模块源码解读
- js隐藏元素、jquery隐藏、css隐藏
- 剑指offer 03:从尾到头打印链表
- docker常用命令记录
- android-基础编程-ListView
- PAT甲题题解-1095. Cars on Campus(30)-(map+树状数组,或者模拟)
- FormatMessage函数
- Ubuntu Linux系统环境变量配置文件