【BZOJ1520】[POI2006]Szk-Schools

#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>using namespace std;int n,ans;int xa[210],ya[210],xb[210],yb[210],va[210],vb[210],from[210],la[210],lb[210],temp,A[210],B[210],dis[210][210];int dfs(int x){	va[x]=1;	for(int i=A[x];i<=B[x];i++)	{		if(!vb[i]&&!(la[x]+lb[i]-dis[x][i]))		{			vb[i]=1;			if(!from[i]||dfs(from[i]))			{				from[i]=x;				return 1;			}		}	}	return 0;}inline int rd(){	int ret=0,f=1;	char gc=getchar();	while(gc<‘0‘||gc>‘9‘)	{if(gc==‘-‘)f=-f;	gc=getchar();}	while(gc>=‘0‘&&gc<=‘9‘)	ret=ret*10+gc-‘0‘,gc=getchar();	return ret*f;}int main(){	scanf("%d",&n);	int i,j,k,a,b;	memset(la,0x80,sizeof(la));	for(i=1;i<=n;i++)	{		a=rd(),A[i]=rd(),B[i]=rd(),b=rd();		for(j=A[i];j<=B[i];j++)	dis[i][j]=-abs(j-a)*b,la[i]=max(la[i],dis[i][j]);	}	for(i=1;i<=n;i++)	{		while(1)		{			memset(va,0,sizeof(va));			memset(vb,0,sizeof(vb));			if(dfs(i))	break;			temp=1<<30;			for(j=1;j<=n;j++)	if(va[j])				for(k=A[j];k<=B[j];k++)	if(!vb[k])					temp=min(temp,la[j]+lb[k]-dis[j][k]);			if(temp==1<<30)			{				printf("NIE");				return 0;			}			for(j=1;j<=n;j++)	if(va[j])	la[j]-=temp;			for(j=1;j<=n;j++)	if(vb[j])	lb[j]+=temp;		}	}	for(i=1;i<=n;i++)	ans+=la[i]+lb[i];	printf("%d",-ans);	return 0;}