[BZOJ2039][2009国家集训队]employ人员雇佣 最小割好题


原题链接
碰到这种将所有元素划分为两个集合,最大化净收益的题,九成是最小割了.
本题就是一道套路题.
我们首先假定拿到了所有的收益,只需要求最小损失.下面讨论一个人选和不选的代价:如果选,则付出这个人的佣金;如果不选,首先需要放弃所有它和其他所有人产生的收益,进一步的,对于已经选择的人,还要付出额外的代价.
至此,建图方式就有了.
源点朝所有点连边,边权为雇佣金;
所有点朝汇点连边,边权为;
点与点之间连边,边权为eij.
跑最小割即可.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 1023
#define M 5002333
using namespace std;
typedef long long ll;
const ll inf=0x3bbbbbbbbbbbbbbbll;
inline char nc()
{
    static char buf[100000],*p1,*p2;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline void read(int &x)
{
    x=0;char c=nc();
    while(!isdigit(c))c=nc();
    while(isdigit(c))x=x*10+c-'0',c=nc();
}
int n,m,head[N],to[M],nxt[M],tot=1;
ll f[M];
inline void add(int x,int y,ll z)
{
    to[++tot]=y,nxt[tot]=head[x],head[x]=tot,f[tot]=z;
    to[++tot]=x,nxt[tot]=head[y],head[y]=tot,f[tot]=0;
}
int dis[N],q[N],l,r,s,t;
inline bool bfs()
{
    memset(dis,0,sizeof dis);
    l=1,r=0;
    dis[s]=1,q[++r]=s;
    int x,i,y;
    while(l<=r)
    {
        x=q[l++];
        for(i=head[x];i;i=nxt[i])if(f[i]&&!dis[y=to[i]])
        {
            dis[y]=dis[x]+1;
            if(y==t)return 1;
            q[++r]=y;
        }
    }
    return 0;
}
ll dinic(int x,ll flow)
{
    if(x==t)return flow;
    ll tmp,lft=flow;
    for(int y,i=head[x];i;i=nxt[i])if(dis[y=to[i]]==dis[x]+1&&f[i])
    {
        tmp=dinic(y,min(lft,f[i]));
        if(!tmp)dis[y]=0;
        f[i]-=tmp,f[i^1]+=tmp,lft-=tmp;
        if(!lft)return flow;
    }
    return flow-lft;
} 
ll maxflow()
{
    ll re=0;
    while(bfs())re+=dinic(s,inf);
    return re;
}
ll sum[N],ans;
int main()
{
    read(n);
    s=0,t=n+1;
    int i,j,val;
    for(i=1;i<=n;++i)
    {
        read(val);
        add(s,i,val);
    }
    for(i=1;i<=n;++i)
    {
        for(j=1;j<=n;++j)
        {
            read(val);
            add(i,j,(ll)val),add(j,i,(ll)val);
            sum[i]+=val,ans+=val;
        }
    }
    for(i=1;i<=n;++i)add(i,t,sum[i]);
    cout<<ans-maxflow();
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注