最大权闭合子图

定义

1.闭合子图：图中所有点的出边所连的点均在图内

2.最大权闭合子图：闭合子图中点权和最大的子图

构造方法&算法

将题目中的依赖关系抽象为闭合图，建立超级源，超级汇，源点向权值为正的点连一条容量为权值的边，权值为负的点向汇点连一条容量为权值绝对值的边，其余边容量改为INF。求最小割，记为C，则有Ans=正点权之和-C

证明

1. 最小割必为简单割(割边全为连接S或T的边)
2. 简单割必为闭合图
3. S所在的集合为最大权闭合图

例题

NOI2006最大获利

代码

#include<cstring>
#include<cstdio>
#include<iostream>
#include<algorithm>
#define INF 0x3f3f3f3f
#define N 60010
#define M 400010
using namespace std;

int n,m,i,lsum=1,x,y,z,Found,flow,Sum,al,cnt;
int head[N],gaps[N],gap[N],cur[N],mingap[N];

struct Edge{
    int fl,re,next,t;
}e[M];

inline int Min(int a,int b){return (a<b)?a:b;}

inline void Add(int s,int t,int fl){
    e[lsum].t=t;    e[lsum].re=lsum+1;
    e[lsum].fl=fl;  e[lsum].next=head[s];   head[s]=lsum++;
    e[lsum].t=s;    e[lsum].re=lsum-1;
    e[lsum].next=head[t];   head[t]=lsum++;
}

inline void Sap(int x){
    int F=al,i=0;
    if (x==cnt){Found=1;    flow+=al;   return;}
    for (i=cur[x];i;i=e[i].next)
    if (e[i].fl){
        if (gap[e[i].t]+1==gap[x]){
            al=Min(al,e[i].fl); Sap(e[i].t);
            if (gap[1]>=cnt)    return;
            if (Found)  {cur[x]=i;  break;}
            al=F;
        }
        mingap[x]=Min(mingap[x],gap[e[i].t]);
    }
    if (!Found){
        gaps[gap[x]]--; if (!gaps[gap[x]])  gap[1]=cnt;
        gaps[gap[x]=mingap[x]+1]++; cur[x]=head[x]; mingap[x]=cnt-1;
    }   else e[i].fl-=al,e[e[i].re].fl+=al;
}

int main(){
    freopen("profit.in","r",stdin);
    freopen("profit.out","w",stdout);
    scanf("%d%d",&n,&m);
    cnt=n+m+2;
    for (i=1;i<=n;i++){
        scanf("%d",&x); Add(1+m+i,cnt,x);
    }
    for (i=1;i<=m;i++){
        scanf("%d%d%d",&x,&y,&z);
        Add(1,1+i,z);   Add(1+i,1+m+x,INF); Add(1+i,1+m+y,INF);
        Sum+=z;
    }
    gaps[0]=cnt;
    for (i=1;i<=cnt;i++)    cur[i]=head[i],mingap[i]=cnt-1;
    while (gap[1]<cnt){
        Found=0;    al=INF; Sap(1);
    }
    gaps[0]=cnt;
    memset(gap,0,sizeof(gap));
    for (i=1;i<=cnt;i++)    cur[i]=head[i],mingap[i]=cnt-1;
    while (gap[1]<cnt){
        Found=0;    al=INF; Sap(1);
    }
    printf("%d\n",Sum-flow);
    return 0;
}

二分图

概念

1. 边覆盖：从图G中选出一个边集，使其覆盖所有的点
2. 独立集：从图G中选出一个点集，使其两两间不相连
3. 点覆盖：从图G中选出一个点集，使其覆盖所有的边

关系

对任意无孤立点的图：

最大匹配数+最小边覆盖=点数

证明：最大匹配数已经覆盖了一些点，此时向匹配后的图中加边，每条新边至多覆盖一个点（否则不是最大匹配），易知二者之和为N。

对于任意图：

最大独立集+最小点覆盖=点数

证明：最大独立集的补集显然与最大独立集的所有点(除孤立点)联通，得证。

对于二分图：

最大匹配数=最小点覆盖

最大独立集=最小边覆盖

最大点权独立集=所有点权-最小点权覆盖集=所有点权-最小简单割