poj 2987 最大权闭合图-程序员宅基地

由上一篇可得

最大权闭合图的权值为sum-max_flow

sum为正的权值和,max_flow为重新建图后的最大流

求最大流后,在残留网络中从s出发dfs能搜到点都为最大权闭合图中的点,即这个最小割对应的是最大权闭合图

View Code
#include<stdio.h>
#include<string.h>
const int MAX=100005;
const int INF=1000000000;

struct
{
int v,c,next;
}edge[1000000];
int E,head[MAX];
int gap[MAX],cur[MAX];
int pre[MAX],dis[MAX];
void add_edge(int s,int t,int c,int cc)
{
/*加边的时候同时加两条,
一条正的,一条反的,
一般情况下反的容量是0
*/
edge[E].v=t; edge[E].c=c;
edge[E].next=head[s];
head[s]=E++;
edge[E].v=s; edge[E].c=cc;
edge[E].next=head[t];
head[t]=E++;
}
int min(int a,int b){ return (a==-1||b<a)?b:a;}
__int64 SAP(int s,int t,int n)
{
memset(gap,0,sizeof(gap));
memset(dis,0,sizeof(dis));
int i;
for(i=0;i<n;i++)cur[i]=head[i];
int u=pre[s]=s,aug=-1,v;
__int64 maxflow=0;
gap[0]=n;
while(dis[s]<n)
{
loop: for(i=cur[u];i!=-1;i=edge[i].next)
{
v=edge[i].v;
if(edge[i].c>0&&dis[u]==dis[v]+1)
{
aug=min(aug,edge[i].c);
pre[v]=u;
cur[u]=i;
u=v;
if(u==t)
{
for(u=pre[u];v!=s;v=u,u=pre[u])
{
edge[cur[u]].c-=aug;
edge[cur[u]^1].c+=aug;
}
maxflow+=aug;
aug=-1;
}
goto loop;
}
}
int mindis=n;
for(i=head[u];i!=-1;i=edge[i].next)
{
v=edge[i].v;
if(edge[i].c>0&&dis[v]<mindis)
{
cur[u]=i;
mindis=dis[v];
}
}
if((--gap[dis[u]])==0)break;
gap[dis[u]=mindis+1]++;
u=pre[u];
}
return maxflow;
}
bool vis[MAX];
void dfs(int u,int t)
{
if(u==t) return ;
vis[u]=true;
for(int i=head[u];i!=-1;i=edge[i].next)
if(edge[i].c>0 && !vis[edge[i].v])
dfs(edge[i].v,t);
}
int main()
{
int i,n,m,j,w,a,b;
scanf("%d%d",&n,&m);
__int64 sum=0;
int s=0,t=n+1;
memset(head,-1,sizeof(head)); E=0;
for(i=1;i<=n;i++)
{
scanf("%d",&w);
if(w>0)
{sum+=w;
add_edge(s,i,w,0);
}
else add_edge(i,t,-w,0);
}
while(m--)
{
scanf("%d%d",&a,&b);
add_edge(a,b,INF,0);
}
__int64 mxflow=SAP(s,t,n+2);
memset(vis,0,sizeof(vis));
dfs(s,t);int ans=0;
for(i=1;i<=n;i++)
{
if(vis[i])
ans++;
}
printf("%d %I64d\n",ans,sum-mxflow);
return 0;
}



版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/haha593572013/article/details/10082629

智能推荐

在linux中使用setns()设置pid namespace-程序员宅基地

文章浏览阅读3.1k次。以下代码展示了 setns() 的用法,#define _GNU_SOURCE#include <fcntl.h>#include <sched.h>#include <unistd.h>#include <stdlib.h>#include <stdio.h>#include <string.h>#include <sys/types.h>#include <sys/wait.h>#in_setns

可逆矩阵性质总结_线性代数下的行列式和矩阵-程序员宅基地

文章浏览阅读5.7k次。实际意义求线性方程组线性方程组一般有 m 个常数项,n 个未知数,m * n 个系数。若常数项全为 0 ,则为齐次线性方程组;若未知数全为 0 ,则称为零解。于是我们考虑的问题是:齐次方程组:是否存在非零解,以及存在的条件通解的结构与性质解法非齐次方程组:是否有解,以及有解的条件是什么有多少解以及对应解数量的条件是什么多解的结构与性质解法行列式二,三阶行列式行列式最初的作用就是求解线性方程组!例如..._可逆矩阵一定是实数矩阵吗

centos8的80端口不通问题记录_为什么keepalived连不上本地的80端口-程序员宅基地

文章浏览阅读5.2k次。1、首先是安装了nginx并启动了服务,查看80端口正常listening2、通过其他机器访问网页无法连接,查看telnet到80端口也不通。初步怀疑跟防火墙有关3、查看iptables,发现有部分默认规则,但都是accept。默认的filter表也都是accept,尝试用iptables -F清空规则表后问题依旧4、之前使用的是ubuntu系统,主要通过的就是iptables来控制..._为什么keepalived连不上本地的80端口

Mysql5.7安装 Gtid原理作用+主从复制_gtid在主从复制的作用-程序员宅基地

文章浏览阅读1.3k次,点赞4次,收藏3次。Gtid的作用Gtid,采用了新的复制协议,旧协议是,首先从服务器上在一个特定的偏移量位置连接到主服务器上一个给定的二进制日志文件,然后主服务器再从给定的连接点开始发送所有的事件。新协议有所不同,支持以全局统一事务ID(GTID)为基础的复制。当在主库上提交事务或者被从库应用时,可以定位和追踪每一个事务。GTID复制是全部以事务为基础,使得检查主从一致性变得非常简单。如果所有主库上提交的事务也同样提交到从库上,一致性就得到了保证。Gtid的工作原理1.当一个事务在主库端执行并提交时,产生GTID,一_gtid在主从复制的作用

Java 单例模式浅析_单例模式论文-程序员宅基地

文章浏览阅读229次。提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档文章目录前言一、pandas是什么?二、使用步骤1.引入库2.读入数据总结前言提示:这里可以添加本文要记录的大概内容:例如:随着人工智能的不断发展,机器学习这门技术也越来越重要,很多人都开启了学习机器学习,本文就介绍了机器学习的基础内容。提示:以下是本篇文章正文内容,下面案例可供参考一、pandas是什么?示例:pandas 是基于NumPy 的一种工具,该工具是为了解决数据分析任务而创建的。二、使用步骤1.引入库代码_单例模式论文

python 解决动态的定义变量名,并给其赋值的方法(大数据处理)_pytorch 动态生成变量名以及动态获取变量的变量名方法-程序员宅基地

文章浏览阅读3.2k次。今天小编就为大家分享一篇python 解决动态的定义变量名,并给其赋值的方法(大数据处理),具有很好的参考价值,希望对大家有所帮助。一起跟随小编过来看看吧最近消费kafka数据到磁盘的时候遇到了这样的问题:需求:每天大概有1千万条数据,每条数据包含19个字段信息,需要将数据写到服务器磁盘,以第二个字段作为大类建立目录,第7个字段作为小类配合时间戳作为文件名,临时文件后缀tmp,当每个文件的写入..._pytorch 动态生成变量名以及动态获取变量的变量名方法

随便推点

安装caffe过程中出现libtbb.so.2 undefined reference error_//usr/lib/x86_64-linux-gnu/libtbb.so.2:对‘__cxa_ini-程序员宅基地

文章浏览阅读768次。caffe 包是从caffe的github官网上下载的https://github.com/BVLC/caffe我是准备安装openpose的,之后按照网上的流程来,可是不管怎么安装依赖项以及修改make.config都卡在最后了[ 4%] Building CXX object src/caffe/CMakeFiles/caffe.dir/util/blocking_queue.cpp.o[ 5%] Linking CXX shared library ../../lib/lib_//usr/lib/x86_64-linux-gnu/libtbb.so.2:对‘__cxa_init_primary_exception@cxxa

会议室电脑怎么无线投屏_会议室无线投屏-程序员宅基地

文章浏览阅读1k次。会议室电脑怎么无线投屏?尤其是远程会议电脑如何无线投屏,可能觉得市场上多如牛毛的投屏器就可以解决这个问题。事实上,投屏器真的可以做到无线投屏电脑吗?一些企业需要召开远程会议,这样可以节省会议成本。演示的会议内容需要多地同屏,比如政府部门,银行等分支机构较多的单位,投屏器是否有这么庞大的数据传输能力;应用开发团队,需要轮流切换不同的电脑和连接设备,接口和分辨率等兼容问题,要反复调试严重影响会议进度;做产品设计演示时让团队成员可以更直观地看到设计稿。这些小问题是企业协同办公中不可忽视的痛点,部署连通宝多屏互_会议室无线投屏

JavaScript绑定this-程序员宅基地

文章浏览阅读42次。问题描述var a = { one: 1, haha() { console.log(this.one) }}setTimeout(a.haha, 1000)在上例中,函数haha引用了this.one,而定时器结束之后调用的haha传入的this并不是a,输出结果this.one是未定义变量。方法一:使用箭头函数的方式设置回调var ...

Spark 配置历史服务器_spark.history.ui.port-程序员宅基地

文章浏览阅读1k次。类似Hadoop,Spark也有自己的history server,这里我们就来配置下:修改 spark-defaults.conf.template 文件名为 spark-defaults.confmv spark-defaults.conf.template spark-defaults.conf修改 spark-default.conf 文件,配置日志存储路径spark.eventLog.enabled truespark.eventLog.dir _spark.history.ui.port

五大UNIX系统家族族谱_unix 族谱-程序员宅基地

文章浏览阅读2.1k次。UNIX操作系统不是某个特定操作系统实现,而是在遵循UNIX相关标准下的一个操作系统大家族,主要代表有SVR4、FreeBSD、Linux、Macc OS X、Solaris五大UNIX操作系统族谱家族名称维护者主要版本说明SVRUSLSVR3.2、SVR4 BSDCSRG4.2BSD(1983)、4._unix 族谱

计算机实验excel总结,EXCEL实验报告-程序员宅基地

文章浏览阅读1.7k次。《EXCEL实验报告》由会员分享,可在线阅读,更多相关《EXCEL实验报告(2页珍藏版)》请在人人文库网上搜索。1、实验报告班 级姓 名学 号日 期实验项目使用Excel进行会计各报表的核算及编制实验设备、用品机房计算机 Excel应用软件实验报告(实验目的与要求、实验基本过程、实验经验总结):实验目的与要求:通过学校可以使我熟练掌握使用excel中 一、实验目的:通过本次课程,使我们熟练掌握在计..._excel实验报告