[洛谷 3440][POI2006]SZK-Schools

题目链接

https://www.luogu.com.cn/problem/P3440

题解

对于这样的匹配类问题，往往要想到建立网络流的模型来解决。

我们将学校放到左边，每个新编号放到右边，将学校与其所有接受的新编号之间连一条流量为 \(1\) 的边，费用为改编号的开销。

从超级源点向左边所有点连一条流量为 \(1\) ，费用为 \(0\) 的边；从超级汇点向右边所有点连一条流量为 \(1\) ，费用为 \(0\) 的边（要确保每个编号恰好被选一次），跑最小费用最大流即可。

如果最大流不到 \(n\) 则无解，否则求出的最小费用即为答案。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
struct graph
{
 #define INF 0x3f3f3f3f
 struct edge
 {
  int v,w,c,next;
 }e[100005];
 struct node
 {
  int v,e;
 }p[10005];
 int head[505],dist[505],vis[505],s,t,cnt;
 void addedge(int u,int v,int w,int c)
 {
  e[++cnt].v=v;
  e[cnt].w=w;
  e[cnt].c=c;
  e[cnt].next=head[u];
  head[u]=cnt;
 }
 void init(int S,int T,int n)
 {
  s=S,t=T;
  cnt=1;
  for(int i=1;i<=n;i++)
  {
   addedge(s,i,1,0);
   addedge(i,s,0,0);
   addedge(i+n,t,1,0);
   addedge(t,i+n,0,0);
  }
 }
 bool spfa()
 {
  queue<int> q;
  memset(dist,INF,sizeof(dist));
  q.push(s);
  dist[s]=0;
  vis[s]=1;
  while(!q.empty())
  {
   int cur=q.front();
   q.pop();
   vis[cur]=0;
   for(int i=head[cur];i;i=e[i].next)
    if(e[i].w&&dist[cur]+e[i].c<dist[e[i].v])
    {
     dist[e[i].v]=dist[cur]+e[i].c;
     p[e[i].v].v=cur;
     p[e[i].v].e=i;
     if(!vis[e[i].v])
     {
      vis[e[i].v]=1;
      q.push(e[i].v);
     }
    }
  }
  return dist[t]!=INF;
 }
 pair<int,int> mcmf()
 {
  int maxw=0,minf=0;
  while(spfa())
  {
   int minw=INF;
   for(int i=t;i!=s;i=p[i].v)
    minw=min(minw,e[p[i].e].w);
   for(int i=t;i!=s;i=p[i].v)
   {
    e[p[i].e].w-=minw;
    e[p[i].e^1].w+=minw;
   }
   maxw+=minw;
   minf+=minw*dist[t];
  }
  return make_pair(maxw,minf);
 }
}g;
int main()
{
 int n;
 scanf("%d",&n);
 g.init(2*n+1,2*n+2,n);
 for(int i=1;i<=n;i++)
 {
  int m,a,b,k;
  scanf("%d%d%d%d",&m,&a,&b,&k);
  for(int j=a;j<=b;j++)
  {
   int c=abs(m-j)*k;
   g.addedge(i,j+n,1,c);
   g.addedge(j+n,i,0,-c);
  }
 }
 auto ans=g.mcmf();
 if(ans.first!=n)puts("NIE");
 else printf("%d\n",ans.second);
 return 0;
}