「Luogu 1361」小 M 的作物

发表于 | | 阅读次数:
字数统计: 1.1k 字

Description

题目链接：Luogu 1361

小 M 在开辟了两块巨大的耕地 $A$ 和 $B$（你可以认为容量无穷），现在他有 $n$ 种作物的种子各 $1$ 个，编号为 $1$ 到 $n$。第 $i$ 种作物在 $A$ 中种植可以获得 $a_i$ 的收益，在 $B$ 中种植可以获得 $b_i$ 的收益。某些作物种在同一块耕地中可以获得额外的收益，小 M 找到 $m$ 种作物的组合，每个组合用 $c_1,c_2,k $ 和一个序列 $p_1,p_2,\cdots.p_k$ 表示，代表这 $k$ 种作物共同种在 $A$ 和 $B$ 耕地中可以分别获得 $c_1$ 和 $c_2$ 的额外收益。求收益的最大值。

数据范围：$1\le n,m\le 1000$

Solution

通过「算法笔记」网络流 - 最小割 中问题模型的分析，我们可以发现这题每种作物只能选择一个耕地，满足二者选其一的性质，所以我们可以考虑用最小割来解决。

对于单独的作物直接从源点 $s$ 连边或向 $t$ 连边即可，难点在如何处理组合的关系。

首先明确一点，一个组合就是一个点集，它的贡献有三种情况：对集合 $A$ 有贡献；对集合 $B$ 有贡献；没有任何贡献。这意味着只划分出一种状态是无法描述的，我们需要把 $A$ 和 $B$ 集合分开考虑。

接下来讨论点集 $\{u,v,w\}$ 对集合 $A$ 的贡献。

按照题意，我们的要求是：只要 $u,v,w$ 其中一者被割进了集合 $B$（连向 $t$），那么这个点集都没有贡献。换言之，只要其中一个点在集合 $B$，那么代表点集和集合 $A$ 的连边必须断开！

我们先用一个虚点 $x$ 从 $s$ 连一条代表贡献的边（显然点集必须用一个虚点代替）。如果其中一个点被割进了集合 $B$，那么这条代表贡献的边就要被断开，而 $x$ 到 $u,v,w$ 的边不能被断开。所以我们可以得到：边 $(s,x)$ 的容量为 $c_1$，边 $(x,u),(x,v),(x,w)$ 的容量均为 $\text{INF}$（因为只有容量为正无穷的边不可能被断开）。

这个点集对集合 $B$ 的贡献同理。经过检验，我们发现这样的连边方式是完全正确的！直接建图跑最小割即可。

注意：答案为总的收益减去最小割！

时间复杂度：$O(n^2m)$（$\text{Dinic}$）

Code

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
 
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>

const int N=3e3+5,M=5e6+5;
int n,m,tot=1,a[N],b[N],lnk[N],ter[M],nxt[M],val[M],dep[N],cnr[N];

int id(int p,int x) {
    switch(p) {
        case 1: return x;
        case 2: return m+x;
        case 3: return m+n+x;
    }
}
void add(int u,int v,int w) {
    ter[++tot]=v,nxt[tot]=lnk[u],lnk[u]=tot,val[tot]=w;
}
void addedge(int u,int v,int w) {
    add(u,v,w),add(v,u,0);
}
int bfs(int s,int t) {
    memset(dep,0,sizeof(dep));
    memcpy(cnr,lnk,sizeof(lnk));
    std::queue<int> q;
    q.push(s),dep[s]=1;
    while(!q.empty()) {
        int u=q.front(); q.pop();
        for(int i=lnk[u];i;i=nxt[i]) {
            int v=ter[i];
            if(val[i]&&!dep[v]) q.push(v),dep[v]=dep[u]+1;
        }
    }
    return dep[t];
}
int dfs(int u,int t,int flow) {
    if(u==t) return flow;
    int ans=0;
    for(int i=cnr[u];i&&ans<flow;i=nxt[i]) {
        cnr[u]=i;
        int v=ter[i];
        if(val[i]&&dep[v]==dep[u]+1) {
            int x=dfs(v,t,std::min(val[i],flow-ans));
            if(x) val[i]-=x,val[i^1]+=x,ans+=x;
        }
    }
    if(ans<flow) dep[u]=-1;
    return ans;
}
int dinic(int s,int t) {
    int ans=0;
    while(bfs(s,t)) {
        int x;
        while((x=dfs(s,t,1<<30))) ans+=x;
    }
    return ans;
}
int main() {
    scanf("%d",&n);
    int ans=0;
    for(int i=1;i<=n;++i) scanf("%d",&a[i]),ans+=a[i];
    for(int i=1;i<=n;++i) scanf("%d",&b[i]),ans+=b[i];
    scanf("%d",&m);
    int S=0,T=m+n+m+1;
    for(int i=1;i<=n;++i) addedge(S,id(2,i),a[i]),addedge(id(2,i),T,b[i]);
    for(int i=1;i<=m;++i) {
        int k,c1,c2;
        for(scanf("%d%d%d",&k,&c1,&c2);k--;) {
            int x;
            scanf("%d",&x);
            addedge(id(1,i),id(2,x),1<<30);
            addedge(id(2,x),id(3,i),1<<30);
        }
        addedge(S,id(1,i),c1);
        addedge(id(3,i),T,c2);
        ans+=c1+c2;
    }
    printf("%d\n",ans-dinic(S,T));
    return 0;
}
0%