博客
关于我
强烈建议你试试无所不能的chatGPT，快点击我
【暖*墟】#网络流# 最大权闭合子图
阅读量：5076 次
发布时间：2019-06-12

本文共 11736 字，大约阅读时间需要 39 分钟。

【相关概念详解】

 

闭合图：有向图的一个点集，且这个点集的所有出边仍然指向该点集。

最大权闭合图：（每一个点有一个权值）在所有的合法闭合图中，点权之和最大的图。

 

处理问题：权值有正有负，重复选只算一次，选择有相互关联性 的问题。

 

首先有一个有向连通图（闭合图），每个点带有一个权值，例如：

 

 

 

造出一个超级源点S和一个超级汇点T，把S连边到所有带有正权的点上，每条边的容量是这个点的权；

把所有带负权的点连边到T，每条边的容量是这个点的权的相反数（正值）。原来的边的容量设成无限大。

所有的点按权值的正负连接到s和t上，转换成一个边权值有向图。

 

 

 

最大权闭合图的最大权 = 所有正权值之和 — 最小割容量（最大流的值） 。

 

步骤归纳：1. 建立超级源点s，超级汇点t。

                  2. 所有点权为正数的点i，建边 s->i，容量为(正)点权。

                  3. 所有点权为负数的点i，建边i->t，容量为(负)点权绝对值。

                  4. 原图建图后，（互相关联影响的）边容量设为正无穷。

                  5.最大权闭合图的权值 = 正权点之和 - (s->t)最大流。

 

建图方法的推导

 

源点s可以理解为最大可获得的权值（即正权点之和）。

汇点t可以理解为最大的会损失的权值（负权点之和）。

我们现在要尽量的获得s，而避免t。

想选出最大权闭合图，则如果选定一个点，这个点的所有后继子孙点都必须选择。

因此，想拿正数，就不可避免的要取负数子孙后继点。

所以：要尽量选择正权点为起点，才有可能增大闭合图点集的权值和。

因此，我们从源点s向正权点连边（即只以正权点为起点）。

至于过程中遇到的负权点，我们让其流向t，即建立边 负权点->t的意图。

好，现在我们尽量去取正数点（直接从源点s起始），过程中遇到的负权点流向t。

现在就变成了：s->t的流量就是我们的损失。

即：我们希望流向t的流量flow尽量少，而从s流出的流量sum尽量多，

从s流出而没有流入t的流量（sum-flow）就是闭合图的最大权。

 

可能有种情况很懵逼：

若要选点，选2吧，权为-5；选1和2吧，权为-1；不如选空集，权为0。明显最后的选择是对的。

 

但按照上面的思路，从s流出4，所以损失最多为4，sum-flow=0。

 

所以对该图就产生这么一种结论：

选择1号点，和不选1号点，结果是相同的，我选的时候他会被损失完，效果等同于不选。

那不妨我一开始就把所有的正权点都给选了（满足从s流出的最多），让他们往后代流，

大不了被负权子孙点损失完，而那些没有被损失完的，就是我们统计下来的结果。

那个损失，就是s->t的最大流。于是得证：闭合图最大权 = 正权和sum - 最大流flow。

 

【例题1】【p4174】最大获利

 

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            #include
             
              #include
              
               using namespace std;typedef long long ll;/*【p4174】最大获利n个中转站，第i个的建立成本为pi。M个用户：ai与bi通讯，获利ci。---> 求净获利最大。（净获利=获益之和–投入成本之和）*///【标签】网络流 + 最大权闭合子图/*【分析】注意，‘用户’和‘中转站’是两种东西，不能混淆。*/void reads(int &x){ //读入优化（正负整数） int fx=1;x=0;char ch_=getchar(); while(ch_<'0'||ch_>'9'){ if(ch_=='-')fx=-1;ch_=getchar();} while(ch_>='0'&&ch_<='9'){x=x*10+ch_-'0';ch_=getchar();} x*=fx; //正负号}const int N=1000019,inf=0x3f3f3f3f;int n,m,s,t,tot=-1,head[N],dep[N],sum=0;struct node{ int nextt,ver,w; }e[N];void add(int x,int y,int z) //正向边权值为1，反向边权值为0 { e[++tot].ver=y,e[tot].nextt=head[x],e[tot].w=z,head[x]=tot; e[++tot].ver=x,e[tot].nextt=head[y],e[tot].w=0,head[y]=tot; }int bfs(){ memset(dep,0,sizeof(dep)); //dep记录深度 queue
               
                 q; while(!q.empty()) q.pop(); dep[s]=1; q.push(s); while(!q.empty()){ int u=q.front(); q.pop(); for(int i=head[u];i!=-1;i=e[i].nextt) if((e[i].w>0)&&(dep[e[i].ver]==0)) //分层 dep[e[i].ver]=dep[u]+1,q.push(e[i].ver); } if(dep[t]!=0) return 1; else return 0; //此时不存在分层图也不存在增广路}int dfs(int u,int lastt){ int ans=0; if(u==t) return lastt; //lastt：此点还剩余的流量 for(int i=head[u];i!=-1&&ans
                
                 0){ e[i].w-=f,e[i^1].w+=f,ans+=f; } } if(ans
【p4174】最大获利 // 网络流 + 最大权闭合子图【模板题】

 

【例题2】【p3749】寿司餐厅

 

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            #include
             
              #include
              
               using namespace std;typedef long long ll;/*【p3749】寿司餐厅 *///【标签】网络流 + 最大权闭合子图 + 读题/细节处理/* 1. n<=2，种数只有 {不选}{1}{2}{1,2}{1;2} 10pts。2. 60%数据m=0，即支出=∑每个代号吃了的种类数*代号。 *//*【分析】感觉有点像网络流但我不会写0.0 最大权闭合子图。日常%GXZ https://www.cnblogs.com/GXZlegend/p/6795784.html对于每个点(i,j)(j>i)，如果它被选择，那么点(i,j-1)和点(i+1,j)也一定被选择。由此建点权图。对于点(i,j)(j>i)，点权为d[i][j]，并向点(i,j-1)和点(i+1,j)连边。对于点(i,i)，点权为d[i][i]-a[i]（收益减去费用），并向编号a[i]连边。对于编号p，点权为-m*p*p。所求为最大权闭合图，所以转化为网络流最小割来求。最后的答案 ： 闭合图最大权 = 正权和sum - 最大流flow。*/void reads(int &x){ //读入优化（正负整数） int fx=1;x=0;char ch_=getchar(); while(ch_<'0'||ch_>'9'){ if(ch_=='-')fx=-1;ch_=getchar();} while(ch_>='0'&&ch_<='9'){x=x*10+ch_-'0';ch_=getchar();} x*=fx; //正负号}const int N=50019,inf=0x3f3f3f3f;int a[N],d[110][110],id[110][110],cnt_;int s,t,tot=-1,n1,n2,n3,head[N],dep[N]; //s为源点，t为汇点 struct node{ int nextt,ver,w; }e[N];void add(int x,int y,int z) //正向边权值为1，反向边权值为0 { e[++tot].ver=y,e[tot].nextt=head[x],e[tot].w=z,head[x]=tot; e[++tot].ver=x,e[tot].nextt=head[y],e[tot].w=0,head[y]=tot; }int bfs(){ memset(dep,0,sizeof(dep)); //dep记录深度 queue
               
                 q; while(!q.empty()) q.pop(); dep[s]=1; q.push(s); while(!q.empty()){ int u=q.front(); q.pop(); for(int i=head[u];i!=-1;i=e[i].nextt) if((e[i].w>0)&&(dep[e[i].ver]==0)) //分层 dep[e[i].ver]=dep[u]+1,q.push(e[i].ver); } if(dep[t]!=0) return 1; else return 0; //此时不存在分层图也不存在增广路}int dfs(int u,int lastt){ int ans=0; if(u==t) return lastt; //lastt：此点还剩余的流量 for(int i=head[u];i!=-1&&ans
                
                 0){ e[i].w-=f,e[i^1].w+=f,ans+=f; } } if(ans
                 
                  0) add(s,id[i][j],d[i][j]),sum+=d[i][j]; //正权 if(d[i][j]<0) add(id[i][j],t,-d[i][j]); //负权，向T建立全值为绝对值的边 if(j>i) add(id[i][j],id[i][j-1],inf),add(id[i][j],id[i+1][j],inf); } //↑↑处理相关联有影响的性质：(i,j) -> (i,j-1)、(i+1,j) while(bfs()) sum-=dfs(s,inf); printf("%d\n",sum);}
【p3749】寿司餐厅 // 网络流 + 最大权闭合子图 + 读题/细节处理

 

【例题3】【p2762】太空飞行问题

 

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            #include
             
              #include
              
               using namespace std;typedef long long ll;//【p2762】太空飞行问题 // 网络流 + 最大权闭合子图 + 读入方式/*【分析】S - m个实验 - n个仪器 - T */const int N=1000019,inf=0x3f3f3f3f;int n,m,s,t,tot=-1,head[N],dep[N],sum=0,flag=0;int reads(int &x){ //读入优化（正负整数） int fx=1;x=0;char ch_=getchar(); while(ch_<'0'||ch_>'9'){ if(ch_=='-')fx=-1;ch_=getchar();} while(ch_>='0'&&ch_<='9'){x=x*10+ch_-'0';ch_=getchar();} x*=fx; return ch_=='\r'||ch_=='\n'?0:1; //十分厉害的读入...}struct node{ int nextt,ver,w; }e[N];void add(int x,int y,int z) //正向边权值为1，反向边权值为0 { e[++tot].ver=y,e[tot].nextt=head[x],e[tot].w=z,head[x]=tot; e[++tot].ver=x,e[tot].nextt=head[y],e[tot].w=0,head[y]=tot; }int bfs(){ memset(dep,0,sizeof(dep)); //dep记录深度 queue
               
                 q; while(!q.empty()) q.pop(); dep[s]=1; q.push(s); while(!q.empty()){ int u=q.front(); q.pop(); for(int i=head[u];i!=-1;i=e[i].nextt) if((e[i].w>0)&&(dep[e[i].ver]==0)) //分层 dep[e[i].ver]=dep[u]+1,q.push(e[i].ver); } if(dep[t]!=0) return 1; else return 0; //此时不存在分层图也不存在增广路}int dfs(int u,int lastt){ int ans=0; if(u==t) return lastt; //lastt：此点还剩余的流量 for(int i=head[u];i!=-1&&ans
                
                 0){ e[i].w-=f,e[i^1].w+=f,ans+=f; } } if(ans
                 
                  0) cout<
                  <<" "; printf("\n"); for(int i=1;i<=n;i++) if(dep[i+m]>0) cout<<<" "; printf("\n"); printf("%d\n",ans); //最大权闭合子图的最大权}
【p2762】太空飞行问题 // 网络流 + 最大权闭合子图 + 读入方式 + 输出方案

 

【例题4】【poj2987】Fireing

 

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            #include
             
              #include
              
               using namespace std;typedef long long ll;//【poj2987】Firing // 网络流 + 最大权闭合子图/* 炒掉一个人能够获得b收益（b可以<0），但必须炒掉他的下属。求最大收益和此时最小裁员。 *///【分析】把u是v的上司变成u—>v，运行最大权闭合子图const ll N=1000019,inf=0x3f3f3f3f;ll n,m,s,t,tot=-1,head[N],dep[N]; ll sum=0;void reads(ll &x){ //读入优化（正负整数） ll fx=1;x=0;char ch_=getchar(); while(ch_<'0'||ch_>'9'){ if(ch_=='-')fx=-1;ch_=getchar();} while(ch_>='0'&&ch_<='9'){x=x*10+ch_-'0';ch_=getchar();} x*=fx; //正负号}struct node{ ll nextt,ver,w; }e[N];void add(ll x,ll y,ll z) //正向边权值为1，反向边权值为0 { e[++tot].ver=y,e[tot].nextt=head[x],e[tot].w=z,head[x]=tot; e[++tot].ver=x,e[tot].nextt=head[y],e[tot].w=0,head[y]=tot; }ll bfs(){ memset(dep,0,sizeof(dep)); //dep记录深度 queue
               
                 q; while(!q.empty()) q.pop(); dep[s]=1; q.push(s); while(!q.empty()){ ll u=q.front(); q.pop(); for(ll i=head[u];i!=-1;i=e[i].nextt) if((e[i].w>0)&&(dep[e[i].ver]==0)) //分层 dep[e[i].ver]=dep[u]+1,q.push(e[i].ver); } if(dep[t]!=0) return 1; else return 0; //此时不存在分层图也不存在增广路}ll dfs(ll u,ll lastt){ ll ans=0; if(u==t) return lastt; //lastt：此点还剩余的流量 for(ll i=head[u];i!=-1&&ans
                
                 0){ e[i].w-=f,e[i^1].w+=f,ans+=f; } } if(ans
                 
                  0 for(ll i=head[u];i!=-1;i=e[i].nextt) { ll v=e[i].ver; if(e[i].w>0&&!vis[v]) ans+=get_(v); } return ans; }int main(){ reads(n),reads(m); s=0,t=n+1; memset(head,-1,sizeof(head)); for(ll i=1,bi;i<=n;i++){ reads(bi); if(bi>0) sum+=bi,add(s,i,bi); else add(i,t,-bi); } for(ll i=1,a,b;i<=m;i++) reads(a),reads(b),add(a,b,inf); //限制关系 ll ans=sum-dinic(); //最大权闭合子图的最大权 printf("%lld %lld\n",get_(s)-1,ans); //最大权闭合子图的最大权}
【poj2987】Firing // 网络流 + 最大权闭合子图 + 不开ll见祖宗 
#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            #include
             
              #include
              
               using namespace std;typedef long long ll;//【poj2987】Firing // 网络流 + 最大权闭合子图/* 炒掉一个人能够获得b收益（b可以<0），但必须炒掉他的下属。求最大收益和此时最小裁员。 *///【分析】把u是v的上司变成u—>v，运行最大权闭合子图const ll N=1000019,inf=0x3f3f3f3f;ll n,m,s,t,tot=-1,head[N],dep[N]; ll sum=0;void reads(ll &x){ //读入优化（正负整数） ll fx=1;x=0;char ch_=getchar(); while(ch_<'0'||ch_>'9'){ if(ch_=='-')fx=-1;ch_=getchar();} while(ch_>='0'&&ch_<='9'){x=x*10+ch_-'0';ch_=getchar();} x*=fx; //正负号}struct node{ ll nextt,ver,w; }e[N];void add(ll x,ll y,ll z) //正向边权值为1，反向边权值为0 { e[++tot].ver=y,e[tot].nextt=head[x],e[tot].w=z,head[x]=tot; e[++tot].ver=x,e[tot].nextt=head[y],e[tot].w=0,head[y]=tot; }ll bfs(){ memset(dep,0,sizeof(dep)); //dep记录深度 queue
               
                 q; while(!q.empty()) q.pop(); dep[s]=1; q.push(s); while(!q.empty()){ ll u=q.front(); q.pop(); for(ll i=head[u];i!=-1;i=e[i].nextt) if((e[i].w>0)&&(dep[e[i].ver]==0)) //分层 dep[e[i].ver]=dep[u]+1,q.push(e[i].ver); } if(dep[t]!=0) return 1; else return 0; //此时不存在分层图也不存在增广路}ll dfs(ll u,ll lastt){ ll ans=0; if(u==t) return lastt; //lastt：此点还剩余的流量 for(ll i=head[u];i!=-1&&ans
                
                 0){ e[i].w-=f,e[i^1].w+=f,ans+=f; } } if(ans
                 
                  0) sum+=bi,add(s,i,bi); else add(i,t,-bi); } for(ll i=1,a,b;i<=m;i++) reads(a),reads(b),add(a,b,inf); //限制关系 ll ans=sum-dinic(),ans_=0; //最大权闭合子图的最大权 for(ll i=1;i<=n;i++) if(dep[i]>0) ans_++; printf("%lld %lld\n",ans_,ans); //最大权闭合子图的最大权}
【poj2987】Firing // 网络流 + 最大权闭合子图 + 第二种找路径的方法 time--

 

 【例题5】【p2805】植物大战僵尸

 

#include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            #include
             
              #include
              
               using namespace std;typedef long long ll;//【p2805】植物大战僵尸 // 网络流 + 最大权闭合子图 + 拓扑排序// 注意：如果某些植物保护关系成了环，那它们都不能吃掉。需要用拓扑排序判环。const int N=1019,inf=0x3f3f3f3f;int n,m,s,t,tot=-1,head[N],dep[N],sum=0,g[N][N],w[N],rd[N],vis_[N];int reads(int &x){ //读入优化（正负整数） int fx=1;x=0;char ch_=getchar(); while(ch_<'0'||ch_>'9'){ if(ch_=='-')fx=-1;ch_=getchar();} while(ch_>='0'&&ch_<='9'){x=x*10+ch_-'0';ch_=getchar();} x*=fx; return ch_=='\r'||ch_=='\n'?0:1;}struct node{ int nextt,ver,w; }e[N*N];void add(int x,int y,int z) //正向边权值为1，反向边权值为0 { e[++tot].ver=y,e[tot].nextt=head[x],e[tot].w=z,head[x]=tot; e[++tot].ver=x,e[tot].nextt=head[y],e[tot].w=0,head[y]=tot; }int bfs(){ memset(dep,0,sizeof(dep)); //dep记录深度 queue
               
                 q; while(!q.empty()) q.pop(); dep[s]=1; q.push(s); while(!q.empty()){ int u=q.front(); q.pop(); for(int i=head[u];i!=-1;i=e[i].nextt) if((e[i].w>0)&&(dep[e[i].ver]==0)) //分层 dep[e[i].ver]=dep[u]+1,q.push(e[i].ver); } if(dep[t]!=0) return 1; else return 0; //此时不存在分层图也不存在增广路}int dfs(int u,int lastt){ int ans=0; if(u==t) return lastt; //lastt：此点还剩余的流量 for(int i=head[u];i!=-1&&ans
                
                 0){ e[i].w-=f,e[i^1].w+=f,ans+=f; } } if(ans
q; for(int i=1;i<=n*m;i++) //统计入度 for(int j=1;j<=n*m;j++) if(g[i][j]) rd[j]++; for(int i=1;i<=n*m;i++) if(!rd[i]) q.push(i); while(!q.empty()){ int x=q.front(); q.pop(),vis_[x]=1; for(int y=1;y<=n*m;y++) if(g[x][y]) { rd[y]--; if(!rd[y]) q.push(y); } }}void dfs(int x){ for(int i=1;i<=n*m;i++) if(g[x][i]&&vis_[i]) vis_[i]=0,dfs(i); }int main(){ reads(n),reads(m); s=0,t=n*m+1; memset(head,-1,sizeof(head)); for(int i=1,k,x,y;i<=n;i++) for(int j=1;j<=m;j++){ reads(w[(i-1)*m+j]),reads(k); if(j>1) g[(i-1)*m+j][(i-1)*m+j-1]=1; while(k--) reads(x),reads(y),g[(i-1)*m+j][x*m+y+1]=1; } topo(); for(int i=1;i<=n*m;i++) if(!vis_[i]) dfs(i); //拓扑排序判环，并把环上所有元素重新标记为vis_[i]==0 //方法：环上的各点入度都为1，不为0，拓扑排序后肯定还有点没进队列 for(int i=1;i<=n*m;i++) if(vis_[i]){ if(w[i]>=0) add(s,i,w[i]),sum+=w[i]; else add(i,t,-w[i]); for(int j=1;j<=n*m;j++) if(g[j][i]&&vis_[j]) add(i,j,inf); } cout<
<
【p2805】植物大战僵尸 // 网络流 + 最大权闭合子图 + 拓扑排序

 

 

    相关资料补充：

 

 

                                                       ——时间划过风的轨迹，那个少年，还在等你。

 

转载于:https://www.cnblogs.com/FloraLOVERyuuji/p/10400914.html

你可能感兴趣的文章
《Genesis-3D开源游戏引擎完整实例教程-跑酷游戏篇03：暂停游戏》
查看>>
CPU，寄存器，一缓二缓.... RAM ROM 外部存储器等简介
查看>>
windows下编译FreeSwitch
查看>>
git .gitignore 文件不起作用
查看>>
Alan Turing的纪录片观后感
查看>>
c#自定义控件中的事件处理
查看>>
django Models 常用的字段和参数
查看>>
IOS--沙盒机制
查看>>
使用 JointCode.Shuttle 访问任意 AppDomain 的服务
查看>>
sqlite的坑
查看>>
digitalocean --- How To Install Apache Tomcat 8 on Ubuntu 16.04
查看>>
【题解】[P4178 Tree]
查看>>
Jquery ui widget开发
查看>>
关于indexOf的使用
查看>>
英语单词
查看>>
Mongo自动备份
查看>>
cer证书签名验证
查看>>
新手Python第一天(接触)
查看>>
【bzoj1029】[JSOI2007]建筑抢修
查看>>
synchronized
查看>>
喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！-- 愿君每日到此一游！
当前时间: 2024-11-16 02:41:10   当前IP: 3.138.102.202   联系邮箱:javaeecc@qq.com     Copyright © 2020 - 2022 baihongyu.com 京ICP备2021015314号-2
强烈建议你试试无所不能的CHAT-GPT，快点击我
强烈建议你试试无所不能的CHAT-GPT，快点击我