题解 P3410 【拍照】
Rachel_in
2019-05-29 11:12:03
介绍一下闭合图的概念，闭合图是建立在有向图上的，就是对于一个集合内每个点，它能达到的所有点都在这个集合里面。
对于样例：
```
输入
2 3
10 1 2 0
25 2 3 0
5 6 7
输出
17
```
我们构成的图为：
对于最大权值闭合图，我们需要用**最小割**来做。
我们重新构图：
**前置结论**：最大权值=闭合图的正权值之和-最小割
**理解边的含义**：
我们做的最小割一定不会切到无穷大的边，所以割里的边都是$S->u$或者$u->T$。
**对于割掉一个$S->u$的边含义为在闭合图中不选择$u$这个点,对于割掉一个$u->T$的边含义为在闭合图中选择$u$这个点。**
(注意：这里边的含义很难去想它为什么要这么定义的时候，先看下去，之后会明白的)
举个例子：我们在网络流那张图里割去权值为10,5,7这些边，含义为不选择要求1，选择1,3这些点，也就是一共选择要求2,1,3这三个点，这不是一个闭合图，因为2这个点没选。然后我们发现网络流里有非0流的，不是割，**也就是说如果选择的不是网络流的割，那么选到的点集必定不是闭合图**。
证明：如果$S$与$T$连通，则存在点$u$,$v$，使得$S$到$u$有边，$u$到$v$连通，$v$到$T$有边，所以$v$一定是$u$的后继，但选择了$u$，没有选择$v$，不是闭合子图。
**得出结论：只有$S$与$T$不连通时，才能得到闭合子图。**
于是我们要求出的是割，至于要将答案最大化：
最小割=不选的$S$到$u$的边权和+选择的$u$到$S$的边权和
闭合图最大权值=全部正权点之和-不选的正权点之和+选择的负权点之和
加上选择的负权点之和就相当于减去选择的负权点的绝对值之和，也就是选择的$u$到$S$的边权和
所以:
**闭合图最大权值=全部正权点之和-不选的$S$到$u$的边权和-选择的$u$到$S$的边权和**
也就是：
**闭合图最大权值=全部正权点之和-最小割**
应该可以理解边的含义了吧
[部分参考博客](https://blog.csdn.net/can919/article/details/77603353)
**代码**：
```cpp
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int res=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-f;ch=getchar();}
while(ch>='0'&&ch<='9'){res=(res<<3)+(res<<1)+ch-'0';ch=getchar();}
return res*f;
}
const int N=255;
const int M=40555;
const int inf=1e7;
int S,T,n,m,fir[N],cur[N],dep[N],nxt[M],go[M],val[M],cnt=1,maxflow,ans;
queue<int> Q;
inline void Add(int u,int v,int w){
nxt[++cnt]=fir[u];
fir[u]=cnt;
go[cnt]=v;
val[cnt]=w;
}
inline bool bfs(){
for(int i=S;i<=T;i++) dep[i]=-1;
dep[S]=0;
Q.push(S);
while(!Q.empty()){
int u=Q.front();Q.pop();
for(int e=fir[u];e;e=nxt[e]){
int v=go[e];
if(dep[v]==-1&&val[e]>0){
dep[v]=dep[u]+1;
Q.push(v);
}
}
}
if(dep[T]==-1) return 0;
else return 1;
}
int dfs(int u,int flow){
if(u==T) return flow;
for(int &e=cur[u];e;e=nxt[e]){
int v=go[e];
if(dep[v]==dep[u]+1&&val[e]>0){
int f=dfs(v,min(flow,val[e]));
if(f>0){
val[e]-=f;val[e^1]+=f;
return f;
}
}
}
return 0;
}
void Dinic(){
while(bfs()){
for(int i=S;i<=T;i++) cur[i]=fir[i];
while(int d=dfs(S,inf)){
maxflow+=d;
}
}
}
int main(){
m=read();n=read();
S=0;T=m+n+1;
for(int i=1;i<=m;i++){
int w=read();
ans+=w;
Add(S,i,w);Add(i,S,0);
int x=read();
while(x){
Add(i,m+x,inf);Add(m+x,i,0);
x=read();
}
}
for(int i=1;i<=n;i++){
int w=read();
Add(m+i,T,w);Add(T,m+i,0);
}
Dinic();
printf("%d",ans-maxflow);
return 0;
}
```