隐藏
「bzoj4177」Mike的农场 - 最小割+捆绑模型 | Bill Yang's Blog
0%

「bzoj4177」Mike的农场 - 最小割+捆绑模型

题目大意

    Mike有一个农场,这个农场$n$个牲畜围栏,现在他想在每个牲畜围栏中养一只动物,每只动物可以是牛或羊,并且每个牲畜围栏中的饲养条件都不同,其中第$i$个牲畜围栏中的动物长大后,每只牛可以卖$a[i]$元,每只羊可以卖$b[i]$元,为了防止牛羊之间相互影响,Mike找到了$m$条规律,每条规律给出一个三元组$(i,j,k)$表示如果第$i$个围栏和第$j$个围栏养的是不同的动物,那么Mike就需要花费$k$的代价请人帮忙处理牛羊之间的影响。不过同时Mike也发现$k$条特殊的规则$(S,a,b)$,表示如果$S$中所有牲畜围栏中都养的是动物$a$,那么Mike可以获得$b$的额外收入。现在Mike想知道他该在哪些围栏中饲养什么动物才能使得总收益最大,为了简化问题,你只需要输出最大收益。


题目分析

捆绑模型


代码

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
125
126
127
128
129
130
131
132
133
134
135
136
137
138
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}

const int maxn=20005;

struct Edge {
int from,to,cap,flow;
Edge(int x=0,int y=0,int c=0,int f=0):from(x),to(y),cap(c),flow(f) {}
};

struct Dinic {
int n,m,s,t;
vector<Edge>edges;
vector<int>G[maxn];
bool vst[maxn];
int dist[maxn],cur[maxn];
void init(int n) {
this->n=n;
edges.clear();
for(int i=1; i<=n; i++)G[i].clear();
}
void AddEdge(int x,int y,int v) {
edges.push_back(Edge(x,y,v,0));
edges.push_back(Edge(y,x,0,0));
m=edges.size();
G[x].push_back(m-2);
G[y].push_back(m-1);
}
bool bfs() {
memset(vst,0,sizeof(vst));
memset(dist,0,sizeof(dist));
queue<int>Q;
Q.push(t);
vst[t]=1;
while(!Q.empty()) {
int Now=Q.front();
Q.pop();
for(int id:G[Now]) {
Edge& e=edges[id^1];
int Next=e.from;
if(!vst[Next]&&e.cap>e.flow) {
vst[Next]=1;
dist[Next]=dist[Now]+1;
Q.push(Next);
}
}
}
return vst[s];
}
int dfs(int Now,int a) {
if(Now==t||a==0)return a;
int flow=0;
for(int& i=cur[Now]; i<G[Now].size(); i++) {
Edge& e=edges[G[Now][i]];
int Next=e.to;
if(dist[Now]-1!=dist[Next])continue;
int nextflow=dfs(Next,min(a,e.cap-e.flow));
if(nextflow>0) {
e.flow+=nextflow;
edges[G[Now][i]^1].flow-=nextflow;
flow+=nextflow;
a-=nextflow;
if(a==0)break;
}
}
return flow;
}
int maxflow(int s,int t) {
this->s=s;
this->t=t;
int flow=0;
while(bfs()) {
memset(cur,0,sizeof(cur));
flow+=dfs(s,INT_MAX);
}
return flow;
}
} dinic;

int n,m,k,sum=0;

int main() {
n=Get_Int();
m=Get_Int();
k=Get_Int();
int S=n+1,T=n+2,cnt=T;
for(int i=1; i<=n; i++) {
int v=Get_Int();
sum+=v;
dinic.AddEdge(i,T,v);
}
for(int i=1; i<=n; i++) {
int v=Get_Int();
sum+=v;
dinic.AddEdge(S,i,v);
}
for(int i=1; i<=m; i++) {
int x=Get_Int(),y=Get_Int(),v=Get_Int();
dinic.AddEdge(x,y,v);
dinic.AddEdge(y,x,v);
}
for(int i=1; i<=k; i++) {
int t=Get_Int(),a=Get_Int(),v=Get_Int(),p=++cnt;
sum+=v;
if(a==0)dinic.AddEdge(p,T,v);
else dinic.AddEdge(S,p,v);
for(int j=1; j<=t; j++) {
int x=Get_Int();
if(a==0)dinic.AddEdge(x,p,INT_MAX/2);
else dinic.AddEdge(p,x,INT_MAX/2);
}
}
printf("%d\n",sum-dinic.maxflow(S,T));
return 0;
}
姥爷们赏瓶冰阔落吧~