我的极少数网络流题解（？
首先考虑将问题转化为最大权闭合子图模型。
由于要求最小化费用，不妨考虑最大化可以从初始的 \(\sum\limits_{i=1}^n w_i\) 中除去的费用。
对原图中的每个点，建一个点权为 \(-b_i\) 的点，代表将这个点的 \(a_i\) 变为 \(0\)。
将原图中每个点的所有出边按照出点的权升序，那么显然是除去一个后缀才有效果，将这些边一一建点，点权为出点的 \(a_i\) 的差，并向下一条边对应的点连边。
当然，这些点还要向出点对应的点连边。
用初始的 \(\sum\limits_{i=1} w_i\) 减去最大权闭合子图的点权和，即是答案。
关于最大权闭合子图，有十分经典的最小割模型转化，此处不再赘述。
代码： 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
using namespace std;
const int N = 1e3;
const int M = 5e4;
int n,m,s,t,tot;
int a[N + 5],b[N + 5];
int ans;
vector<int> e[N + 5];
inline bool cmp(int x,int y)
{
return a[x] < a[y];
}
namespace Dinic
{
const int N = 1e5;
const int M = 2e5;
int n;
int to[(M << 1) + 5],val[(M << 1) + 5],pre[(M << 1) + 5],first[N + 5],cur[N + 5],edge_tot;
inline int init()
{
memset(first,-1,sizeof first);
return 0;
}
int Init = init();
inline void add_edge(int u,int v,int w)
{
int &tot = edge_tot;
to[tot] = v,val[tot] = w,pre[tot] = first[u],first[u] = tot++;
}
inline void add(int u,int v,int w)
{
add_edge(u,v,w),add_edge(v,u,0);
}
int head,tail,q[N + 5],dep[N + 5],vis[N + 5];
int bfs()
{
head = tail = 0;
memset(vis,0,sizeof vis);
memset(dep,0x3f,sizeof dep);
dep[s] = 0,vis[s] = 1,q[++tail] = s;
while(head < tail)
{
int p = q[++head];
vis[p] = 0;
for(register int i = first[p];~i;i = pre[i])
if(val[i] && dep[to[i]] > dep[p] + 1)
{
dep[to[i]] = dep[p] + 1;
if(!vis[to[i]])
vis[to[i]] = 1,q[++tail] = to[i];
}
}
return dep[t] ^ 0x3f3f3f3f;
}
int maxflow;
int dfs(int p,int flow)
{
if(p == t)
return (maxflow += flow,flow);
int ret = 0,used = 0;
for(register int &i = cur[p];~i;i = pre[i])
if(val[i] && dep[to[i]] == dep[p] + 1 && (ret = dfs(to[i],min(flow - used,val[i]))))
{
used += ret,val[i] -= ret,val[i ^ 1] += ret;
if(used >= flow)
break;
}
return used;
}
int dinic()
{
while(bfs())
memcpy(cur,first,sizeof cur),dfs(s,0x3f3f3f3f);
return maxflow;
}
}
int main()
{
scanf("%d%d",&n,&m);
for(register int i = 1;i <= n;++i)
scanf("%d",a + i);
for(register int i = 1;i <= n;++i)
scanf("%d",b + i);
int u,v;
for(register int i = 1;i <= m;++i)
scanf("%d%d",&u,&v),e[u].push_back(v);
Dinic::n = n + m + 2,s = n + m + 1,t = n + m + 2;
for(register int i = 1;i <= n;++i)
{
sort(e[i].begin(),e[i].end(),cmp);
for(register int j = 0;j < e[i].size();++j)
Dinic::add(s,n + ++tot,a[e[i][j]] - (j ? a[e[i][j - 1]] : 0)),j + 1 < e[i].size() && (Dinic::add(n + tot,n + tot + 1,0x3f3f3f3f),1),Dinic::add(n + tot,e[i][j],0x3f3f3f3f);
Dinic::add(i,t,b[i]);
}
ans = Dinic::dinic();
printf("%d\n",ans);
}