传送门
题意：
有
n
n
n个通信塔，建立第
i
i
i个通讯塔需要花费
p
i
p_i
pi元。同时有
m
m
m个人，对于第
i
i
i个人，如果
a
i
a_i
ai号塔以及
b
i
b_i
bi号塔被建了，则会赚
c
i
c_i
ci元。问最大的收益。
分析：
最大权闭合图的经典的模型。
所谓闭合图，即要满足一定的依赖关系，即一个事件要发生，它需要的所有前提也都一定要发生。
而最大权闭合图即为点权最大的闭合图。
而这类问题的一个比较经典的建图方法是：
将能够使收益增加的点与超级源点相连，边的容量为将会增加的收益值（设之为
a
i
a_i
ai）将能够使收益减少的点与超级汇点相连，边的容量为将会减少的收益值（设之为
b
i
b_i
bi）将原来的闭合图之间连接一条容量为无穷的边。
最后的闭合图的最大权为
∑
a
i
−
r
e
s
\sum a_i-res
∑ai−res。而
r
e
s
res
res的值为需要损失的收益且其值一定为原图的最小割。
简单说明（全是胡扯） ：
要使得
∑
a
i
−
r
e
s
\sum a_i-res
∑ai−res最大，则显然我们需要损失的收益值
r
e
s
res
res最小。而因为在闭合图中，某些事件（亦或者说，某些能使得收益增加的事件）的发生，必然会导致它后面所依赖的所有事件（可能部分事件会使得收益减少）均发生，而在这个过程中，可能会产生很大的损失。
因此我们考虑将部分边割掉。
我们发现，如果我们将某个能使得收益增加的点与源点的边割掉，则必然会导致我们得不到该点带来的贡献，这个我们可以看作损失；同理，如果我们将某个能使得收益减少的点与汇点的边割掉，我们则需要付出一定代价，这也可以看错损失。
而我们目前需要求得的是最小的损失
r
e
s
res
res，因此我们只需要求出原图的最小割即可。
而对于上面的题目，我们发现，使得每个人满意是能够使得答案增加的，而使得每个人满意的制约条件是会使得答案减少的，因此我们把人和超级源点相连，灯塔与超级汇点相连，最后跑一边最大流，最后的答案即为
∑
c
i
−
m
a
x
f
l
o
w
\sum c_i-maxflow
∑ci−maxflow
代码：
#include <bits/stdc++.h>
using namespace std
;
const int maxn
=1000005;
const int inf
=0x3f3f3f3f;
struct Node
{
int to
,val
,next
;
}q
[maxn
<<1];
int head
[maxn
],cnt
=0,dep
[maxn
],cur
[maxn
],vis
[maxn
];
int sp
,ep
,maxflow
;
void init(){
memset(head
,-1,sizeof(head
));
cnt
=2,maxflow
=0;
}
void add_edge(int from
,int to
,int val
){
q
[cnt
].to
=to
;
q
[cnt
].val
=val
;
q
[cnt
].next
=head
[from
];
head
[from
]=cnt
++;
q
[cnt
].to
=from
;
q
[cnt
].val
=0;
q
[cnt
].next
=head
[to
];
head
[to
]=cnt
++;
}
bool bfs(int n
){
for(int i
=0;i
<=n
;i
++){
cur
[i
]=head
[i
],dep
[i
]=0x3f3f3f3f;
vis
[i
]=0;
}
dep
[sp
]=0;
queue
<int>que
;
que
.push(sp
);
while(!que
.empty()){
int x
=que
.front();
que
.pop();
vis
[x
]=0;
for(int i
=head
[x
];i
!=-1;i
=q
[i
].next
){
int to
=q
[i
].to
;
if(dep
[to
]>dep
[x
]+1&&q
[i
].val
){
dep
[to
]=dep
[x
]+1;
if(!vis
[to
]){
que
.push(to
);
vis
[to
]=1;
}
}
}
}
if(dep
[ep
]!=inf
) return true;
else return false;
}
int dfs(int x
,int flow
){
int rlow
=0;
if(x
==ep
){
maxflow
+=flow
;
return flow
;
}
int used
=0;
for(int i
=cur
[x
];i
!=-1;i
=q
[i
].next
){
cur
[x
]=i
;
int to
=q
[i
].to
;
if(q
[i
].val
&&dep
[to
]==dep
[x
]+1){
if(rlow
=dfs(to
,min(flow
-used
,q
[i
].val
))){
used
+=rlow
;
q
[i
].val
-=rlow
;
q
[i
^1].val
+=rlow
;
if(used
==flow
) break;
}
}
}
return used
;
}
int dinic(int n
){
while(bfs(n
)){
dfs(sp
,inf
);
}
return maxflow
;
}
int main()
{
int n
,m
;
scanf("%d%d",&n
,&m
);
init();
sp
=0,ep
=n
+m
+1;
for(int i
=1;i
<=n
;i
++){
int vals
;
scanf("%d",&vals
);
add_edge(i
+m
,ep
,vals
);
}
int res
=0;
for(int i
=1;i
<=m
;i
++){
int from
,to
,val
;
scanf("%d%d%d",&from
,&to
,&val
);
add_edge(sp
,i
,val
);
add_edge(i
,m
+from
,inf
);
add_edge(i
,m
+to
,inf
);
res
+=val
;
}
printf("%d\n",res
-dinic(n
+m
+1));
return 0;
}
