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

wxwoo

2019-04-19

题解 / 洛谷

原题目链接

选人有利润，选了要付出代价：~~明显的~~最小割模型

我们将每个人看成一个点，然后如下建边：

源点向每个人连流量为其总收益的边（即$\sum\limits_{j=1}^n E_{i,j}$）

每个人向汇点连流量为其花费的边

$i$向$j$连流量为$E_{i,j} \times 2$的边

接下来我们思考这样建边的正确性

前两条是经典的最小割模型

第三条，如果两个人都选，可以获得$E_{i,j}$的利润

如果有一个不选，会亏损$E_{i,j}$的利润

利润差为$E_{i,j} \times 2$

这样连边，一旦两个人中有一个人没选，这条边就会断掉，造成利润差

代码如下

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

template<typename T> inline void read(T &x)
{
    char ch=getchar();
    T f=1;
    x=0;
    while(!('0'<=ch&&ch<='9'))
    {
        if(ch=='-')
            f=-1;
        ch=getchar();
    }
    while('0'<=ch&&ch<='9')
    {
        x=(x<<3)+(x<<1)+ch-48;
        ch=getchar();
    }
    x*=f;
}
const int inf=1e9;
const int N=3e5+1;
struct edge
{
    int from,to,next,cap,flow;
}e[N];
int cnt,n,m,sour,sink,head[N],ans,q[N],l[N],p[N];
inline int min(int i,int j)
{
    return i<j?i:j;
}
inline void add(int u,int v,int l)
{
    e[++cnt]=(edge){u,v,head[u],l,0};
    head[u]=cnt;
    e[++cnt]=(edge){v,u,head[v],0,0};
    head[v]=cnt;
}
inline bool find()
{
    memset(l,0,sizeof(l));
    int h=1,t=1;
    q[1]=sour;
    l[sour]=1;
    while(h<=t)
    {
        int x=q[h++];
        for(int i=head[x];i;i=e[i].next)
            if(!l[e[i].to]&&e[i].cap>e[i].flow)
            {
                q[++t]=e[i].to;
                l[e[i].to]=l[x]+1;
                if(e[i].to==sink)
                    return true;
            }
    }
    return false;
}
int dfs(int x,int now)
{
    if(x==sink||!now)
        return now;
    int t=now,detla;
    for(int i=head[x];i;i=e[i].next)
    {
        if(e[i].cap>e[i].flow&&l[e[i].to]==l[x]+1)
        {
            detla=dfs(e[i].to,min(t,e[i].cap-e[i].flow));
            if(!detla)
                l[e[i].to]=0;
            e[i].flow+=detla;
            e[((i-1)^1)+1].flow-=detla;
            t-=detla;
            if(t==0)
                break;
        }
    }
    return now-t;
}
inline void dinic()
{
    while(find())
        ans+=dfs(sour,inf);
}
int sum;
int main()
{
    read(n);
    sour=0;
    sink=n+1;
    int w,cost;
    for(int i=1;i<=n;++i)
    {
        read(w);
        add(i,sink,w);
    }
    for(int i=1;i<=n;++i)
    {
        cost=0;
        for(int j=1;j<=n;++j)
        {
            read(w);
            if(w!=0)//优化：如果是0就不连边
            {
                cost+=w;
                add(i,j,w<<1);
            }
        }
        add(sour,i,cost);
        sum+=cost;
    }
    dinic();
    printf("%d",sum-ans);
    return 0;
}