洛谷 P1361. 小M的作物

发表于 分类于

链接

https://www.luogu.com.cn/problem/P1361

题意

有 $n$ 种作物，两块耕地 $A$ 和 $B$

第 $i$ 种作物种植在 $A$ 中收益为 $a_i$，种植在 $B$ 中收益为 $b_i$

另有 $m$ 种组合，每种组合有 $k$ 种作物，如果这 $k$ 种作物共同种在 $A$ 中收益为 $c1_i$，共同种在 $B$ 中收益为 $c2_i$

求种植的最大收益

思路

  • 先不考虑 $m$ 种组合

把源点 $s$ 当作耕地 $A$，源点 $t$ 当作耕地 $B$

$s$ 与每个作物 $i$ 之间建立一条权值为 $a_i$ 的边，每个作物 $i$ 与 $t$ 之间建立一条权值为 $b_i$ 的边，代表收益

显然所有边权和与最小割的差就是种植的最大收益

  • 接下来考虑加入 $m$ 种组合

将每种组合拆成两个点，设为 $p,q$，$s$ 与 $p$ 之间建立一条权值为 $c_1$ 的边，$q$ 与 $t$ 之间建立一条权值为 $c_2$ 的边，$p,q$ 分别与该种组合中的 $k$ 个点建立一条边权为正无穷的边（这些正无穷的边必不可能被割）

图中 $u,v$ 为某种组合中的两个点

易发现最小割只有 ${1,2,5},{3,4,6},{1,4,5,6},{2,3,5,6}$ 这四种情况

并且割去边与剩余边（除权为正无穷）之间的存在关系与题意均符合

因此根据最大流最小割定理，求出最大流，即最小割，所有边（除权为正无穷）的和与最小割的差即为最大收益

代码

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
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,m,s,t,d[N],cur[N],cnt;
long long sum;
vector<pair<int,long long> > e;
vector<int> G[N];
void init() {
    e.clear();
    for(int i=1;i<=n;i++) G[i].clear();
}
void addedge(int u,int v,long long w) {
    e.push_back(make_pair(v,w));
    e.push_back(make_pair(u,0));
    G[u].push_back(e.size()-2);
    G[v].push_back(e.size()-1);
}
bool bfs() {
    for(int i=1;i<=n;i++) d[i]=0;
    queue<int> q;
    q.push(s);
    while(!q.empty()) {
        int u=q.front();
        q.pop();
        for(auto x:G[u]) {
            int &v=e[x].first;
            long long &w=e[x].second;
            if(v==s||d[v]||w<=0) continue;
            d[v]=d[u]+1;
            q.push(v);
        }
    }
    if(d[t]) return true;
    return false;
}
long long dfs(int u,long long a) {
    if(u==t) return a;
    long long f,flow=0;
    for(int &i=cur[u];i<G[u].size();i++) {
        int &v=e[G[u][i]].first;
        long long &w=e[G[u][i]].second;
        if(d[v]!=d[u]+1||w<=0||(f=dfs(v,min(a,w)))<=0) continue;
        w-=f;
        e[G[u][i]^1].second+=f;
        a-=f;
        flow+=f;
        if(a==0) break;
    }
    return flow;
}
long long dinic() {
    long long flow=0;
    while(bfs()) {
        for(int i=1;i<=n;i++) cur[i]=0;
        flow+=dfs(s,0x7fffffff);
    }
    return flow;
}
int main() {
    scanf("%d",&n);
    s=n+1,t=n+2;
    for(int i=1;i<=n;i++) {
        long long w;
        scanf("%lld",&w);
        addedge(s,i,w);
        sum+=w;
    }
    for(int i=1;i<=n;i++) {
        long long w;
        scanf("%lld",&w);
        addedge(i,t,w);
        sum+=w;
    }
    scanf("%d",&m);
    for(int i=1;i<=m;i++) {
        int k;
        long long w1,w2;
        scanf("%d%lld%lld",&k,&w1,&w2);
        addedge(s,t+cnt+1,w1);
        addedge(t+cnt+2,t,w2);
        for(int i=1;i<=k;i++) {
            int x;
            scanf("%d",&x);
            addedge(t+cnt+1,x,0x7fffffff);
            addedge(x,t+cnt+2,0x7fffffff);
        }
        cnt+=2;
        sum+=w1+w2;
    }
    n+=2+cnt;
    printf("%lld\n",sum-dinic());
    return 0;
}