【思维题最大权闭合子图】loj#6045. 「雅礼集训 2017 Day8」价

又是经典模型的好题目

人类智慧之神 zhangzj 最近有点胖，所以要减肥，他买了 NN 种减肥药，发现每种减肥药使用了若干种药材，总共正好有 NN 种不同的药材。

经过他的人脑实验，他发现如果他吃下去了 KK（0≤K≤N0≤K≤N）种减肥药，而这 KK 种减肥药使用的药材并集大小也为 KK，这 KK 种才会有效果，否则无效。
第 ii 种减肥药在产生效果的时候会使 zhangzj 的体重增加 PiPi 斤，显然 PiPi 可以小于 00。

他想知道，一次吃药最好情况下体重变化量是多少，当然可以一种药也不吃，此时体重不变。由于某些奥妙重重的情况，我们可以让这 NN 种减肥药每一种对应一个其使用的药材，且 NN 种减肥药对应的药材互不相同（即有完美匹配）。

第一行一个整数 NN。

接下来 NN 行，每行描述一种减肥药，对于一种减肥药，第一个数读入使用的药材个数 tt，接下来 tt 个整数表示使用的药材编号，一个药材编号在一行只会出现一次。
最后一行 NN 个整数，第 ii 个整数 PiPi 表示第 ii 种减肥药产生效果时的体重变化量。

对于

题目分析

这道题最主要的麻烦在于药材和药的数目要相同，这意味着最优情况下，可能需要选取一些收益为负的药来达到合法状态。因此wqs二分药材权值负增量的做法就会挂得很彻底。

再观察题目的特殊性质，发现给出的一张图是恰好两侧点数相同，且具有完美匹配的二分图。这个条件说明在左侧任意选取$k$个点，右侧对应的$k'$必定有$k le k'$。这是一个相当重要的条件。在这个前提下，我们可以把每种减肥药的权值改为$BASE-P_i$；药材的权值设成$BASE$，再以此做最大权闭合子图。关于这个做法的解释如下所示：

这里是第一个例子，最优方案是三个全选，收益为20。考虑一下“表面权值和最优”（但是不合法）的选前两个的方案，由于我们在右侧每个药材都连出了$BASE$的边，那么当左边选取$k$个、右边选取$kle k'$个时，进行的操作相当于是选了右侧$k' imes BASE$的割，然而很明显选左侧$k imes BASE-sum P_i$的割更优。但在最大权闭合子图的方面看，割去$(S,i)$也即意味着点$i$就是不选了，这与前一假设矛盾。因此，右边边权的$BASE$增量能够致使$kge k'$，那么综上所述保证了$k=k'$。

以下是第二个例子。在这个例子中，为了保证合法，我们不得不选取增肥100的减肥药。同样是考虑选取前两个元素的方案，会发现仍然由于右侧有三个$BASE，所以导致只有在加入第三个元素时才得到最大值。

 1 #include<bits/stdc++.h>
 2 const int maxn = 1035;
 3 const int maxm = 200035;
 4 const int INF = 2e9;
 5 const int base = 5e6;
 6 
 7 struct Edge
 8 {
 9     int u,v,f,c;
10     Edge(int a=0, int b=0, int c=0, int d=0):u(a),v(b),f(c),c(d) {}
11 }edges[maxm];
12 int edgeTot,head[maxn],nxt[maxm],lv[maxn];
13 int n,ans,tot,S,T;
14 
15 void addedge(int u, int v, int c)
16 {
17     edges[edgeTot] = Edge(u, v, 0, c), nxt[edgeTot] = head[u], head[u] = edgeTot, ++edgeTot;
18     edges[edgeTot] = Edge(v, u, 0, 0), nxt[edgeTot] = head[v], head[v] = edgeTot, ++edgeTot;
19 }
20 bool buildLevel()
21 {
22     std::queue<int> q;
23     memset(lv, 0, sizeof lv);
24     q.push(S), lv[S] = 1;
25     for (int tmp; q.size(); )
26     {
27         tmp = q.front(), q.pop();
28         for (int i=head[tmp]; i!=-1; i=nxt[i])
29         {
30             int v = edges[i].v;
31             if (!lv[v]&&edges[i].f < edges[i].c){
32                 lv[v] = lv[tmp]+1, q.push(v);
33                 if (v==T) return true;
34             }
35         }
36     }
37     return false;
38 }
39 int fndPath(int x, int lim)
40 {
41     int sum = 0;
42     if (x==T||!lim) return lim;
43     for (int i=head[x]; i!=-1&&sum < lim; i=nxt[i])
44     {
45         int v = edges[i].v, val;
46         if (lv[v]==lv[x]+1&&edges[i].f < edges[i].c){
47             if ((val = fndPath(v, std::min(lim-sum, edges[i].c-edges[i].f)))){
48                 edges[i].f += val, edges[i^1].f -= val, sum += val;
49             }else lv[v] = -1;
50         }
51     }
52     return sum;
53 }
54 int dinic()
55 {
56     int ret = 0, val;
57     while ((buildLevel()))
58         while ((val = fndPath(S, INF))) ret += val;
59     return ret;
60 }
61 int main()
62 {
63     freopen("loj6045.in","r",stdin);
64     freopen("loj6045.out","w",stdout);
65     memset(head, -1, sizeof head);
66     scanf("%d",&n), S = 0, T = 2*n+1;
67     for (int i=1,k; i<=n; i++)
68     {
69         scanf("%d",&k);
70         for (int u; k; --k)
71             scanf("%d",&u), addedge(i, u+n, INF);
72     }
73     for (int i=1,s; i<=n; i++)
74     {
75         scanf("%d",&s);
76         addedge(S, i, base-s);
77         addedge(i+n, T, base);
78         tot += base-s;
79     }
80     printf("%d
",-tot+dinic());
81     return 0;
82 }

END