自动搬运

查看原文

来自洛谷，原作者为

	不存在之人 早已……无所谓了

搬运于2025-08-24 21:57:19，当前版本为作者最后更新于2018-06-10 10:24:11，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

什么是最大权闭合子图：

先解释一下有向图的闭合图：闭合图内任意点的任意后继也一定还在闭合图中。

物理意义：事物间依赖关系:一个事件要发生，它需要的所有前提也都一定要发生。

最大权闭合图：点权之和最大的闭合图

最大权闭合图构图方法：

1.增加源s汇t

2.源s连接原图的正权点，容量为相应点权

3.原图的负权点连接汇t，容量为相应点权的相反数

4.原图边的容量为正无限。

最大权闭合图 解决：

闭合图V的权为正权点总和减去对应割的容量

当割最小时，闭合图权最大

NOI2006 最大获利：

1.将原题中的边和点都看成事件。

2.边事件依赖边的两个端点事件的发生。这与闭合图的性质相似。

3.构造性地，将边转化为点事件。

4.将所有边都转化为事件点，原图便转化为一个二分图。

5.解决该二分图的最大权闭合图即可

#include<cmath>  
#include<cstdio>  
#include<cstring>  
#include<iostream>  
#include<algorithm>  
using namespace std;  
const int N=120005;  
const int M=400005;  
const int inf=2100000000;  
int n,m,S,T;  
int from[M],to[M],nxt[M],w[M],lj[N],cnt=-1;  
void insert(int f,int t,int p)  
{  
    to[++cnt]=t;  
    nxt[cnt]=lj[f];  
    lj[f]=cnt;  
    w[cnt]=p;  
    to[++cnt]=f;  
    nxt[cnt]=lj[t];  
    lj[t]=cnt;  
    w[cnt]=0;  
}  
int d[N],q[N*2];  
bool bfs()  
{  
    memset(d,0,sizeof(d));  
    int h=1,t=1,x,j;  
    q[1]=S,d[S]=1;  
    while(h!=t+1)  
    {  
        x=q[h];  
        for(int i=lj[x];i>=0;i=nxt[i])  
        if(w[i]&&!d[to[i]])  
        {  
            d[to[i]]=d[x]+1;  
            q[++t]=to[i];  
            if(t==N) t=0;  
        }  
        if(++h==N) h=0;  
    }  
    if(d[T]) return true;  
    return false;   
}  
int dfs(int x,int v)  
{  
    if(x==T||v==0) return v;  
    int f,ret=0;  
    for(int i=lj[x];i>=0;i=nxt[i])  
    if(d[to[i]]==d[x]+1)  
    {  
        f=dfs(to[i],min(w[i],v));  
        w[i]-=f;  
        w[i^1]+=f;  
        v-=f;  
        ret+=f;  
        if(v==0) break;  
    }  
    return ret;  
}  
int main()  
{  
    scanf("%d%d",&n,&m);  
    T=m+n+1,S=0;  
    int x,y,p;  
    for(int i=0;i<=T;i++) lj[i]=-1;  
    for(int i=1;i<=n;i++)  
    {  
        scanf("%d",&x);  
        insert(0,i,x);  
    }  
    int sum=0,ans=0;  
    for(int i=1;i<=m;i++)  
    {  
        scanf("%d%d%d",&x,&y,&p);  
        insert(n+i,T,p);  
        insert(x,n+i,inf);  
        insert(y,n+i,inf);  
        sum+=p;  
    }  
    while(bfs()) ans+=dfs(S,inf);  
    printf("%d",sum-ans);  
}