最小割好劲啊

原题:

新的技术正冲击着手机通讯市场,对于各大运营商来说,这既是机遇,更是挑战。THU集团旗下的CS&T通讯公司在新一代通讯技术血战的前夜,需要做太多的准备工作,仅就站址选择一项,就需要完成前期市场研究、站址勘测、最优化等项目。在前期市场调查和站址勘测之后,公司得到了一共N个可以作为通讯信号中转站的地址,而由于这些地址的地理位置差异,在不同的地方建造通讯中转站需要投入的成本也是不一样的,所幸在前期调查之后这些都是已知数据:建立第i个通讯中转站需要的成本为Pi(1≤i≤N)。另外公司调查得出了所有期望中的用户群,一共M个。关于第i个用户群的信息概括为Ai, Bi和Ci:这些用户会使用中转站Ai和中转站Bi进行通讯,公司可以获益Ci。(1≤i≤M, 1≤Ai, Bi≤N) THU集团的CS&T公司可以有选择的建立一些中转站(投入成本),为一些用户提供服务并获得收益(获益之和)。那么如何选择最终建立的中转站才能让公司的净获利最大呢?(净获利 = 获益之和 - 投入成本之和)

N≤5 000,M≤50 000,0≤Ci≤100,0≤Pi≤100

本来想看妹主席的ppt补一波最小割,然后照着ppt上的套路建图,然后连样例都过不了……
然后自己脑补啊,然后脑补出来的图离妹主席的模型越来越远了,最后想到一种建图好像有理有据的样子

测一下样例过了,然后抱着直接WA掉的心态裸交1A……

具体就是先使用最小不能获得的收益转化成最小割模型

然后s到i表示选,i到t表示不选,那么如果把s->i割掉就会损失pi的收益(表示选),把i->t割掉就会损失wi/2的收益(表示不选)

为啥是wi/2?

因为如果a和b有两个都选则获得wi的收益的条件,就会在ab之间连两个方向相反流量为wi/2的边(为啥不是无向边?,因为网络流要建反向边)

然后如果两个都没选那么割掉两个i->t就是少了wi/2*2的收益,如果一个选一个没选那么没选的a就会通过s->a,a->b,b->t割一个wi/2的边,依旧会少wi/2*2的收益

只有当两个都选即s->a,s->b都被割掉的时候a,b之间的边和a,b到t的边才能避免被割掉,获得wi/2*2的收益

(感觉妹主席的方法和我的核心思想是一样的但是在某些细节上不同?反正我A掉了

恩差不多就是酱紫

为了防止精度问题我输入的时候乘个2输出的时候再除回去,不知道这样是否有必要

代码:

 #include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
using namespace std;
const int oo=;
int rd(){int z=,mk=; char ch=getchar();
while(ch<''||ch>''){if(ch=='-')mk=-; ch=getchar();}
while(ch>=''&&ch<=''){z=(z<<)+(z<<)+ch-''; ch=getchar();}
return z*mk;
}
struct ddd{int nxt,y,v,rvs;}e[]; int lk[],ltp=;
inline void ist(int x,int y,int z){
e[++ltp].nxt=lk[x],lk[x]=ltp,e[ltp].y=y,e[ltp].v=z,e[ltp].rvs=ltp+;
e[++ltp].nxt=lk[y],lk[y]=ltp,e[ltp].y=x,e[ltp].v=,e[ltp].rvs=ltp-;
}
int n,m,a[]; int s,t,M=;
int lvl[];
int q[],hd=;
int quq=;
bool gtlvl(){
memset(lvl,,sizeof(lvl));
q[hd=]=s,lvl[s]=;
for(int k=;k<=hd;++k)
for(int i=lk[q[k]];i;i=e[i].nxt)if(e[i].v && !lvl[e[i].y])
lvl[e[i].y]=lvl[q[k]]+,q[++hd]=e[i].y;
return lvl[t];
}
int mxflw(int x,int y){
if(x==t) return y;
int bwl=,flw=;
for(int i=lk[x];i && bwl<y;i=e[i].nxt)if(e[i].v && lvl[e[i].y]==lvl[x]+)
if((flw=mxflw(e[i].y,min(y-bwl,e[i].v)))){
bwl+=flw;
e[i].v-=flw,e[e[i].rvs].v+=flw;
//cout<<x<<"->"<<e[i].y<<" "<<flw<<endl;
}
if(!bwl) lvl[x]=;
return bwl;
}
int dnc(){
int bwl=,flw;
while(gtlvl())while(flw=mxflw(s,oo)) bwl+=flw;
return bwl;
}
int main(){//freopen("ddd.in","r",stdin);
cin>>n>>m; s=,t=n+;
for(int i=;i<=n;++i) ist(s,i,rd()*);
int l,r,v;
for(int i=;i<=m;++i){
l=rd(),r=rd(),v=rd()*; quq+=v,v>>=;
a[l]+=v,a[r]+=v,ist(l,r,v),ist(r,l,v);
}
for(int i=;i<=n;++i) ist(i,t,a[i]);
cout<<(quq-dnc())/<<endl;
return ;
}

最新文章

  1. ThreadLocal
  2. 图片垂直居中 和 float
  3. [Leetcode] Word BreakII
  4. sp_executesql 两种写法
  5. vbe6ext.olb不能被加载 宏内存溢出
  6. PD 脚本中列名注释用Name属性
  7. iOS开发UI篇—UITabBarController生命周期(使用storyoard搭建)
  8. linux笔记2.21
  9. Google机器学习笔记(七)TF.Learn 手写文字识别
  10. day2--课前考试题
  11. SpringBoot ( 七 ) :springboot + mybatis 多数据源最简解决方案
  12. IO (一)
  13. Android使用百度地图出现闪退及定位时显示蓝屏问题
  14. 如何使用RSS
  15. innerHTML innerText与outerHTML间的区别
  16. vue 项目引入字体报错
  17. LeetCode 771 Jewels and Stones 解题报告
  18. python request 接口自动化设计
  19. 结合 spring 使用阿里 Druid 连接池配置方法
  20. mySql慢查询分析原因

热门文章

  1. .net core 学习笔记(4)-ViewComponent
  2. 【matlab】libsvm-3.18安装与使用
  3. Yii里获取当前controller和action的id
  4. Swift3.0语言教程使用占位符格式创建和初始化字符串
  5. dubbo配置文件xml校验报错
  6. 《机器学习实战》学习笔记——第2章 KNN
  7. [ACM_动态规划] 轮廓线动态规划——铺放骨牌(状态压缩1)
  8. Linux LVS Nginx HAProxy 优缺点
  9. u-boot-1.1.6移植之dm9000
  10. PHP 中变量的间接引用
  11. 淘宝npm镜像使用方法
  12. Spring集成RabbiMQ-Spring AMQP新特性
  13. 复习HTML+CSS(3)
  14. async await详解
  15. 日期类时间类,日期时间类,单例模式,装箱与拆箱,数字类随机数,BigDecimal总结
  16. canvas-4createPattern.html
  17. nightwatch-前端自动化测试工具安装
  18. c++中new的三种用法详细解析
  19. 06机器学习实战之SVM
  20. 定时任务 Wpf.Quartz.Demo.3