SPOJ COMPANYS Two Famous Companies 最小生成树,二分,思路 难度:2
2024-10-17 21:27:04
http://www.spoj.com/problems/COMPANYS/en/
题目要求恰好有k条0类边的最小生成树
每次给0类边的权值加或减某个值delta,直到最小生成树上恰好有k条边为0,此时得到最小生成树的权值-更改的值*k即为答案
但是直接这么做的话会超时,因为都是整数权值,所以只需要优先取0类边,二分整数delta即可
如果直接给所有0类边减100,让0类边优先选择,那么会导致整棵树不一定是最小的,应该优先选择的1类边没有选择
#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn=2e5+5;
typedef pair<int,int> P;
int first[maxn];
struct edge{
int f,t,nxt,c;
int tel;
}e[maxn],org[maxn];
int n,m,k,sum;
bool used[maxn]; void addedge(int f,int t,int c,int tel,int i){
org[i].nxt=first[f];
first[f]=i;
org[i].f=f;
org[i].t=t;
org[i].c=c;
org[i].tel=tel;
}
class Greater: public binary_function<P, P,bool>
{
public:
bool operator()(const P& a, const P& b)
{
if(a.first!=b.first)return a.first>b.first;
return e[a.second].tel<e[b.second].tel;
}
};
priority_queue <P,vector<P>,Greater> pque;
int prim(){
memset(used,false,sizeof(used));
used[0]=true;
int unum=1;
for(int p=first[0];p!=-1;p=e[p].nxt){
pque.push(P(e[p].c,p));
}
sum=0;
int ans=0;
while(unum<n&&!pque.empty()){
int p=pque.top().second;
int t=e[p].t;
int td=pque.top().first;
pque.pop();
if(used[t])continue;
if(e[p].tel)ans++;
sum+=td;
used[t]=true;
unum++; for(int p=first[t];p!=-1;p=e[p].nxt){
if(!used[e[p].t]){
pque.push(P(e[p].c,p));
}
} }
while(!pque.empty())pque.pop();
return ans;
}
int main(){
int ki=0;
while(scanf("%d%d%d",&n,&m,&k)==3&&++ki){
memset(first,-1,sizeof(first));
for(int i=0;i<m;i++){
int f,t,c,color;
scanf("%d%d%d%d",&f,&t,&c,&color);
addedge(f,t,c,1-color,2*i);
addedge(t,f,c,1-color,2*i+1);
}
int l=-110,r=110;
int ans;
while(l<=r){
int mid=(l+r)/2;
copy(org,org+2*m,e);
for(int i=0;i<2*m;i++){
if(e[i].tel){
e[i].c+=mid;
}
}
int kk=prim();
// if(kk==k){ans=sum-k*mid;break;}
if(kk<k)r=mid-1;
else {ans=sum-k*mid;l=mid+1;}
}
printf("Case %d: %d\n",ki,ans);
}
return 0;
}
最新文章
- UEditor百度富文本编辑器--让编辑器自适应宽度的解决方案
- hello 漂亮的小靓仔
- 常用HTML标签元素结合及简介
- java 删除所有HTML工具类
- DISK 100% BUSY,谁造成的?
- centos7扩展磁盘空间
- Fatal error: Class &#39;GearmanClient&#39; not found解决方法
- Qt之QHeaderView自定义排序(获取正确的QModelIndex)
- SpringMVC 简单
- 解题报告 HDU1176 免费馅饼
- GDB: advanced usages
- 原生JS的HTTP请求
- 浏览器Agent大全 (含IE 11, Edge)
- Hadoop问题:chmod 0700 of directory /var/lib/apt/lists/
- 『Candies 差分约束系统』
- discuz论坛 模板修改
- Structs复习 访问web元素
- js如何获取前后连续n天的时间
- [BZOJ3309]DZY Loves Math(莫比乌斯反演+线性筛)
- 利用xpath来解析douban电影相对应的信息
热门文章
- Rain on your Parade---hdu2389(HK求最大匹配)
- yii2框架2 (二)项目结构
- 【Loadrunner】使用LoadRunner上传及下载文件
- [py]python中的==和is的区别
- HDU4135Co-prime(容斥原理)
- 忘记oracle的sys用户密码怎么修改以及Oracle 11g 默认用户名和密码
- 无界面Ubuntu服务器搭建selenium+chromedriver+VNC运行环境
- linux内核分析第三周-跟踪分析Linux内核的启动过程
- Linux服务器使用tar加密压缩文件
- JDK 1.8 ConcurrentHashMap 源码剖析