hdu4313 贪心+并查集
2024-09-06 04:43:52
题意简单思路也还可以。开始从小到大排序非常烦。后来从大到小就很简单了;
从大到小解决了删除的边最小。
#include<stdio.h>
#include<string.h>
#include<algorithm>
#define maxn 100010
using namespace std;
#define LL long long
struct node
{
int x,y;
LL v;
}edge[maxn];
int pa[maxn],n,m,vis[maxn];
bool cmp(node a,node b)
{
return a.v>b.v;
}
void init()
{
int i;
for(i=;i<=n;i++)
pa[i]=i;
}
int find (int x)
{
if(x!=pa[x])
pa[x]=find(pa[x]);
return pa[x];
}
void kruskal()
{
int i,j;
LL ans=;
for(i=;i<n-;i++)
{
int fx=find(edge[i].x);
int fy=find(edge[i].y);
if(vis[fx]&&vis[fy])
{
ans+=edge[i].v;
}
else if(vis[fx])
pa[fy]=fx;
else if(vis[fy])
pa[fx]=fy;
else pa[fx]=fy;
}
printf("%I64d\n",ans);
}
int main()
{
int i,j,t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
init();
memset(vis,,sizeof(vis));
for(i=;i<n-;i++)
{
scanf("%d%d%lld",&edge[i].x,&edge[i].y,&edge[i].v);
}
for(i=;i<m;i++)
{
int c;
scanf("%d",&c);
vis[c]=;
}
sort(edge,edge+n-,cmp);
kruskal();
}
}
最新文章
- 小小改动帮你减少bundle.js文件体积(翻译)
- Workerman-文件监控-牛刀小试
- Spring学习笔记之一----基于XML的Spring IOC配置
- @MappedSuperclass的用法
- Spring.Net Remoting 相关使用
- uva----(100)The 3n + 1 problem
- Mysql性能优化那些事
- iTween visual Editor 0.6.1
- 删除链表的中间节点和a/b处节点
- route命令实例练习
- js的赋值问题:值传递还是引用传递?
- jquery 树形导航菜单无限级
- 【Android开发经验】android:windowSoftInputMode属性具体解释
- 《ERP系统修正数据的sql文件》
- java中线程池的使用
- Homebrew安装与使用
- system v 共享内存
- 2018.11.04 洛谷P1081 开车旅行(倍增)
- 【BZOJ】【2120】数颜色 &; 【2453】维护队列
- R语言低级绘图函数-grid