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

· · 题解

竟然没有这题的题解，水一发qwq

最小割模型

1.题意:

　a.选择每个人有一个代价A_i；

　b.如果有两个人同时选择就可以获得收益E_{i,j}

　c.如果一个人选择另一个不选会产生代价E_{i,j}

2.解法

　　a,b两条就是典型的最小割模型，从S向每个人连边流量为这人可以带来的收益\Sigma_{j=1}^{n} E_{i,j}，用ans记录总收益，再从人向T连边表示代价A_i，用ans-minc（这样如果割掉人到T的边代表选这个人并支付代价，如果割掉S到人的边代表舍弃收益，不支付代价）得到的就是最大的收益

　　考虑c条件，那么我们对于每对i,j都再新建一条从i到j的边，流量为E_{i,j}<<1这样如果选一个不选另一个的话这条边就会断掉（造成代价）,c条件就能满足了

　　最小割可以转化为最大流，我用的dinic极限数据942ms有点慌

　　还有就是千万别忘开long long

3.代码

#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<algorithm>
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;
}