题解 P3440 [POI2006]SZK-Schools

· · 题解

为什么题解里面都是跑网络流啊喂。

下面提供一种二分图完美匹配的思路。

解题思路

题目最后提到要求最低成本，那就相当于是要跑二分图最小权完美匹配（说白了就是负权边跑最大权）

加边的时候（用的是邻接矩阵），我们枚举能更新到的编号范围，然后加边。

加完边之后就再跑一个 KM 的板子就好了。

关于什么时候输出 NIE：

只需在更新 del 的时候判断 del 是否还是 \infty 就好了。

如果还是 \infty ，那么就输出 NIE。

具体看代码理解，这里跑的是 dfs 版的 KM。

AC代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e2+1,inf=1e9+1;
int n;
int a[N],b[N];
int last[N],k[N]; 
int goal[N],slack[N];
struct edge{
    int to,ne,dis;
}e[N*N];
int adj[N],l;
inline void add(int x,int y,int z){e[++l].to=y,e[l].ne=adj[x],e[l].dis=z,adj[x]=l;}
int col[N],vis[N],mat[N];
int nn;
int flag=0;
int ans[N],sum;
int dfs(int x){
    vis[x]=1;
    for(register int i=adj[x];i;i=e[i].ne){
        int y=e[i].to,z=e[i].dis;
        if(vis[y]) continue;
        int dist=goal[x]+goal[y]-z;
        if(dist==0){
            vis[y]=1;
            if(!mat[y]||dfs(mat[y])){
                if(mat[y]) sum-=ans[y];
                ans[y]=z;
                sum+=z;
                mat[y]=x;
                return 1;
            } 
        }
        else slack[y]=min(slack[y],dist);
    }
    return 0;
}
inline int KM(){
    for(register int x=1;x<=n;x++){
        for(int i=adj[x];i;i=e[i].ne){
            int y=e[i].to,z=e[i].dis;
            goal[x]=max(goal[x],z);
        }
    }
    for(register int i=1;i<=n;i++){
        memset(slack,inf,sizeof(slack));
        while(1){
            memset(vis,0,sizeof(vis));
            if(dfs(i)) break;
            int del=inf;
            for(register int j=n+1;j<=n+nn;j++) if(!vis[j]) del=min(del,slack[j]);
            if(del==inf) return inf;
            for(register int j=1;j<=n;j++) if(vis[j]) goal[j]-=del;
            for(register int j=n+1;j<=n+nn;j++){
                if(vis[j]) goal[j]+=del;
                else slack[j]-=del;
            } 
        }
    }
    return sum;
}
signed main(){
    scanf("%lld",&n);
    for(register int i=1;i<=n;i++){
        scanf("%lld%lld%lld%lld",&last[i],&a[i],&b[i],&k[i]);
        nn=max(nn,max(a[i],b[i]));
        for(register int j=a[i];j<=b[i];j++) add(i,j+n,-k[i]*abs(last[i]-j));
        goal[i]=-inf;
    }
    int anss=KM();
    if(anss==inf) printf("NIE");
    else printf("%lld",-anss);
}