题目描述

Description

Input

Output

如果有可行解, 输出最小代价,否则输出NIE.

Sample Input

5
1 1 2 3
1 1 5 1
3 2 5 5
4 1 5 10
3 3 3 1

Sample Output

9

题目分析

最小费用流
s向每个学校连费用0 流量1的边
每个学校向区间连流量1 费用abs(c[i]-j)*c的边
区间每个点向t连费用0 流量1的边
然后跑网络流并判断是否满流即可

#include <cstdio>
#include <cstring>
#include <cmath>
#include <queue>
#include <algorithm>
using namespace std;
int n,m,s,t;
int head[10000],to[100000],val[100000],net[100000],flo[100000];
int tot=1;
int path[100000];
void add(int x,int y,int v,int c)
{
    net[++tot]=head[x],head[x]=tot,to[tot]=y,flo[tot]=v,val[tot]=c;
    net[++tot]=head[y];head[y]=tot,to[tot]=x,flo[tot]=0,val[tot]=-c;
}
int dis[10000],vis[10000];
int spfa()
{
    memset(dis,0x3f,sizeof dis);
    memset(vis,0,sizeof vis);
    queue<int>q;
    vis[s]=1,q.push(s),dis[s]=0;
    while(q.size())
    {
        int nmp=q.front();
        q.pop();
        vis[nmp]=0;
        for(int i=head[nmp];i;i=net[i])
            if(flo[i]>0&&dis[to[i]]>dis[nmp]+val[i])
            {
                dis[to[i]]=dis[nmp]+val[i];
                path[to[i]]=i^1;
                if(!vis[to[i]]) q.push(to[i]),vis[to[i]]=1;
            }
    }
    return dis[t]<0x3f3f3f3f;
}
void mincost()
{
    int ans=0,tmp=0;
    while(spfa())
    {
        tmp++;
        int minflow=1<<30;
        for(int i=t;i!=s;i=to[path[i]]) minflow=min(minflow,flo[path[i]^1]);
        for(int i=t;i!=s;i=to[path[i]])
        {
            flo[path[i]]+=minflow;
            flo[path[i]^1]-=minflow;
            ans+=val[path[i]^1]*minflow;
        }
    }
    if(tmp<n) printf("NIE");
    else printf("%d",ans);
}
int main()
{
    scanf("%d",&n);
    s=0,t=2*n+1;
    for(int i=1;i<=n;i++)
    {
        add(s,i,1,0);
        int a,b,x,c;
        scanf("%d%d%d%d",&x,&a,&b,&c);
        for(int j=a;j<=b;j++)
            add(i,n+j,1,abs(x-j)*c);
    }
    for(int i=1;i<=n;i++) add(i+n,t,1,0);
    mincost();
    return 0;
}