自动搬运

查看原文

来自洛谷，原作者为

	银河AI **

搬运于2025-08-24 21:49:01，当前版本为作者最后更新于2021-06-23 12:57:43，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

为什么题解里面都是跑网络流啊喂。

下面提供一种二分图完美匹配的思路。

解题思路

题目最后提到要求最低成本，那就相当于是要跑二分图最小权完美匹配（说白了就是负权边跑最大权）

加边的时候（用的是邻接矩阵），我们枚举能更新到的编号范围，然后加边。

加完边之后就再跑一个 KM 的板子就好了。

关于什么时候输出 NIE：

只需在更新 $del$ 的时候判断 $del$ 是否还是 $\infty$ 就好了。

如果还是 $\infty$ ，那么就输出 NIE。

具体看代码理解，这里跑的是 dfs 版的 KM。

AC代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e2+1,inf=1e9+1;
int n;
int a[N],b[N];
int last[N],k[N]; 
int goal[N],slack[N];
struct edge{
	int to,ne,dis;
}e[N*N];
int adj[N],l;
inline void add(int x,int y,int z){e[++l].to=y,e[l].ne=adj[x],e[l].dis=z,adj[x]=l;}
int col[N],vis[N],mat[N];
int nn;
int flag=0;
int ans[N],sum;
int dfs(int x){
	vis[x]=1;
	for(register int i=adj[x];i;i=e[i].ne){
		int y=e[i].to,z=e[i].dis;
		if(vis[y]) continue;
		int dist=goal[x]+goal[y]-z;
		if(dist==0){
			vis[y]=1;
			if(!mat[y]||dfs(mat[y])){
				if(mat[y]) sum-=ans[y];
				ans[y]=z;
				sum+=z;
				mat[y]=x;
				return 1;
			} 
		}
		else slack[y]=min(slack[y],dist);
	}
	return 0;
}
inline int KM(){
	for(register int x=1;x<=n;x++){
		for(int i=adj[x];i;i=e[i].ne){
			int y=e[i].to,z=e[i].dis;
			goal[x]=max(goal[x],z);
		}
	}
	for(register int i=1;i<=n;i++){
		memset(slack,inf,sizeof(slack));
		while(1){
			memset(vis,0,sizeof(vis));
			if(dfs(i)) break;
			int del=inf;
			for(register int j=n+1;j<=n+nn;j++) if(!vis[j]) del=min(del,slack[j]);
			if(del==inf) return inf;
			for(register int j=1;j<=n;j++) if(vis[j]) goal[j]-=del;
			for(register int j=n+1;j<=n+nn;j++){
				if(vis[j]) goal[j]+=del;
				else slack[j]-=del;
			} 
		}
	}
	return sum;
}
signed main(){
	scanf("%lld",&n);
	for(register int i=1;i<=n;i++){
		scanf("%lld%lld%lld%lld",&last[i],&a[i],&b[i],&k[i]);
		nn=max(nn,max(a[i],b[i]));
		for(register int j=a[i];j<=b[i];j++) add(i,j+n,-k[i]*abs(last[i]-j));
		goal[i]=-inf;
	}
	int anss=KM();
	if(anss==inf) printf("NIE");
	else printf("%lld",-anss);
}