BZOJ 5037 [JSOI2014]电信网络

题目大意

给你一些点，每个点如果使用就会得到一个权值（正或负），如果一个点选中那么必须选择特定的另外数个点。求最大获利

23333

黑体字就是题解= =

直接最大权闭合子图，S连正权点权值为点权，负权点连T权值为点权相反数，点间连边正常，权值为INF。之后用正权点和减去最小割就可以了。

#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define INF 1000000000
#define maxN 510
#define maxM 300010
int n,x[maxN],y[maxN],r[maxN],s[maxN],depth[maxN],ans,S,T;
int to[maxM<<1],nex[maxM<<1],val[maxM<<1],head[maxN],tot=1;
queue<int>q;
int pf(int tx) {return tx*tx;}
bool check(int tx,int ty) {return pf(x[tx]-x[ty])+pf(y[tx]-y[ty])<pf(r[tx]);}
void addedge(int tx,int ty,int tz) {to[++tot]=ty,nex[tot]=head[tx],head[tx]=tot,val[tot]=tz,to[++tot]=tx,nex[tot]=head[ty],head[ty]=tot,val[tot]=0;}
bool bfs()
{
	memset(depth,-1,sizeof depth);
	depth[S]=0;
	while(!q.empty()) q.pop();
	q.push(S);
	while(!q.empty())
	{
		int tmp=q.front();
		q.pop();
		for(int i=head[tmp];i;i=nex[i])
			if(val[i]&&depth[to[i]]==-1)
			{
				depth[to[i]]=depth[tmp]+1;
				if(to[i]==T) return true;
				q.push(to[i]);
			}
	}
	return false;
}
int dinic(int pos,int left)
{
	if(pos==T) return left;
	int nleft=left;
	for(int i=head[pos];i;i=nex[i])
		if(val[i]&&depth[to[i]]==depth[pos]+1)
		{
			int tmp=dinic(to[i],min(nleft,val[i]));
			if(!tmp) depth[to[i]]=-1;
			nleft-=tmp;
			val[i]-=tmp;
			val[i^1]+=tmp;
			if(!nleft) break;
		}
	return left-nleft;
}
int main()
{
	scanf("%d",&n);
	S=0,T=n+1;
	for(int i=1;i<=n;++i) scanf("%d%d%d%d",x+i,y+i,r+i,s+i);
	for(int i=1;i<=n;++i)
	{
		if(s[i]>0) ans+=s[i],addedge(S,i,s[i]);
		else addedge(i,T,-s[i]);
	}
	for(int i=1;i<=n;++i)
		for(int j=1;j<=n;++j)
			if(i!=j&&check(i,j)) addedge(i,j,INF);
	while(bfs()) ans-=dinic(S,INF);
	printf("%d",ans);
}