hdu5438 Ponds
2024-10-15 04:01:45
Time Limit: 1500/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 2677 Accepted Submission(s): 850
Problem Description
Betty 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
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
Input
The first line of input will contain a number T(1≤T≤30) which
is the number of test cases.
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.
is the number of test cases.
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.
Output
For 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.
Sample Input
1
7 7
1 2 3 4 5 6 7
1 4
1 5
4 5
2 3
2 6
3 6
2 7
7 7
1 2 3 4 5 6 7
1 4
1 5
4 5
2 3
2 6
3 6
2 7
Sample Output
21
这题可以用拓扑排序做,先删除所有能删除的点,然后再一遍dfs就行了。
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<stack>
#include<string>
#include<algorithm>
using namespace std;
typedef long long ll;
#define inf 99999999
#define pi acos(-1.0)
#define maxn 10040
int value[maxn],du[maxn],vis[maxn],n;
ll sum1,num1;
struct edge{
int to,next,len;
}e[200050];
int first[maxn];
int q[1111111];
void topu()
{
int i,j,front,rear,x,xx,v;
front=1;rear=0;
for(i=1;i<=n;i++){
if(du[i]<=1){
rear++;q[rear]=i;
vis[i]=1;
}
}
while(front<=rear){
x=q[front];
front++;
for(i=first[x];i!=-1;i=e[i].next){
v=e[i].to;
if(vis[v])continue;
du[v]--;
if(du[v]<=1){
rear++;
q[rear]=v;
vis[v]=1;
}
}
}
}
void dfs(int root)
{
int i,j,v;
vis[root]=1;
num1++;
sum1+=value[root];
for(i=first[root];i!=-1;i=e[i].next){
v=e[i].to;
if(!vis[v]){
dfs(v);
}
}
}
int main()
{
int m,i,j,T,tot,c,d;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++){
scanf("%d",&value[i]);
}
tot=0;
memset(first,-1,sizeof(first));
memset(du,0,sizeof(du));
memset(vis,0,sizeof(vis));
for(i=1;i<=m;i++){
scanf("%d%d",&c,&d);
du[c]++;
du[d]++;
tot++;
e[tot].next=first[c];e[tot].to=d;
first[c]=tot;
tot++;
e[tot].next=first[d];e[tot].to=c;
first[d]=tot;
}
topu();
ll sum=0;
for(i=1;i<=n;i++){
if(vis[i])continue;
sum1=0;
num1=0;
dfs(i);
if(num1&1)sum+=sum1;
}
printf("%lld\n",sum);
}
return 0;
}
最新文章
- sql 批量插入数据到Sqlserver中 效率较高的方法
- codesmith生成java类
- Kinect V2 基础教程之彩色图像
- Android应用中菜单(Menu)的位置显示问题
- StringBuilder 大量字符串时使用,速度比较快
- hibernate总结一
- Ajaxterm
- 微信小程序入门学习
- Day-16: 图形界面
- 【漏洞分析】dedecms有前提前台任意用户密码修改
- [bzoj2286][Sdoi 2011]消耗战
- Java多线程之一
- 关于nexus的学习
- FAT文件系统规范v1.03学习笔记---1.保留区之启动扇区与BPB
- 论文阅读笔记三:R2CNN:Rotational Region CNN for Orientation Robust Scene Text Detection(CVPR2017)
- es6学习日记2
- Android学习之Button按钮在程序运行时全部变大写的处理
- nodejs操作monggodb数据库封装
- MySQL学习笔记-MySQL体系结构总览
- HttpServletRequest -- 获取请求主机真实的IP地址