P3440 [POI2006]SZK-Schools

传送门

应该是很显然的费用流模型吧...

$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=,f=; char ch=getchar();

    while(ch<''||ch>'') { if(ch=='-') f=-; ch=getchar(); }

    while(ch>=''&&ch<='') { x=(x<<)+(x<<)+(ch^); ch=getchar(); }

    return x*f;

}

const int N=2e5+,M=2e6+,INF=1e9+;

int fir[N],from[M<<],to[M<<],val[M<<],cst[M<<],cntt=;

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]=; 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]=; dis[S]=; mif[S]=INF;

    while(!q.empty())

    {

        int x=q.front(); q.pop(); inq[x]=;

        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]=;

        }

    }

    return dis[T]<INF;

}

int ans;

inline void upd()

{

    for(int now=T,i=pre[T]; now!=S; now=to[i^],i=pre[now])

        val[i]-=mif[T],val[i^]+=mif[T];

    ans+=mif[T]*dis[T];

}

int n;

int main()

{

    int m,a,b,k;

    n=read(); S=,T=n+n+;

    for(int i=;i<=n;i++)

    {

        add(S,i,,);

        m=read(),a=read(),b=read(),k=read();

        add(i,n+m,,);

        for(int j=a;j<=b;j++)

            add(i,n+j,,abs(m-j)*k);

    }

    for(int i=;i<=n;i++) add(n+i,T,,);

    while(BFS()) upd();

    for(int i=fir[S];i;i=from[i])

        if(val[i]) { printf("NIE"); return ; }

    printf("%d",ans);

    return ;

}