对于每座学校，都将它与可更换的值连上一条容量为1，权值为c*|a-m|的边。
然后跑一遍费用流就行了。
#include <cstdio> #include <queue> #include <cstring> #include <algorithm> using namespace std; const int M=1000005,N=2005,Inf=1<<29; int n,m,a,b,c; struct edge{ int nxt,to,ro,c,flow; }e[M]; int s,t; int tot,head[N]; inline void add(int u,int v,int ro,int c) { e[tot].to=v,e[tot].ro=ro,e[tot].c=c,e[tot].nxt=head[u],head[u]=tot,tot++; e[tot].to=u,e[tot].ro=0,e[tot].c=-c,e[tot].nxt=head[v],head[v]=tot,tot++; } bool vis[N]; int dis[N],prp[N],prd[N],qaq[N]; inline bool spfa(int s,int t) { register int i,j; for (i=0;i<=n+n+1;i++) dis[i]=Inf; vis[s]=1;dis[s]=0;prp[s]=prd[s]=1,qaq[s]=Inf; queue<int> q; q.push(s); while (!q.empty()) { int x=q.front(); q.pop(); vis[x]=false; for (i=head[x];i!=-1;i=e[i].nxt) { if (e[i].ro>e[i].flow&&dis[x]+e[i].c<dis[e[i].to]) { dis[e[i].to]=dis[x]+e[i].c; prp[e[i].to]=i; qaq[e[i].to]=min(qaq[x],e[i].ro-e[i].flow); prd[e[i].to]=x; if (!vis[e[i].to]) q.push(e[i].to),vis[e[i].to]=1;; } } } return dis[t]==Inf?0:1; } inline void MCMF(int s,int t) { int flow=0,cost=0; while (spfa(s,t)) { flow+=qaq[t]; cost+=dis[t]*qaq[t]; for (int i=t;i!=s;i=prd[i]) { e[prp[i]].flow+=qaq[t]; e[prp[i]^1].flow-=qaq[t]; //printf("%d ",i); } //printf("\n"); } if (flow<n) printf("NIE"); else printf("%d",cost); } int main() { register int i,j; scanf("%d",&n); memset(head,-1,sizeof(head)); s=0,t=n+n+1; for (i=1;i<=n;i++) { add(s,i,1,0); add(i+n,t,1,0); scanf("%d %d %d %d",&m,&a,&b,&c); for (j=a;j<=b;j++) add(i,n+j,1,c*abs(m-j)); } MCMF(s,t); }
