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;
}