题解 P1791 【[国家集训队]人员雇佣】

· · 题解

这题只要注意三点

1.区间(a,b)a有可能大于b

2.端点重合不算包含

3.区间从-999开始

AC代码：

#include<bits/stdc++.h>
using namespace std;
inline long long read(){
    long long ans=0,fh=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-')
            fh=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
        ans=(ans<<1)+(ans<<3)+ch-'0',ch=getchar();
    return ans*fh;
}
const int maxn=1e4,maxm=5e6,inf=0x7fffffff;
int n,m,a,b,c,cc[maxn],cur[maxn],head[maxn],nex[maxm],v[maxm],s,t;
int num=1;
long long ans,siz[maxn],fee,w[maxm];
queue<int>q;
int bh(int x,int y){return n+(x-1)*n+y;}
void add(int x,int y,long long z){
    v[++num]=y;
    w[num]=z;
    nex[num]=head[x];
    head[x]=num;
    v[++num]=x;
    w[num]=0;
    nex[num]=head[y];
    head[y]=num;
}
bool bfs(){
    memset(cc,0,sizeof(cc));
    cc[s]=1;
    q.push(s);
    while(!q.empty()){
        int now=q.front();
        q.pop();
        for(int i=head[now];i;i=nex[i])
            if(w[i]&&!cc[v[i]])
                cc[v[i]]=cc[now]+1,q.push(v[i]);
    }
    return cc[t];
}
long long dfs(int x,long long ll){
    if(x==t)
        return ll;
    for(int &i=cur[x];i;i=nex[i])
        if(w[i]&&cc[v[i]]==cc[x]+1){
            int pp=dfs(v[i],ll>w[i]?w[i]:ll);
            if(pp){
                w[i]-=pp;
                w[i^1]+=pp;
                return pp;
            }
        }
    return 0;
}
void dinic(){
    long long maxl=0,ll;
    while(bfs()){
        memcpy(cur,head,sizeof(cur));
        while(ll=dfs(s,inf))
            maxl+=ll;
    }
    printf("%d\n",ans-maxl);
}
int main(){
    n=read();s=0;t=n+1;
    for(int i=1;i<=n;i++)
        a=read(),add(i,t,a);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            fee=read();
            siz[i]+=fee;
            add(i,j,fee*2);
        }
        add(s,i,siz[i]);
        ans+=siz[i];
    }
    dinic();
    return 0;
}