bzoj1497最大闭权图基础题
2024-10-09 03:25:40
1497: [NOI2006]最大获利
Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 5485 Solved: 2661
[Submit][Status][Discuss]
Description
新的技术正冲击着手机通讯市场,对于各大运营商来说,这既是机遇,更是挑战。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公司可以有选择的建立一些中转站(投入成本),为一些用户提供服务并获得收益(获益之和)。那么如何选择最终建立的中转站才能让公司的净获利最大呢?(净获利 = 获益之和 - 投入成本之和)
Input
输入文件中第一行有两个正整数N和M 。第二行中有N个整数描述每一个通讯中转站的建立成本,依次为P1, P2, …, PN 。以下M行,第(i + 2)行的三个数Ai, Bi和Ci描述第i个用户群的信息。所有变量的含义可以参见题目描述。
Output
你的程序只要向输出文件输出一个整数,表示公司可以得到的最大净获利。
Sample Input
5 5
1 2 3 4 5
1 2 3
2 3 4
1 3 3
1 4 2
4 5 3
1 2 3 4 5
1 2 3
2 3 4
1 3 3
1 4 2
4 5 3
Sample Output
4
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int N=;
const int M=;
const int INF=;
int head[N+M],dis[N+M];
int tot,n,m,st,ed,val;
struct node{
int v,next,w;
}e[M<<];
void add(int u,int v,int w){
e[tot].v=v;e[tot].w=w;e[tot].next=head[u];head[u]=tot++;
e[tot].v=u;e[tot].w=;e[tot].next=head[v];head[v]=tot++;
}
bool bfs(){
queue<int>Q;
for(int i=;i<=ed;++i) dis[i]=-;
dis[st]=;
Q.push(st);
while(!Q.empty()) {
int u=Q.front();
Q.pop();
for(int i=head[u];i+;i=e[i].next){
if(dis[e[i].v]!=-||e[i].w<=) continue;
dis[e[i].v]=dis[u]+;
if(e[i].v==ed) return true;
Q.push(e[i].v);
}
}
return false;
}
int dinic(int u,int low){
if(u==ed||!low) return low;
int ans=low,a;
for(int i=head[u];i+;i=e[i].next){
int v=e[i].v;
if(e[i].w>&&dis[v]==dis[u]+&&(a=dinic(v,min(ans,e[i].w)))){
ans-=a;
e[i].w-=a;
e[i^].w+=a;
if(!ans) return low;
}
}
if(ans==low) dis[u]=-;
return low-ans;
}
int main(){
scanf("%d%d",&n,&m);
tot=st=,ed=n+m+;
for(int i=;i<=ed;++i) head[i]=-;
for(int i=;i<=n;++i){
scanf("%d",&val);
add(i+m,ed,val);
}
int a,b,c,ans=;
for(int i=;i<=m;++i){
scanf("%d%d%d",&a,&b,&c);
ans+=c;
add(,i,c);
add(i,a+m,INF);
add(i,b+m,INF);
}
while(bfs()) ans-=dinic(st,INF);
printf("%d\n",ans);
}
最新文章
- AJAX简介
- Swift语言快速入门
- Deployment options
- Paxos算法细节详解(一)--通过现实世界描述算法
- poj2568
- 基于Jquery Validate 的表单验证
- Windows 7各版本的主要功能区别是什么 有何不同
- rsync安装及其配置
- zabbix杂文二
- 关于python使用cv画矩形并填充颜色同时填充文字
- Java 缩写总结
- CSS 选择器的兼容性
- day037 行记录的操作
- Vue:v-on自定义事件
- sql乘法函数实现方式
- LocalBroadcastManager 的使用
- 如何统计TFS代码库中的团队项目所占用的磁盘空间
- react native 学习之 native modules
- PythonWeb 服务部署文档及迁移到Linux相关
- List 集合remove问题
热门文章
- 为物联网而生:高性能时间序列数据库HiTSDB商业化首发!
- Mysql 查看被锁住的表
- Apache2.4 根目录修改
- C++编程入门题目--No.4
- 数学--数论--HDU 1792 A New Change Problem (GCD+打表找规律)
- 信息奥赛一本通1486: CH 6202 黑暗城堡 最短路径生成树计数
- 学习HTML
- ASP.NET Core 包管理工具(4)
- 深度学习环境搭建:window10+CUDA10.0+CUDNN+pytorch1.2.0
- 区间dp E - Multiplication Puzzle POJ - 1651