BZOJ5037[Jsoi2014]电信网络——最大权闭合子图-白红宇

BZOJ5037[Jsoi2014]电信网络——最大权闭合子图

阅读量：6271 次

发布时间：2019-06-22

本文共 1771 字，大约阅读时间需要 5 分钟。

题目描述

JYY创建的电信公司，垄断着整个JSOI王国的电信网络。JYY在JSOI王国里建造了很多的通信基站。目前所有的基站

都是使用2G网络系统的。而现在3G时代已经到来了，JYY在思考，要不要把一些基站升级成3G网络的呢？JSOI王国

可以被看作为一个无穷大的二维平面，JYY一共建造了N个通信基站，第i个基站的坐标是(Xi,Yi)。每个基站有一个

通信范围Ri。第i号基站会向所有到其距离不超过Ri的基站发送信息。每个基站升级到3G网络都会有一个收益Si，

这个收益可能是正数（比如基站附近有个大城市，用户很多，赚的流量费也就很多了），也可能是负数（比如基站

周围市场不佳，收益不能填补升级基站本身的投资）。此外，由于原有的使用2G网络系统的基站无法解析从升级成

3G网络系统的基站所发来的信息（但是升级之后的基站是可以解析未升级基站发来的信息的），所以，JYY必须使

得，在升级工作全部完成之后，所有使用3G网络的基站，其通信范围内的基站，也都是使用3G网络的。由于基站数

量很多，你可以帮助JYY计算一下，他通过升级基站，最多能获得的收益是多少吗？

输入

第一行一个整数N；

接下来N行，每行4个整数，Xi，Yi，Ri，Si，表示处在(Xi,Yi)的基站的通信

范围是Ri，升级可以获得的收益是Si。

数据满足任意两个基站的坐标不同。

1≤N≤500，1≤Ri≤20000，|Xi|,|Yi|,|Si|≤10^4。

输出

输出一行一个整数，表示可以获得的最大收益。

样例输入

0 1 7 10

0 -1 7 10

5 0 1 -15

10 0 6 10

15 1 2 -20

样例输出

【样例说明】

我们可以将前三座基站升级成 3G 网络，以获得最佳收益。

根据题意要求，显然就是求最大权闭合子图，将源点连向正收益的点，流量为收益；负收益点连向汇点，流量为收益的相反数。暴力枚举两个点，如果$j$在$i$的范围内，那么就将$i$向$j$连边，流量为$INF$。答案就是正收益之和$-$最小割

#include
      
       #include
       #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #define INF 1000000000using namespace std;int head[600];int next[600000];int to[600000];int val[600000];int d[600];int q[600];int n;int x[600];int y[600];int r[600];int s[600];int tot=1;int ans;int S,T;void add(int x,int y,int v){ tot++; next[tot]=head[x]; head[x]=tot; to[tot]=y; val[tot]=v; tot++; next[tot]=head[y]; head[y]=tot; to[tot]=x; val[tot]=0;}bool bfs(int S,int T){ int r=0; int l=0; memset(q,0,sizeof(q)); memset(d,-1,sizeof(d)); q[r++]=S; d[S]=0; while(l
                 
                  0) { ans+=s[i]; add(S,i,s[i]); } else { add(i,T,-s[i]); } } for(int i=1;i<=n;i++) { for(int j=1;j<=n;j++) { if(check(i,j)) { add(i,j,INF); } } } dinic(); printf("%d",ans);}

转载于:https://www.cnblogs.com/Khada-Jhin/p/10574560.html

你可能感兴趣的文章

网络编程懒人入门(九)：通俗讲解，有了IP地址，为何还要用MAC地址？