bzoj 1497（最大权闭合图/最小割）

ゝ一纸荒年。 2021-11-05 13:16 277阅读 0赞

# [传送门][Link 1] #

# 题意： #

有$n$个通信塔，建立第$i$个通讯塔需要花费$p\_i$元。同时有$m$个人，对于第$i$个人，如果$a\_i$号塔以及$b\_i$号塔被建了，则会赚$c\_i$元。问最大的收益。

# 分析： #

最大权闭合图的经典的模型。

所谓闭合图，即要满足一定的依赖关系，即一个事件要发生，它需要的所有前提也都一定要发生。

而最大权闭合图即为**点权最大**的闭合图。

而这类问题的一个比较经典的建图方法是：

1.  将能够使收益增加的点与超级源点相连，边的容量为将会增加的收益值（设之为$a\_i$）
2.  将能够使收益减少的点与超级汇点相连，边的容量为将会减少的收益值（设之为$b\_i$）
3.  将原来的闭合图之间连接一条容量为无穷的边。

最后的闭合图的最大权为$\\sum a\_i-res$。而$res$的值为需要损失的收益且其值一定为原图的最小割。

--------------------

简单说明（全是胡扯） ：

要使得$\\sum a\_i-res$最大，则显然我们需要损失的收益值$res$最小。而因为在闭合图中，某些事件（亦或者说，某些能使得收益增加的事件）的发生，必然会导致它后面所依赖的所有事件（可能部分事件会使得收益减少）均发生，而在这个过程中，可能会产生很大的损失。

因此我们考虑将部分边割掉。

我们发现，如果我们将某个能使得收益增加的点与源点的边割掉，则必然会导致我们得不到该点带来的贡献，这个我们可以看作损失；同理，如果我们将某个能使得收益减少的点与汇点的边割掉，我们则需要付出一定代价，这也可以看错损失。

而我们目前需要求得的是最小的损失$res$，因此我们只需要求出原图的最小割即可。

--------------------

而对于上面的题目，我们发现，使得每个人满意是能够使得答案增加的，而使得每个人满意的制约条件是会使得答案减少的，因此我们把人和超级源点相连，灯塔与超级汇点相连，最后跑一边最大流，最后的答案即为$\\sum c\_i-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;
    }

转载于:https://www.cnblogs.com/Chen-Jr/p/11007134.html

[Link 1]: https://www.lydsy.com/JudgeOnline/problem.php?id=1497