LG 1791 人员雇佣

发表于 | 更新于 | 分类于 ， | 评论数：

摘要

$n$ 个人，选取一个子集，选人有代价，两人同时选有收益，二选一有损失，求最大收益。

Pickupwin 知道这是最小割，但不会建图

题面

题解

最小割

每个人建一个点，用该点与 $S$ 或 $T$ 连通表示不取或取，割断边要支付代价。

可以将两人同时选的收益转化为选人的收益和二选一的代价：

用 $X_i\in{0,1}$ 表示不选/选，则 $X_i\times X_j=\frac{1}{2}(X_i+X_j-[X_i\neq X_j])$

于是点 $i$ 与 $S$ 连边 $A_i$ ，与 $T$ 连边 $\sum_j E_{i,j}$

点 $i$ 与点 $j$ 连边 $2\times E_{i,j}$ （均为无向边）

求最小割 $Min$ ， $Ans=\sum_{i,j} E_{i,j}-Min$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
//https://www.luogu.com.cn/problem/P1791
//20211023 AliCCC

#include <cstdio>
#include <queue>
#include <algorithm>

using std::min;
using std::queue;

const long long LONF=4567891012345678910LL;
const int MAXN=1011;
const int MAXV=MAXN<<1;
const int MAXE=(MAXN<<1)+(MAXN*MAXN);	//undirected

int N;

int A[MAXN];

int Ee[MAXN][MAXN];

struct Vert{
	int FE;
	int Lev, Bfn;
} V[MAXV];

int Vcnt;
int Sink, Sour;
int P[MAXN];

struct Edge{
	int y, next;
	long long f;
} E[MAXE<<1];

int Ecnt=2;

void addE(const int &a, const int &b, const long long &f){
	E[Ecnt].y=b;E[Ecnt].next=V[a].FE;V[a].FE=Ecnt;E[Ecnt].f=f;++Ecnt;
	E[Ecnt].y=a;E[Ecnt].next=V[b].FE;V[b].FE=Ecnt;E[Ecnt].f=f;++Ecnt;
}

int BFN;

queue<int> Q;

bool BFS(int at=Sour){
	++BFN;
	V[at].Lev=1;
	Q.push(at);
	V[at].Bfn=BFN;
	while(!Q.empty()){
		at=Q.front();Q.pop();
		for(int k=V[at].FE, to;k;k=E[k].next){
			if(E[k].f<=0)	continue;
			to=E[k].y;
			if(V[to].Bfn==BFN)	continue;
			V[to].Lev=V[at].Lev+1;
			Q.push(to);
			V[to].Bfn=BFN;
		}
	}
	return V[Sink].Bfn==BFN;
}

long long DFS(int at=Sour, long long inc=LONF){
	if(at==Sink || inc<=0LL)	return inc;
	long long ret=0LL, out;
	for(int k=V[at].FE, to;k;k=E[k].next){
		if(E[k].f<=0)	continue;
		to=E[k].y;
		if(V[to].Lev!=V[at].Lev+1)	continue;
		out=DFS(to, min(E[k].f, inc));
		inc-=out;E[k].f-=out;
		ret+=out;E[k^1].f+=out;
	}
	if(inc>0LL)	V[at].Lev=-1;
	return ret;
}

long long DINIC(){
	long long ret=0LL;
	while(BFS()){
		ret+=DFS();
		// for(int i=0;i<Ecnt;++i){
		// 	printf("%d %d %lld\n", E[i].y, E[i].next, E[i].f);
		// }
		// printf("--%lld\n", ret);
		// puts("");
	}
	return ret;
}

int main(){
	
	scanf("%d", &N);
	
	Sour=++Vcnt;Sink=++Vcnt;
	for(int i=1;i<=N;++i)	P[i]=++Vcnt;
	
	for(int i=1;i<=N;++i)	scanf("%d", &A[i]);
	
	for(int i=1;i<=N;++i){
		addE(Sour, P[i], A[i]);
	}
	
	long long Ans=0LL;
	
	for(int i=1;i<=N;++i){
		long long tmp=0LL;
		for(int j=1;j<=N;++j){
			scanf("%d", &Ee[i][j]);
			if(Ee[i][j])	addE(P[i], P[j], Ee[i][j]);
			tmp+=Ee[i][j];Ans+=Ee[i][j];
		}
		addE(Sink, P[i], tmp);
	}
	
	Ans-=DINIC();
	
	printf("%lld\n", Ans);
	
	return 0;
}

后记

其实 $0\leq X_i\leq 1$ ， $\max \sum_{i,j} X_iX_jE_{i,j}-\sum_{i,j} [X_i>X_j]E_{i,j}-\sum_{i}X_iA_i$ 是比较经典的线性规划式子，但 Pickupwin 发现自己不会线性规划转网络流了 TAT

求大佬指点 [可怜]