[文章目录]
Description
JSOI王国可以被看作为一个无穷大的二维平面，JYY一共建造了N个通信基站，第i个基站的坐标是(Xi,Yi)。每个基站有一个通信范围Ri。第i号基站会向所有到其距离不超过Ri的基站发送信息。每个基站升级到3G网络都会有一个收益Si，这个收益可能是正数（比如基站附近有个大城市，用户很多，赚的流量费也就很多了），也可能是负数（比如基站周围市场不佳，收益不能填补升级基站本身的投资）。此外，由于原有的使用2G网络系统的基站无法解析从升级成3G网络系统的基站所发来的信息（但是升级之后的基站是可以解析未升级基站发来的信息的），所以，JYY必须使得，在升级工作全部完成之后，所有使用3G网络的基站，其通信范围内的基站，也都是使用3G网络的。由于基站数量很多，你可以帮助JYY计算一下，他通过升级基站，最多能获得的收益是多少吗？1≤N≤500，1≤Ri≤20000，|Xi|,|Yi|,|Si|≤10^4
每个已选节点可及节点都必须选择。n<=500，网络流最小割求最大权闭合子图
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int inf=0x3f3f3f;
int xx[510],yy[510],r[510],w[510];
int n,sum,s,t;
int head[600],to[601000],nxt[601000],f[601000],cnt=1;
void add(int x,int y,int z)
{
to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt; f[cnt]=z;
to[++cnt]=x; nxt[cnt]=head[y]; head[y]=cnt; f[cnt]=0;
}
bool check(int x,int y)
{
return (xx[y]-xx[x])*(xx[y]-xx[x])+(yy[y]-yy[x])*(yy[y]-yy[x])<=r[x]*r[x];
}
queue<int>q;
int dis[600];
bool bfs()
{
while(!q.empty()) q.pop();
memset(dis,-1,sizeof dis);
q.push(s); dis[s]=0; int x;
while(!q.empty())
{
x=q.front(); q.pop();
for(int i=head[x];i;i=nxt[i])
if(f[i]>0&&dis[to[i]]<0)
{
dis[to[i]]=dis[x]+1;
if(to[i]==t) return true;
q.push(to[i]);
}
}
return false;
}
int dinic(int x,int flow)
{
if(x==t) return flow;
int xx,tmp=flow;
for(int i=head[x];i;i=nxt[i])
if(f[i]>0&&dis[to[i]]==dis[x]+1)
{
xx=dinic(to[i],min(f[i],tmp));
if(!xx) dis[to[i]]=-1;
f[i]-=xx; f[i^1]+=xx; tmp-=xx;
if(!tmp) break;
}
return flow-tmp;
}
int main()
{
scanf("%d",&n); s=n+1,t=s+1; int x;
for(int i=1;i<=n;++i)
{
scanf("%d%d%d%d",&xx[i],&yy[i],&r[i],&x);
if(x>0) add(s,i,x),sum+=x;
else add(i,t,-x);
}
for(int i=1;i<=n;++i)
{
for(int j=1;j<=n;++j)
if(j!=i&&check(i,j))
add(i,j,inf);
}
while(bfs()) sum-=dinic(s,inf);
printf("%d",sum);
return 0;
}