应该是很显然的费用流模型吧...
$S$ 向所有学校连边，流量为 $1$，费用为 $0$（表示每个学校要选一个编号）
学校向范围内的数字连边，流量为 $1$，费用为 $c|m-m'|$（表示学校选择编号的花费）
注意学校向原来的数字连边，流量 $1$，费用 $0$（表示学校可以不改变编号）
所有数字向 $T$ 连边，流量为 $1$（每个数字只能给一个学校）
那么一个流就代表一个学校的选择
然后最小费用最大流就是答案
记得判一下无解就好了
#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> #include<cmath> #include<queue> using namespace std; typedef long long ll; inline int read() { int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f; } const int N=2e5+7,M=2e6+7,INF=1e9+7; int fir[N],from[M<<1],to[M<<1],val[M<<1],cst[M<<1],cntt=1; inline void add(int a,int b,int c,int d) { from[++cntt]=fir[a]; fir[a]=cntt; to[cntt]=b; val[cntt]=c; cst[cntt]=d; from[++cntt]=fir[b]; fir[b]=cntt; to[cntt]=a; val[cntt]=0; cst[cntt]=-d; } int dis[N],mif[N],pre[N],S,T; queue <int> q; bool inq[N]; bool BFS() { for(int i=S;i<=T;i++) dis[i]=INF; q.push(S); inq[S]=1; dis[S]=0; mif[S]=INF; while(!q.empty()) { int x=q.front(); q.pop(); inq[x]=0; for(int i=fir[x];i;i=from[i]) { int &v=to[i]; if( !val[i] || dis[v]<=dis[x]+cst[i] ) continue; dis[v]=dis[x]+cst[i]; pre[v]=i; mif[v]=min(mif[x],val[i]); if(!inq[v]) q.push(v),inq[v]=1; } } return dis[T]<INF; } int ans; inline void upd() { for(int now=T,i=pre[T]; now!=S; now=to[i^1],i=pre[now]) val[i]-=mif[T],val[i^1]+=mif[T]; ans+=mif[T]*dis[T]; } int n; int main() { int m,a,b,k; n=read(); S=0,T=n+n+1; for(int i=1;i<=n;i++) { add(S,i,1,0); m=read(),a=read(),b=read(),k=read(); add(i,n+m,1,0); for(int j=a;j<=b;j++) add(i,n+j,1,abs(m-j)*k); } for(int i=1;i<=n;i++) add(n+i,T,1,0); while(BFS()) upd(); for(int i=fir[S];i;i=from[i]) if(val[i]) { printf("NIE"); return 0; } printf("%d",ans); return 0; }