洛谷P2700 逐个击破
2024-08-29 00:25:26
P2700 逐个击破
题目背景
三大战役的平津战场上,傅作义集团在以北平、天津为中心,东起唐山西至张家口的铁路线上摆起子一字长蛇阵,并企图在溃败时从海上南逃或向西逃窜。为了就地歼敌不让其逃走,毛主席制定了先切断敌人东西两头退路然后再逐个歼灭敌人的战略方针。秉承伟大军事家的战略思想,作为一个有智慧的军长你,遇到了一个类似的战场局面。
题目描述
现在有N个城市,其中K个被敌方军团占领了,N个城市间有N-1条公路相连,破坏其中某条公路的代价是已知的,现在,告诉你K个敌方军团所在的城市,以及所有公路破坏的代价,请你算出花费最少的代价将这K个地方军团互相隔离开,以便第二步逐个击破敌人。
输入输出格式
输入格式:
第一行包含两个正整数n和k。
第二行包含k个整数,表示哪个城市别敌军占领。
接下来n-1行,每行包含三个正整数a,b,c,表示从a城市到b城市有一条公路,以及破坏的代价c。城市的编号从0开始。
输出格式:
输出一行一个整数,表示最少花费的代价。
输入输出样例
说明
【数据范围】
10%的数据:2≤n≤10;
100%的数据:2≤n≤100000,2≤k≤n,1≤c≤1000000。
/*
倒序加边并查集
*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#define maxn 100010
using namespace std;
int n,m,k,fa[maxn],num,head[maxn];
long long sum;
bool vis[maxn];
struct node{
int from,to,v;
}e[maxn];
bool cmp(node x,node y){return x.v>y.v;}
int find(int x){
if(x==fa[x])return x;
return fa[x]=find(fa[x]);
}
int main(){
scanf("%d%d",&n,&m);int x;
for(int i=;i<=n;i++)fa[i]=i;
for(int i=;i<=m;i++){
scanf("%d",&x);
vis[x]=;
}
for(int i=;i<=n-;i++){
scanf("%d%d%d",&e[i].from,&e[i].to,&e[i].v);
sum+=e[i].v;
}
sort(e+,e+n,cmp);
for(int i=;i<n;i++){
int f1=find(e[i].from),f2=find(e[i].to);
if(!(vis[f1]&&vis[f2])){
fa[f2]=f1;
vis[f1]=(vis[f1]||vis[f2]);
sum-=e[i].v;
}
}
cout<<sum;
return ;
}
最新文章
- OpenCV人脸识别Eigen算法源码分析
- 关于kali2.0 rolling无法连接数据的解决办法
- mybatis与 Exception
- map,hash_map, hash_table, 红黑树 的原理和使用
- 微信客户端自带的Js Api:WeixinJSBridge
- Codeforces Round #379 (Div. 2) D. Anton and Chess 水题
- uiwebview和 js交互框架
- 网狐6603 cocos2dx 棋牌、捕鱼、休闲类游戏《李逵捕鱼》手机端完整源码分析及分享
- 最流行的android组件大全
- 51操作各种demo 驱动
- wpf为ListBox添加渐变
- MVC项目中使用百度地图
- Unity中的Mono &; Linux上编译Mono的流程
- python3之File文件方法
- 转化.vdi到.vmdk
- 26个ASP.NET常用性能优化方法
- JS取出两个数组中的不同或相同元素
- DBMS客户端是否安装:Make sure DBMS client is installed and this required library is available for dynamic loading
- maven项目红叉问题
- Python高级网络编程系列之第一篇
热门文章
- Vue从接口请求数据
- 关于C++多态的理解
- leetcode 50. Pow(x, n)(快速幂)
- the referenced script on this behaviour is missing!
- 【leetcode刷题笔记】Reverse Linked List II
- Redo Log File(inactive、active)损坏,处理恢复对策
- nodejs 上传图片(服务端输出全部代码)
- 【Android学习笔记】 点击穿透(Click Through)
- 使用svnadmin对VisualSVN进行项目迁移
- Wireshark抓包常见问题解析