P3440 [POI2006]SZK-Schools

題目連結

題解：

暴力連邊，然後直接最小費用最大流就OK了

AC代碼：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
#include<ext/rope>
using namespace std;
using namespace __gnu_cxx;
#define LL long long
const int MAXN = 2000+50;
const int MAXM = 2e6+50;
const int MOD = 1e9+7;
const int INF = 0x3f3f3f3f;
int n,m,s,t,tot=1,maxflow,res,head[MAXN],nxt[MAXM],w[MAXM],to[MAXM],co[MAXM];
int dis[MAXN],vis[MAXN],pre[MAXN],flow[MAXN];
inline void ade(int u,int v,int ww,int cost){
    to[++tot]=v; w[tot]=ww; co[tot]=cost; nxt[tot]=head[u]; head[u]=tot;
}
inline void add(int u,int v,int w,int cost){ ade(u,v,w,cost); ade(v,u,0,-cost); }
inline int spfa(){
    memset(dis,INF,sizeof(dis)); memset(vis,0,sizeof(vis));
    queue<int> que; que.push(s); dis[s]=0; vis[s]=1; flow[s]=INF;
    while(!que.empty()){
        int u=que.front(); que.pop(); vis[u]=0;
        for(int i=head[u];i;i=nxt[i]){
            int v=to[i];
            if(w[i] && dis[u]+co[i]<dis[v]){
                dis[v]=dis[u]+co[i]; pre[v]=i;
                flow[v]=min(flow[u],w[i]);
                if(!vis[v]) vis[v]=1,que.push(v);
            }
        }
    }
    return dis[t]!=INF;
}
inline void update(){
    int x=t;
    while(x!=s){
        int i=pre[x];
        w[i]-=flow[t]; w[i^1]+=flow[t]; x=to[i^1];
    }
    maxflow+=flow[t]; res+=dis[t]*flow[t];
}
inline void EK(){
    while(spfa()) update();
}
signed main(){
#ifndef ONLINE_JUDGE
    freopen("C:\\Users\\Administrator\\Desktop\\in.txt","r",stdin);
#endif // ONLINE_JUDGE
    scanf("%d",&n); s=0,t=2*n+1;
    for(int i=1;i<=n;i++) add(s,i,1,0);
    for(int i=1;i<=n;i++){
        int m,a,b,kk; scanf("%d%d%d%d",&m,&a,&b,&kk);
        for(int j=a;j<=b;j++)
            add(i,j+n,1,abs(j-m)*kk);
    }
    for(int i=1;i<=n;i++) add(i+n,t,1,0);
    EK();
    if(maxflow==n) printf("%d\n",res);
    else puts("NIE");
    return 0;
}