Bakser's Blog

我是逗比。

bzoj2039[2010集训队作业][employ人员雇佣]

| Comments

目标就是将人们分成雇佣与不雇佣两个集合,最小割显然
奇妙的补集转化思想。首先统计最大可能的收益为e数组的和。
然后从s向i连边,容量为ai,代表选了i后会有ai的损失。
从i向t连边,容量为sigma(e[i][j])(1<=j<=n),代表不选i会造成的损失。
i向j连边,容量为2*e[i][j],代表只选i,j其中一个会造成的损失,注意是无向边。

bzoj2039
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
typedef long long LL;
#define N 1100
#define M 2100000
#define INF 0x7f7f7f7f7f7f7f7fLL
#define MIN(a,b) (((a)<(b))?(a):(b))
struct hh
{
    int next,u,v;
    LL cap;
}edges[M];
int n,point[N],s,t,cur[N],p[N],d[N],gap[N];
LL sum;
inline void addedge(int u,int v,LL cap)
{
    static int en(-1);
    edges[++en].next=point[u];point[u]=en;edges[en].u=u;edges[en].v=v;edges[en].cap=cap;
    edges[++en].next=point[v];point[v]=en;edges[en].u=v;edges[en].v=u;edges[en].cap=0;
}
inline LL augment()
{
    LL flow(INF);
    for(int x(t);x!=s;x=edges[p[x]].u)
        flow=MIN(flow,edges[p[x]].cap);
    for(int x(t);x!=s;x=edges[p[x]].u)
        edges[p[x]].cap-=flow,edges[p[x]^1].cap+=flow;
    return flow;
}
inline void bfs()
{
    static queue<int> q;
    memset(d,0xff,sizeof(d));
    gap[d[t]=0]++;q.push(t);
    while(!q.empty())
    {
        int u(q.front());q.pop();
        for(int i(point[u]);i!=-1;i=edges[i].next)
            if(edges[i^1].cap&&d[edges[i^1].u]==-1)
            {
                gap[d[edges[i^1].u]=d[u]+1]++;
                q.push(edges[i^1].u);
            }
    }
}
inline LL isap()
{
    int x(s);LL res(0);
    memcpy(cur,point,(n+5)*sizeof(int));
    bfs();
    while(d[s]<n+2)
    {
        if(x==t)res+=augment(),x=s;
        bool flag(0);
        for(int i(cur[x]);i!=-1;i=edges[i].next)
            if(edges[i].cap&&d[x]-1==d[edges[i].v])
                {
                    flag=1;
                    cur[x]=i;
                    x=edges[i].v;
                    p[x]=i;
                    break;
                }
        if(!flag)
        {
            int delta(n+2);
            if(!--gap[d[x]])break;
            for(int i(point[x]);i!=-1;i=edges[i].next)
                if(edges[i].cap&&d[edges[i].v]<delta)
                    {
                        delta=d[edges[i].v];
                        cur[x]=i;
                    }
            gap[d[x]=delta+1]++;
            if(x!=s)x=edges[p[x]].u;
        }
    }
    return res;
}
int main()
{
    scanf("%d",&n);
    s=0;t=n+1;
    memset(point,0xff,sizeof(point));
    LL tmp;
    for(int i(1);i<=n;i++)
    {
        scanf("%lld",&tmp);
        addedge(s,i,tmp);
    }
    for(int i(1);i<=n;i++)
    {
        LL sigma(0);
        for(int j(1);j<=n;j++)
        {
            scanf("%lld",&tmp);
            sum+=tmp;sigma+=tmp;
            if(i!=j)addedge(i,j,tmp<<1);
        }
        addedge(i,t,sigma);
    }
    printf("%lld\n",sum-isap());
    return 0;
}

Comments

comments powered by Disqus