Minimum Cut(2015沈阳online)【贪心】
2024-10-06 20:14:14
Minimum Cut[贪心]2015沈阳online
题意:割最少的边使得图不连通,并且割掉的边中有且仅有一条是生成树的边。
首先,我们选择一条树中的边进行切割,此时仅考虑树上的边集,有两种情况:1.树被分为两个结点数大于1的子树2.树被分为一个子树和一个单独结点。
如果选择第一种情况,那么还要割掉其中一颗子树中的结点所涉及到的所有非树中边,这种情况下,如果重新选择,选择子树上的一个叶子结点,那么只需要割掉叶子结点于该树所连的边和该结点涉及到的非树中边,所需要割的边数一定小于第一种情形。
代码如下:
#include<bits/stdc++.h> using namespace std; int main(){
int t,n,m,a,b;
scanf("%d",&t);
for(int i=;i<=t;i++){
scanf("%d%d",&n,&m);
int td[]={},gd[]={};
for(int i=;i<n;i++){
scanf("%d%d",&a,&b);
td[a]++;
td[b]++;
}
for(int i=;i<=m-n+;i++){
scanf("%d%d",&a,&b);
gd[a]++;
gd[b]++;
}
int ans=;
for(int i=;i<=n;i++){
if(td[i]==)
ans=min(ans,+gd[i]);
}
printf("Case #%d: %d\n",i,ans);
}
return ;
}
xxmlala's code
不得不说,最近的几场训练赛中,我们普遍存在一个问题,就是过于相信榜,榜上较少人过的题,我们往往会觉得自己也肯定过不了,就直接看都不看跳过了,此外,我们也常常在一道题上吊死,常常卡题卡好几个小时还不肯放过,以后一定要及时开新题,充分开新题!
由于做过的树相关题目较少,看到树的题,我总是会下意识的逃避,以后要克服这种畏难情绪,多多刷题~
Ps:参考了这位巨巨的解析https://blog.csdn.net/wygdove/article/details/48625467
最新文章
- 常见http错误码解读
- eclipse从下载到使用
- 疯狂java学习笔记之面向对象(五) - 封装、继承、多态
- oracle create table(转)
- StreamWriter和StremReader简单的用法
- .bash_profile备份
- 248. Strobogrammatic Number III
- Django里,如何更改ADMIN管理后台的显示
- My安装Eclipse三种方法插件
- Java基础知识强化之网络编程笔记02:Socket通信原理图解
- 11061160顾泽鹏homework-01
- MySQL的grant,revoke使用
- Linux服务器病毒清理实践
- 996.ICU与死亡因素
- jdk8中奖Date转换为String格式的方法
- OSI七层协议与TCP/IP模型
- 获取Map的key和value的两种方法
- Java 配置环境变量教程
- Android--WebView 自适应代码
- 【LOJ】#2122. 「HEOI2015」小 Z 的房间
热门文章
- vue-cli 3.x 修改dist路径和在本地查看方法
- Windows下安装Elasticsearch6.4.1和Head,IK分词器
- 第四章 Python数据分析-描述性分析
- js中的DOM对象和jQuery对象的比较
- 处理flutter http请求添加application/json报错Cannot set the body fields of a Request with content-type “application/json”
- [Java]给指定时间加上十秒
- PHP学习之PHP代码的优化
- Android自定义权限与使用
- 使用Pull解析器生成XML文件
- Java之分布式事务TCC