【BZOJ1520】[POI2006]Szk-Schools KM算法

【BZOJ1520】[POI2006]Szk-Schools

Description

Input

Output

如果有可行解, 输出最小代价,否则输出NIE.

Sample Input

5
1 1 2 3
1 1 5 1
3 2 5 5
4 1 5 10
3 3 3 1

Sample Output

9

题解：二分图最小权匹配裸题，可以直接无脑费用流，不过这里就当复习一下KM算法了。

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

}