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

2024-03-16 18:08:04

Description

作为一个富有经营头脑的富翁，小L决定从本国最优秀的经理中雇佣一些来经营自己的公司。

这些经理相互之间合作有一个贡献指数,（我们用Ei,j表示i经理对j经理的了解程度），即当经理i和经理j同时被雇佣时，经理i会对经理j做出贡献，使得所赚得的利润增加Ei,j。

当然，雇佣每一个经理都需要花费一定的金钱Ai，对于一些经理可能他做出的贡献不值得他的花费，那么作为一个聪明的人，小L当然不会雇佣他。

然而，那些没有被雇佣的人会被竞争对手所雇佣，这个时候那些人会对你雇佣的经理的工作造成影响，使得所赚得的利润减少Ei,j（注意：这里的Ei,j与上面的Ei,j 是同一个）。

作为一个效率优先的人，小L想雇佣一些人使得净利润最大。

你可以帮助小L解决这个问题吗？

Input

第一行有一个整数N<=1000表示经理的个数

第二行有N个整数Ai表示雇佣每个经理需要花费的金钱

接下来的N行中一行包含N个数，表示Ei,j，即经理i对经理j的了解程度。（输入满足Ei,j=Ej,i）

Output

第一行包含一个整数，即所求出的最大值。

Sample Input

3
3 5 100
0 6 1
6 0 2
1 2 0

Sample Output

1
【数据规模和约定】
20%的数据中N<=10
50%的数据中N<=100
100%的数据中 N<=1000， Ei,j<=maxlongint, Ai<=maxlongint

题解Here!

在洛谷上卡常卡了好久终于过了。。。 $BZOJ$秒过。。。

于是补一发题解，给后来人一个借鉴。

记住：

1. 如果你的$Dinic$开了$O2$却$TLE$，请不要开$O2$。。。

2. 如果你的$Dinic$不开$O2$却还是$TLE$，请使用$ISAP$。。。

3. 如果你的$ISAP$开了$O2$却$TLE$，请不要开$O2$。。。

4. 如果你的$ISAP$不开$O2$却还是$TLE$，请使用$HLPP$。。。（当然我没用。。。）

以上是我的个人做题总结。。。

可以与看一下我的提交记录。

在$BZOJ$上$Dinic$是可以过的。

下面说解法：

显然这是一个最小割模型。

类似的题目有[这题]和[这题]。

对于本题，我们设$<u,v,w>$表示从$u$到$v$，流量为$w$得一条有向边，当然包括流量为零的反向边。

将源点设为$S$，汇点设为$T$。

于是连边：$<S,x,\sum_{i=1}^nE_{x,i}>,<x,T,A_x>$

那个敌对公司的影响先不管它。

这样，跑最小割即可。

也就是：

割掉$S$到$x$的边表示不雇佣这个人并且不给它工资，收益也被丢掉。

割掉$x$到$T$的边表示雇佣这个人并且给它工资。

然后用总收益$Sum$减去最小割$Ans$即为答案。

然后考虑敌对公司：

我们发现选这一对$i,j$和不选$i,j$之间的收益差正好是$E_{i,j}\times 2$。

所以我们对于每对$i,j$连边$<i,j,E_{i,j}\times 2>$。

然后同上，跑最小割即可。

这个题就做完了。

记得开$long\ long$。

各位巨佬也可以帮忙看看我的$Dinic$哪里写丑了。。。

附上在$BZOJ$上能过，洛谷上$70$的$Dinic$：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<queue>
#define MAXN 1010
#define MAXM 4100000
#define MAX (1LL<<60)
using namespace std;
int n,c=2,s,t;
int head[MAXN],deep[MAXN];
long long sum=0;
struct Edge{
    int next,to;
    long long w;
}a[MAXM];
inline int read(){
    int date=0;char c=0;
    while(c<'0'||c>'9')c=getchar();
    while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
    return date;
}
inline long long min(long long x,long long y){return x<y?x:y;}
inline void add(int u,int v,long long w){
    a[c].to=v;a[c].w=w;a[c].next=head[u];head[u]=c++;
    a[c].to=u;a[c].w=0;a[c].next=head[v];head[v]=c++;
}
bool bfs(){
    int u,v;
    queue<int> q;
    for(int i=1;i<=t;i++)deep[i]=0;
    deep[s]=1;
    q.push(s);
    while(!q.empty()){
        u=q.front();
        q.pop();
        for(int i=head[u];i;i=a[i].next){
            v=a[i].to;
            if(a[i].w&&!deep[v]){
                deep[v]=deep[u]+1;
                if(v==t)return true;
                q.push(v);
            }
        }
    }
    return false;
}
long long dfs(int x,long long limit){
    if(x==t)return limit;
    int v;
    long long sum,cost=0;
    for(int i=head[x];i;i=a[i].next){
        v=a[i].to;
        if(a[i].w&&deep[v]==deep[x]+1){
            sum=dfs(v,min(a[i].w,limit-cost));
            if(sum>0){
                a[i].w-=sum;
                a[i^1].w+=sum;
                cost+=sum;
                if(cost==limit)break;
            }
            else deep[v]=-1;
        }
    }
    return cost;
}
long long dinic(){
    long long ans=0;
    while(bfs())ans+=dfs(s,MAX);
    return ans;
}
void init(){
    int x;
    long long y;
    n=read();
    s=n+1;t=n+2;
    for(int i=1;i<=n;i++){
        x=read();
        add(i,t,x);
    }
    for(int i=1;i<=n;i++){
        y=0;
        for(int j=1;j<=n;j++){
            x=read();
            y+=x;
            add(i,j,x*2);
        }
        sum+=y;
        add(s,i,y);
    }
}
int main(){
    init();
    printf("%lld\n",sum-dinic());
    return 0;
}

然后是$ISAP$：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<queue>
#define MAXN 1010
#define MAXM 2100000
#define MAX (1LL<<60)
using namespace std;
int n,c=2,s,t;
int head[MAXN],num[MAXN],deep[MAXN],h[MAXN];
long long sum=0;
struct Edge{
	int next,to;
	long long w;
}a[MAXM];
inline int read(){
	int date=0;char c=0;
	while(c<'0'||c>'9')c=getchar();
	while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
	return date;
}
inline long long min(long long x,long long y){return x<y?x:y;}
inline void add(int u,int v,long long w){
	a[c].to=v;a[c].w=w;a[c].next=head[u];head[u]=c++;
	a[c].to=u;a[c].w=0;a[c].next=head[v];head[v]=c++;
}
long long dfs(int x,long long limit){
	if(x==t)return limit;
	int v;
	long long sum,cost=0;
	for(int i=h[x];i;i=a[i].next){
		v=a[i].to;
		if(a[i].w&&deep[v]+1==deep[x]){
			sum=dfs(v,min(a[i].w,limit-cost));
			a[i].w-=sum;
			a[i^1].w+=sum;
			cost+=sum;
			if(cost==limit)return cost;
			if(a[i].w)h[x]=i;
		}
	}
	--num[deep[x]];
	if(!num[deep[x]])deep[s]=n+2;
	deep[x]++;num[deep[x]]++;
	h[x]=head[x];
	return cost;
}
long long ISAP(){
	long long ans=0;
	for(int i=1;i<=n;i++)h[i]=head[i];
	while(deep[s]<n+2)ans+=dfs(s,MAX);
	return ans;
}
void init(){
	int x;
	long long y;
	n=read();
	s=n+1;t=n+2;
	for(int i=1;i<=n;i++){
		x=read();
		add(i,t,x);
	}
	for(int i=1;i<=n;i++){
		y=0;
		for(int j=1;j<=n;j++){
			x=read();
			y+=x;
			add(i,j,x*2);
		}
		sum+=y;
		add(s,i,y);
	}
}
int main(){
	init();
	printf("%lld\n",sum-ISAP());
	return 0;
}

码农公寓