BZOJ2039 [2009国家集训队]employ人员雇佣

AC通道：http://www.lydsy.com/JudgeOnline/problem.php?id=2039

鉴于一开始看题如果不仔细是看不懂题目的，还是说一下题目大意

[题目大意]：给定n个人，每个人有一个佣金，i和j如果同时被雇佣会产生2*E(i,j)的效益，i和j如果一个被雇佣一个不被雇佣会产生E(i,j)的亏损，求最大收益

[题目分析]：

　　发现这题和往常某道实验的题很像。[见网络流24题-太空飞行计划问题]

　　"很像"是说，如果没有“一个被雇佣一个不被雇佣”的惩罚的话一模一样。

　　那么先不考虑惩罚，那么就是直接往每个E[i][j]连边，容量为2*E[i][j]，然后E[i][j]往i,j连边，容量为INF，然后每个i往t连边，容量为cost[i]。

　　这样的话，割集就代表了一组决策，最小割为一组费用。最后的答案就是sigma(E[i][j])-maxflow。

　　现在我们考虑惩罚的部分怎么弄。

　　我们需要设计一种方案，使得如果选择两个能得到2*效益，选择一个会失去1*效益。

　　于是可以从s向每个i连边，容量为E[i][j]，然后在i与j之间连一条双向边，容量为2*E[i][j]。

　　这样的话，如果假设i选了，j没选，那么说明到i的流量会通过2*E[i][j]这条边再从cost[j]这条边流走，损失了2*E[i][j]，然后通过s->i的E[i][j]的补充，就完成了损失E[i][j]的操作。

　　假设i,j都选了，那么中间的边就只是一个调控流量的东西，使得i,j到t的流量都流满。

　　如果你发现这样打了速度不够快？...居然有人200ms能过，怎么我tm要用7000ms?下面有一些优化方法。

　　1.连两条单向边改成连一条来回流量都为w的边[可以减少边的数量]

　　2.读入优化

　　3.特判，数据中有许多E[i][j]=0的情况，这种情况你不要连边就好。

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int maxn=;

const int INF=0x3f3f3f3f;

inline int in(){

    int x=;char ch=getchar();

    while(ch>'' || ch<'') ch=getchar();

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

    return x;

}

struct Node{

    int data,next,low;

}node[maxn*maxn*];

#define now node[point].data

#define then node[point].next

#define www node[point].low

int n,cnt,s,t,ans;

int head[maxn],cur[maxn];

int dis[maxn],que[maxn];

int stoi[maxn];

int a[maxn][maxn],cost[maxn];

void add(int u,int v,int w){

    node[cnt].data=v;node[cnt].next=head[u];node[cnt].low=w;head[u]=cnt++;

    node[cnt].data=u;node[cnt].next=head[v];node[cnt].low=;head[v]=cnt++;

}

void add2(int u,int v,int w){

    node[cnt].data=v;node[cnt].next=head[u];node[cnt].low=w;head[u]=cnt++;

    node[cnt].data=u;node[cnt].next=head[v];node[cnt].low=w;head[v]=cnt++;

}

bool BFS(){

    memset(dis,-,sizeof(dis));

    int H=,T=;que[]=s,dis[s]=;

    while(H<T){

        H++;

        for(int point=head[que[H]];point!=-;point=then)

            if(www && dis[now]<){

                dis[now]=dis[que[H]]+;

                que[++T]=now;

            }

    }

    if(dis[t]<) return false;

    return true;

}

int dfs(int x,int low){

    if(x==t) return low;

    int Low;

    for(int &point=cur[x];point!=-;point=then)

        if(www && dis[now]==dis[x]+){

            Low=dfs(now,min(low,www));

            if(Low){

                www-=Low;node[point^].low+=Low;

                return Low;

            }

        }

    return ;

}

int main(){

#ifndef ONLINE_JUDGE

    freopen("2039.in","r",stdin);

    freopen("2039.out","w",stdout);

#endif

    scanf("%d",&n);

    t=n+;

    for(int i=s;i<=t;i++) head[i]=-;

    for(int i=;i<=n;i++)

        cost[i]=in(),add(i,t,cost[i]);

    for(int i=;i<=n;i++)

        for(int j=;j<=n;j++)

            a[i][j]=in();

    for(int i=;i<=n;i++)

        for(int j=i+;j<=n;j++){

            stoi[i]+=a[i][j];

            stoi[j]+=a[i][j];

            if(a[i][j])

                add2(i,j,a[i][j]<<);

        }

    for(int i=;i<=n;i++)

        add(s,i,stoi[i]),ans+=stoi[i];

    int flag;

    while(BFS()){

        for(int i=s;i<=t;i++) cur[i]=head[i];

        while(){

            flag=dfs(s,INF);

            if(!flag) break;

            ans-=flag;

        }

    }

    printf("%d",ans);

    return ;

}

巴特西

BZOJ2039 [2009国家集训队]employ人员雇佣

最新文章

热门文章