BZOJ2039_employ人员雇佣_KEY

题目传送门

网络流，求最小割。

设tot为所有盈利的和，即所有人（不花钱）雇佣。

对于S->i建一条容量为c[i]的边，i->j建一条S[i][j]*2的边，之所以这样建是因为如果不选这个人还会亏S[i][j]。

对于i->T建一条容量为∑S[i][j]的边。

最小割=最大流，跑Dinic

code：

/**************************************************************

    Problem: 2039

    User: yekehe

    Language: C++

    Result: Accepted

    Time:4428 ms

    Memory:52316 kb

****************************************************************/

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

int read()

{

    char c;while(c=getchar(),c<''||c>'');

    int x=c-'';while(c=getchar(),c>=''&&c<='')x=x*+c-'';

    return x;

}

int N,a[],MP[][];

int head[],nxt[],To[],W[],cnt;

void add(int x,int y,int c)

{

    To[cnt]=y,W[cnt]=c;

    nxt[cnt]=head[x];

    head[x]=cnt;

    cnt++;

}

int dist[],l[],h,t;

int BFS()

{

    h=t=;

    memset(dist,0xfff,sizeof dist);

    l[++t]=,dist[]=;

        while(h<t){

            int front=l[++h];

                for(int i=head[front];i!=-;i=nxt[i]){

                    if(dist[To[i]]==- && W[i]){

                        dist[To[i]]=dist[front]+;

                        l[++t]=To[i];

                    }

                }

        }

    return dist[N+]!=-;

}

int DFS(int x,int w)

{

    if(x==N+ || !w)return w;

    int res=;

        for(int i=head[x];i!=-&&w;i=nxt[i]){

            if(dist[x]+==dist[To[i]] && W[i]){

                int DK=DFS(To[i],min(w,W[i]));

                res+=DK;w-=DK;

                W[i]-=DK,W[i^]+=DK;

            }

        }

    if(!res)dist[x]=-;

    return res;

}

int tot=;

void Dinic()

{

    int ans=;

        while(BFS())

            ans+=DFS(,2e9);

    printf("%d",tot-ans);

    return ;

}

int main()

{

    memset(head,-,sizeof head);

    memset(nxt,-,sizeof nxt);

    N=read();

    register int i,j;

        for(i=;i<=N;i++)

            a[i]=read(),add(,i,a[i]),add(i,,);

        for(i=;i<=N;i++)

            for(j=;j<=N;j++)

                MP[i][j]=read(),tot+=MP[i][j];

        for(i=;i<=N;i++)

            for(j=i+;j<=N;j++)

                add(i,j,MP[i][j]<<),add(j,i,MP[i][j]<<);

        for(i=;i<=N;i++){

            int res=;for(j=;j<=N;j++)res+=MP[i][j];

            add(i,N+,res),add(N+,i,);

        }

    Dinic();

    return ;

}