BZOJ1479 最大获利
程序员文章站
2022-07-15 12:24:10
...
题目描述
新的技术正冲击着手机通讯市场,对于各大运营商来说,这既是机遇,更是挑战。THU 集团旗下的 CS&T 通讯公司在新一代通讯技术血战的前夜,需要做太多的准备工作,仅就站址选择一项,就需要完成前期市场研究、站址勘测、最优化等项目。
在前期市场调查和站址勘测之后,公司得到了一共 N 个可以作为通讯信号中转站的地址,而由于这些地址的地理位置差异,在不同的地方建造通讯中转站需要投入的成本也是不一样的,所幸在前期调查之后这些都是已知数据:建立第 i个通讯中转站需要的成本为 P_iPi (1≤i≤N)。
另外公司调查得出了所有期望中的用户群,一共 M 个。关于第 i 个用户群的信息概括为 A_iAi , B_iBi 和 C_iCi :这些用户会使用中转站 A i 和中转站 B i 进行通讯,公司可以获益 C_iCi 。(1≤i≤M, 1≤A_iAi , B_iBi ≤N)
THU 集团的 CS&T 公司可以有选择的建立一些中转站(投入成本),为一些用户提供服务并获得收益(获益之和)。那么如何选择最终建立的中转站才能让公司的净获利最大呢?(净获利 = 获益之和 – 投入成本之和)
解析:最大权闭合子图的基本应用。源点向所有用户连流量为收益的边,所有中转站向汇点连流量为成本的边,用户所需要的中转站,由用户向需要的中转站连inf边,最后用总收益减去最小割(最大流)就是答案,原因很简单,如果割掉用户的边,那么就舍弃掉一部分收益,可以看做损失,如果割掉中转站的边,那么就付出一定代价,可以看做损失,又因为不会割掉INF的边,所以就巧妙的解决了选A必须选B的问题。
代码:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define inf 1e9
using namespace std;
struct point
{
int next;
int dis;
int to;
}e[1000010];
int n,m,num,s,t,a,b,c,ans;
int head[600010],h[60010];
void add(int from,int to,int dis)
{
e[num].next=head[from];
e[num].to=to;
e[num].dis=dis;
head[from]=num++;
}
bool bfs()
{
memset(h,0,sizeof(h));
h[s]=1;
queue<int>q;
q.push(s);
while(!q.empty())
{
int x=q.front();
q.pop();
for(int i=head[x];i!=0;i=e[i].next)
{
int to=e[i].to;
if(!h[to]&&e[i].dis)
{
q.push(to);
h[to]=h[x]+1;
}
}
}
return h[t];
}
int dfs(int x,int dis)
{
if(x==t)
return dis;
int sum=0;
for(int i=head[x];i!=0;i=e[i].next)
{
int to=e[i].to;
if(h[to]==h[x]+1&&e[i].dis)
{
int diss=dfs(to,min(dis,e[i].dis));
if(diss>0)
{
sum+=diss;
dis-=diss;
e[i].dis-=diss;
e[i^1].dis+=diss;
if(!dis)
break;
}
}
}
if(!sum)
h[x]=-1;
return sum;
}
int dinic()
{
int tot=0;
while(bfs())
tot+=dfs(s,inf);
return tot;
}
int main()
{
scanf("%d%d",&n,&m);
t=m+n+1;
for(int i=1;i<=n;i++)
{
int w;
scanf("%d",&w);
add(i,0,0);
add(0,i,w);
}
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&a,&b,&c);
ans+=c;
add(i+n,a,0);
add(a,i+n,inf);
add(i+n,b,0);
add(b,i+n,inf);
add(t,i+n,0);
add(i+n,t,c);
}
printf("%d",ans-dinic());
return 0;
}