BruceJay's Blog

BZOJ2039 人员雇佣

| Comments

To start with

又是一道最小割的题。

Problem

Solution

这种求最大收益的题往往都是总收益-最小花费。
定义总收益为∑E(i,j)。
考虑S集为雇佣,T集为不雇佣。考虑每一条边(u,v),如果都被雇佣,花费将是a[u]+a[v];如果都不被雇佣,花费将是E(u,v)+E(v,u);如果一个被雇佣,一个不被佣(将设u被雇佣,v不被雇佣),花费将是2E(u,v)+E(v,u)。
所以,对于每条边(u,v)。u和v分别向T连容量为a[u],a[v]的边,S向u和v分别连容量为E(u,v)的边,再u和v之间互连容量为2E(u,v)的边。
由于按上方案建图S会向每个点连很多条边,最好将这些边合并。

Code

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

typedef long long ll;
const int N = 1010;
const int M = 1010000;
const ll INF = 1e15;
struct Edge{int u,v;ll cap,flow;int nxt;}e[M];
int head[N]; int cur[N];
ll a[N]; int h[N];
queue<int> q;
int n,t,cnt=1; ll ans=0;

inline ll read()
{
    ll t=1,x=0; char ch=getchar();
    while(ch<'0' || ch>'9'){
        if(ch=='-') t=-1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9'){
        x=x*10+(ll)ch-'0';
        ch=getchar();
    }
    return t*x;
}

void Addedge(int u,int v,ll cap)
{
    e[++cnt]=(Edge){u,v,cap,0,head[u]}; head[u]=cnt;
    e[++cnt]=(Edge){v,u,0,0,head[v]}; head[v]=cnt;
}

void Addedge2(int u,int v,ll cap)
{
    e[++cnt]=(Edge){u,v,cap,0,head[u]}; head[u]=cnt;
    e[++cnt]=(Edge){v,u,cap,0,head[v]}; head[v]=cnt;
}

bool Bfs()
{
    memset(h,-1,sizeof(h));
    h[0]=0; q.push(0);
    while(!q.empty()){
        int u=q.front(); q.pop();
        for(int i=head[u];i;i=e[i].nxt){
            if(h[e[i].v]==-1 && e[i].cap>e[i].flow){
                h[e[i].v]=h[u]+1; q.push(e[i].v);
            }
        }
    }
    return h[t]!=-1;
}

ll Dfs(int u,ll now)
{
    ll flow=0;
    if(u==t || !now) return now;
    for(int& i=cur[u];i;i=e[i].nxt)
        if(h[e[i].v]==h[u]+1){
            ll f=Dfs(e[i].v,min(now,e[i].cap-e[i].flow));
            e[i].flow+=f; e[i^1].flow-=f;
            flow+=f; now-=f; if(!now) break;
        }
    return flow;
}

void Dinic()
{
    while(Bfs()){
        memcpy(cur,head,sizeof(cur));
        ans-=Dfs(0,INF);
    }
}

int main()
{
    ll x;
    freopen("2039.in","r",stdin);
    freopen("2039.out","w",stdout);
    n=read(); t=n+1;
    for(int i=1;i<=n;i++) Addedge(i,t,read());
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            x=read(); a[i]+=x;
            if(x && i<j) Addedge2(i,j,x<<1);
        }
        Addedge(0,i,a[i]); ans+=a[i];
    }
    Dinic();
    printf("%lld",ans);
    return 0;
}

Last but not least

对于那些E(i,j)==0的,就不需要连边了。特判一下,会有非常神奇的效果。

Comments

comments powered by Disqus