HDU6187(对偶图生成树)
Destroy Walls
Time Limit: 8000/4000 MS (Java/Others) Memory Limit: 132768/132768 K (Java/Others)
Total Submission(s): 377 Accepted Submission(s): 166
Problem Description
Since it was not convenient, the new king wants to destroy some of these walls, so he can arrive anywhere from his castle. We assume that his castle locates at (0.6∗2√,0.6∗3√).
There are n towers in the city, which numbered from 1 to n. The ith's location is (xi,yi). Also, there are m walls connecting the towers. Specifically, the ith wall connects the tower ui and the tower vi(including the endpoint). The cost of destroying the ith wall is wi.
Now the king asks you to help him to divide the city. Firstly, the king wants to destroy as less walls as possible, and in addition, he wants to make the cost least.
The walls only intersect at the endpoint. It is guaranteed that no walls connects the same tower and no 2 walls connects the same pair of towers. Thait is to say, the given graph formed by the walls and towers doesn't contain any multiple edges or self-loops.
Initially, you should tell the king how many walls he should destroy at least to achieve his goal, and the minimal cost under this condition.
Input
For each test case:
The first line contains 2 integer n, m.
Then next n lines describe the coordinates of the points.
Each line contains 2 integers xi,yi.
Then m lines follow, the ith line contains 3 integers ui,vi,wi
|xi|,|yi|≤105
3≤n≤100000,1≤m≤200000
1≤ui,vi≤n,ui≠vi,0≤wi≤10000
Output
Sample Input
-1 -1
-1 1
1 1
1 -1
1 2 1
2 3 2
3 4 1
4 1 2
Sample Output
Source
Recommend
根据欧拉公式我们可以知道对于一个有k个连通分量的平面图的区域数r=E−V+k+1。
//2017-11-16
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm> using namespace std; const int N = ;
const int M = ; namespace DSU{
int fa[N];
void init(){
for(int i = ; i < N; i++)fa[i] = i;
}
int getfa(int x){
return fa[x] = x == fa[x] ? x : getfa(fa[x]);
}
void merge(int a, int b){
int af = getfa(a);
int bf = getfa(b);
if(af != bf){
fa[bf] = af;
}
}
} struct Edge{
int u, v, w;
bool operator< (const Edge e) const {
return w > e.w;
}
}edge[M]; int main()
{
freopen("input.txt", "r", stdin);
int n, m, x, y;
while(~scanf("%d%d", &n, &m)){
for(int i = ; i < n; i++)
scanf("%d%d", &x, &y);
int ans = ;
for(int i = ; i < m; i++){
scanf("%d%d%d", &edge[i].u, &edge[i].v, &edge[i].w);
ans += edge[i].w;
}
DSU::init();
sort(edge, edge+m);
int cnt = ;
for(int i = ; i < m; i++){
int u = edge[i].u;
int v = edge[i].v;
if(DSU::getfa(u) != DSU::getfa(v)){
ans -= edge[i].w;
DSU::merge(u, v);
cnt++;
}
}
printf("%d %d\n", m-cnt, ans);
} return ;
}
最新文章
- mysql习惯及主从复制参数设置
- SSH的端口转发:本地转发Local Forward和远程转发Remote Forward
- jsp学习---css基础知识学习,float,position,padding,div,margin
- unix环境C编程之日期时间转换
- Zend Studio 错误集锦[PHP]
- DbHelperSQL和Dapper数据访问的性能对比
- HibernateTemplate类的方法flush()
- hdu 4501 小明系列故事——买年货_二维背包
- Linux内核中常见内存分配函数(一)
- WPF-20:richtextbox相关操作(转)
- clearfix:after 清除css浮动
- CI/CD持续集成/持续部署 敏捷开发
- 架构师技能图谱 V1.2
- jQuery_parent() parents() closest()区别
- 【Java线程安全】 — 常用数据结构及原理(未完结)
- cocos2dx 实现文字的一键复制功能(IOS、Android)
- Docker Image管理学习笔记,ZT
- 洛谷P4043 支线剧情
- c语言指针应用
- WPF LinkButton