「CF103E」Buying Sets-霍尔定理-网络流-最小权闭合子图

我们有 $n$ 个集合,第 $i$ 个集合有 $m_i$ 个数($1$ 到 $n$ 中的整数),权值为 $w_i$ 。

现在请你从中选出 $k$ ($k$ 为任意 $0$ 到 $n$ 中的整数)个集合,满足这 $k$ 个集合的并集的大小为 $k$ ,询问这 $k$ 个集合的权值和最小值。

保证从这 $n$ 选出任意 $x$ 个集合,他们的并集大小不小于 $k$ 。

链接

Codeforces

题解

熟悉二分图那套理论的同学很快就会发现,题目中给出的条件:任意 $k(1 \le k \le n)$ 个集合的并集的大小都不小于 $k$ ,可以转化成霍尔定理的一方面的表述。

我们建立一个二分图 $G_1$ ,左边放上所有的集合,右边放上所有的数,把左侧每个集合向其拥有的数连一条边,那么这个时候,根据霍尔定理,这个二分图存在一个左侧所有节点都在匹配中的匹配(这个图中右侧也只有 $n$ 个节点,所以事实上是一个完美匹配)。

所以每一个集合 $i$ 都可以对应到一个数 $c_i$ , 且任意两个数的 $c_i$ 都不相同。

这个时候我们发现,任意选 $k$ 个集合,我们都可以得到这 $k$ 个集合并集的一个子集,就是由这 $k$ 个集合的 $c_i$ 构成的集合。这个时候我们已经不能有任何其他的数加入,如果我们选择了第 $i$ 个集合,那么我们对于第 $i$ 个集合,对于除了 $c_i$ 的元素 $t$ ,我们都必须选择 $c_j = t$ 的 $j$ 集合,才能保证不多出来元素。

这个时候,我们就有了一个新模型, 仔细观察的话,就会发现其实是一个最小权闭合子图的模型,可以用最小割模型来解决,网上也有许多资料,在这里就不重复了。

代码

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
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 610,inf = 0x3f3f3f3f;

int n,w[MAXN];
vector<int> G[MAXN];

struct Edge{
int from,to;
int cap,flow;
int nex;
}edge[MAXN*MAXN*2];
int fir[MAXN],ecnt = 2;
int addedge(int a,int b,int c){
edge[ecnt] = (Edge){a,b,c,0,fir[a]};
fir[a] = ecnt++;
edge[ecnt] = (Edge){b,a,0,0,fir[b]};
fir[b] = ecnt++;
return ecnt - 2;
}

int dis[MAXN];
queue<int> q;

bool bfs(int s,int t){
memset(dis,0,sizeof(dis));
while(!q.empty()) q.pop();
dis[s] = 1;q.push(s);
while(!q.empty()){
int nown = q.front();q.pop();
for(int nowe = fir[nown];nowe;nowe = edge[nowe].nex){
int v = edge[nowe].to;
if(dis[v] == 0 && edge[nowe].cap > edge[nowe].flow){
dis[v] = dis[nown] + 1;
q.push(v);
}
}
}
return dis[t] != 0;
}

int dfs(int nown,int t,int limit = inf){
if(nown == t || limit == 0) return limit;
int sumf = 0;
for(int nowe = fir[nown];nowe;nowe = edge[nowe].nex){
int v = edge[nowe].to;
if(dis[v] == dis[nown] + 1 && edge[nowe].cap > edge[nowe].flow){
int f = dfs(v,t,min(limit,edge[nowe].cap - edge[nowe].flow));
if(f){
edge[nowe].flow += f,edge[nowe^1].flow -= f;
sumf += f,limit -= f;
}
if(limit == 0) break;
}
}
return sumf;
}

int dinic(int s,int t){
int ans = 0;
while(bfs(s,t)) ans += dfs(s,t);
return ans;
}

void init(){
scanf("%d",&n);
for(int i = 1;i<=n;i++){
int m;
scanf("%d",&m);
while(m--){
int x;scanf("%d",&x);
G[i].push_back(x);
}
}
for(int i = 1;i<=n;i++) scanf("%d",&w[i]);
}

vector<int> E[MAXN];int c[MAXN],back[MAXN];

void get_matching(){
int S = 0,T = 2*n+1;
for(int i = 1;i<=n;i++){
addedge(S,i,1),addedge(i+n,T,1);
for(auto j : G[i])
E[i].push_back(addedge(i,j+n,1));
}
dinic(S,T);
for(int i = 1;i<=n;i++){
for(unsigned x = 0;x < G[i].size();x++){
if(edge[E[i][x]].flow == 1){
c[i] = G[i][x];
back[G[i][x]] = i;
break;
}
}
}
}

void solve(){
get_matching();
ecnt = 2;memset(fir,0,sizeof(fir));
int S = n+1,T = S+1;
int ans = 0;
for(int i = 1;i<=n;i++){
w[i] = -w[i];
if(w[i] > 0) addedge(S,i, w[i]),ans += w[i];
else addedge(i,T,-w[i]);
}
for(int i = 1;i<=n;i++){
for(auto j : G[i])if(j != c[i])
addedge(i,back[j],inf);
}
ans -= dinic(S,T);
printf("%d\n",-ans);
}

int main(){
init();
solve();
return 0;
}

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×