codeforces1146G Zoning Restrictions

题面

题意

在一条路上有标号为1-n的n座房子,每座房子最高为h,若一座房子的高度为x,则这座房子的收益为x*x,有m条限制,每条限制表示如果在l-r之间的所有房子的最大高度超过hi,则罚款ci.问所有房子的最大收益是多少.

做法

一道经典的最小割.

假设一开始所有房子的高度均为h,初始答案为 n ∗ h ∗ h n*h*h n∗h∗h,可以对每座房子的每一种取值建一个点,并且这样连边S->0->1->2->3->4…h->T,第i个点到第i+1个点的边的权值为 h ∗ h − i ∗ i h*h-i*i h∗h−i∗i,割掉这条边就表示房子的高度为i.对每一条限制也新建一个点x,并且x向T连一条边,边权为罚款金额,割掉这条边就表示可以不交这一项罚款,并从每个受限制的房子的相应高度代表的点向x连流量为INF的边,然后 n ∗ h ∗ h − n*h*h- n∗h∗h−最小割即为答案.

代码

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
#define N 3010
#define M 1001000
using namespace std;

int n,m,tot,S,T,h,ans,bb=1,first[N],cur[N],deep[N];
struct Bn
{
	int to,next,quan;
}bn[M];
queue<int>que;

inline void add(int u,int v,int w)
{
	bb++;
	bn[bb].to=v;
	bn[bb].quan=w;
	bn[bb].next=first[u];
	first[u]=bb;
}

inline void ad(int u,int v,int w)
{
	add(u,v,w);
	add(v,u,0);
}

inline bool bfs()
{
	memset(deep,0,sizeof(deep));
	int p,q;
	deep[S]=1;
	que.push(S);
	for(;!que.empty();)
	{
		q=que.front();
		que.pop();
		for(p=first[q];p!=-1;p=bn[p].next)
		{
			int t=bn[p].to;
			if(deep[t] || !bn[p].quan) continue;
			deep[t]=deep[q]+1;
			que.push(t);
		}
	}
	return deep[T];
}

int dfs(int now,int mn)
{
	if(now==T) return mn;
	int res;
	for(int &p=cur[now];p!=-1;p=bn[p].next)
	{
		int t=bn[p].to;
		if(deep[t]!=deep[now]+1 || !bn[p].quan) continue;
		res=dfs(t,min(mn,bn[p].quan));
		if(res)
		{
			bn[p].quan-=res;
			bn[p^1].quan+=res;
			return res;
		}
	}
	return 0;
}

int main()
{
	memset(first,-1,sizeof(first));
	int i,j,p,q,o,t;
	cin>>n>>h>>m;
	tot=(h+1)*n;
	T=tot+m+1;
	for(i=1;i<=n;i++)
	{
		for(j=(i-1)*(h+1)+1;j<i*(h+1);j++) ad(j,j+1,h*h-(j-(i-1)*(h+1)-1)*(j-(i-1)*(h+1)-1));
		ad(S,(i-1)*(h+1)+1,INF);
	}
	for(i=1;i<=m;i++)
	{
		scanf("%d%d%d%d",&p,&q,&o,&t);
		if(o>=h) continue;
		ad(i+tot,T,t);
		for(j=p;j<=q;j++) ad((j-1)*(h+1)+o+2,i+tot,INF);
	}
	for(;bfs();)
	{
		memcpy(cur,first,sizeof(first));
		for(t=dfs(S,INF);t;ans+=t,t=dfs(S,INF));
	}
	cout<<h*h*n-ans;
}