题解 51nod2935 土地划分

题解 51nod2935 土地划分

题面

51nod

解析

一眼最小割考虑怎么建图.

从最简单的边连起:对于每个点 $i$,连边 $(S,i,A_i)$,$(i,T,B_i)$,

($S,T$ 分别为源,汇点)

然后考虑每条边 $(x,y)$的问题,

如果两个点都划分给 $A$,那在图上就是两个点到 $T$ 的边都被割掉了,

因此我们新建一个点 $z$ ,连边 $(x,z,\inf),(y,z,\inf),(z,T,EB_i)$

即割掉都划分给 $B$ 的收益.

而都划分给 $B$ 的连边方式同理,这里就不再赘述.

(如果硬是不知道可以看代码)

然后考虑 $EC$ 的影响,不妨设图中还存在 $S\to x$ 及 $y\to T$ 这两条边.

那么我们要割掉 $EC$ 的代价.

对于边 $(x,y)$,连边 $(x,y,EC_i),(y,x,EC_i)$ 即可.

code

$\texttt{DINIC}$ 加点优化就能过?

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
#include <iostream>
#include <stdio.h>
#include <cstring>
#include <queue>
#define ll long long
#define filein(a) freopen(a,"r",stdin)
#define fileout(a) freopen(a,"w",stdout);
using namespace std;

inline int read(){
int sum=0,f=1;char c=getchar();
while((c<'0'||c>'9')&&c!=EOF){if(c=='-') f=-1;c=getchar();}
while(c>='0'&&c<='9'&&c!=EOF){sum=sum*10+c-'0';c=getchar();}
return sum*f;
}

const int N=50005;
const int INF=0x3f3f3f3f;
struct val{int a,b,c,x,y;}v[N<<1];
int n,m,S,T;ll ans;

namespace nw{
struct edge{int to,next,v;}e[N<<4];
int head[N<<3],cnt=1;
int d[N<<3],cur[N<<3];
queue<int> que;
inline void add(int x,int y,int v){
e[++cnt]=(edge){head[x],y,v};head[x]=cnt;
e[++cnt]=(edge){head[y],x,0};head[y]=cnt;
}
inline bool bfs(){
memset(d,0,sizeof(d));
memcpy(cur,head,sizeof(cur));
que.push(S);d[S]=1;
while(!que.empty()){
int x=que.front();que.pop();
for(int i=head[x];i;i=e[i].to){
int k=e[i].next;
if(d[k]||!e[i].v) continue;
d[k]=d[x]+1;que.push(k);
}
}
return d[T];
}
inline int dfs(int x,int mi){
if(x==T||!mi) return mi;
int flow=0;
for(int &i=cur[x];i;i=e[i].to){
int k=e[i].next;
if(!e[i].v||d[k]!=d[x]+1) continue;
int ret=dfs(k,min(mi,e[i].v));
mi-=ret;flow+=ret;
e[i].v-=ret;e[i^1].v+=ret;
if(!mi) break;
}
if(mi) d[x]=-1;
return flow;
}
inline ll DINIC(){
ll ret=0;
while(bfs()) ret+=dfs(S,INF);
return ret;
}
}
using namespace nw;

int main(){
n=read();m=read();S=1;T=n;
for(int i=2;i<n;i++) v[i].a=read();
for(int i=2;i<n;i++) v[i].b=read();
for(int i=n+1;i<=n+m;i++){
v[i].x=read(),v[i].y=read();
v[i].a=read(),v[i].b=read(),v[i].c=read();
}
for(int i=2;i<n;i++){
ans+=v[i].a+v[i].b;
add(S,i,v[i].a);add(i,T,v[i].b);
}
for(int i=n+1;i<=n+m;i++){
ans+=v[i].a+v[i].b;
add(v[i].x,v[i].y,v[i].c);add(v[i].y,v[i].x,v[i].c);
add(S,i,v[i].a);add(i+m,T,v[i].b);
add(i,v[i].x,INF);add(i,v[i].y,INF);
add(v[i].x,i+m,INF);add(v[i].y,i+m,INF);
}
printf("%lld\n",ans-DINIC());
return 0;
}
感谢您又打赏