题解 P3410 【拍照】

· · 题解

介绍一下闭合图的概念，闭合图是建立在有向图上的，就是对于一个集合内每个点，它能达到的所有点都在这个集合里面。

对于样例：

输入
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的边权和

也就是：

闭合图最大权值=全部正权点之和-最小割

应该可以理解边的含义了吧

部分参考博客

代码：

#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;
}