当前位置: 首页 > news >正文

[hihocoder1395] 最大权闭合子图

题意:

原题链接

题解:

建图:源点向所有正权点连正权权值的边,负权点向汇点连负权的绝对值的边,正权点与负权点之间的边为inf

最大权闭合子图=正权和-最小割

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#define ll long long
#define M 100010
#define N 100010
using namespace std;

int n,m,t,inf=1<<30,sum,e_num=-1;
int nxt[M],to[M],w[M],h[N],lev[N],cur[N];
//边数大约为:2*(n^2),点数约为2*n

int gi() {
  int x=0,o=1; char ch=getchar();
  while(ch!='-' && (ch<'0' || ch>'9')) ch=getchar();
  if(ch=='-') o=-1,ch=getchar();
  while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
  return o*x;
}

void add(int x, int y, int z) {
  nxt[++e_num]=h[x],to[e_num]=y,w[e_num]=z,h[x]=e_num;
}

bool bfs() {
  queue<int> q;
  memset(lev,0,sizeof(lev));
  q.push(0),lev[0]=1;
  while(!q.empty()) {
    int u=q.front(); q.pop();
    for(int i=h[u]; i!=-1; i=nxt[i]) {
      int v=to[i];
      if(!lev[v] && w[i]) {
    lev[v]=lev[u]+1;
    q.push(v);
    if(v==t) return true;
      }
    }
  }
  return false;
}

int dfs(int u, int f) {
  if(u==t) return f;
  int tag=0,c;
  for(int &i=cur[u]; i!=-1; i=nxt[i]) {
    int v=to[i];
    if(lev[v]==lev[u]+1 && w[i]) {
      c=dfs(v,min(f-tag,w[i])); 
      w[i]-=c,w[i^1]+=c,tag+=c;
      if(tag==f) return tag;
    }
  }
  return tag;
}

int dinic() {
  int ret=0;
  while(bfs()) {
    for(int i=0; i<=t; i++) cur[i]=h[i];
    ret+=dfs(0,inf);
  }
  return ret;
}

int main() {
  memset(h,-1,sizeof(h));
  n=gi(),m=gi(),t=n+m+1;
  for(int i=1; i<=m; i++) {
    int v=gi();
    add(i+n,t,v),add(t,i+n,0);
  }
  for(int i=1; i<=n; i++) {
    int v=gi(),k=gi(),x;
    add(0,i,v),add(i,0,0);
    while(k--) x=gi(),add(i,x+n,inf),add(x+n,i,0);
    sum+=v;
  }
  printf("%d\n", sum-dinic());
  return 0;
}

转载于:https://www.cnblogs.com/HLXZZ/p/7655093.html

相关文章:

  • CodeDom系列目录
  • 转: Lua 语言 15 分钟快速入门
  • JavaScript多线程之HTML5 Web Worker
  • Qt学习: QPixmap实现的截屏程序代码示例
  • HDFS上创建文件、写入内容
  • 管理OCR与Voting Disk(原创)
  • Open-E DSS V7 应用系列之十 主动/主动 iSCSI群集部署(二)
  • ThinkSNS特有需求之--英文字符占 0.5 个,中文字符占 1 个
  • Java 加密解密基础
  • HTML5边玩边学(9):俄罗斯方块就是这么简单 之 数据模型篇
  • PAT (Advanced Level) 1045. Favorite Color Stripe (30)
  • Web安全实践(15)CSRF(跨站请求伪造)-从校内的插入图片说起
  • CCAction
  • Wireshark漫谈(一)
  • 手写数字识别的几种实现方法
  • 【跃迁之路】【699天】程序员高效学习方法论探索系列(实验阶段456-2019.1.19)...
  • CSS居中完全指南——构建CSS居中决策树
  • HTML中设置input等文本框为不可操作
  • mysql 数据库四种事务隔离级别
  • mysql常用命令汇总
  • oldjun 检测网站的经验
  • Rancher-k8s加速安装文档
  • 大数据与云计算学习:数据分析(二)
  • 对超线程几个不同角度的解释
  • 高度不固定时垂直居中
  • 关于for循环的简单归纳
  • 好的网址,关于.net 4.0 ,vs 2010
  • 前嗅ForeSpider教程:创建模板
  • 三栏布局总结
  • 使用Maven插件构建SpringBoot项目,生成Docker镜像push到DockerHub上
  • 微信开源mars源码分析1—上层samples分析
  • 学习ES6 变量的解构赋值
  • FaaS 的简单实践
  • Spring第一个helloWorld
  • 函数计算新功能-----支持C#函数
  • ​无人机石油管道巡检方案新亮点:灵活准确又高效
  • ​云纳万物 · 数皆有言|2021 七牛云战略发布会启幕,邀您赴约
  • $NOIp2018$劝退记
  • (9)目标检测_SSD的原理
  • (二)斐波那契Fabonacci函数
  • (机器学习-深度学习快速入门)第一章第一节:Python环境和数据分析
  • (论文阅读30/100)Convolutional Pose Machines
  • (三)模仿学习-Action数据的模仿
  • (十三)Maven插件解析运行机制
  • (一)C语言之入门:使用Visual Studio Community 2022运行hello world
  • (原創) 如何安裝Linux版本的Quartus II? (SOC) (Quartus II) (Linux) (RedHat) (VirtualBox)
  • .apk文件,IIS不支持下载解决
  • .cfg\.dat\.mak(持续补充)
  • .net core 依赖注入的基本用发
  • .Net CoreRabbitMQ消息存储可靠机制
  • .NET 的程序集加载上下文
  • .NET 简介:跨平台、开源、高性能的开发平台
  • .NET连接数据库方式
  • @ConfigurationProperties注解对数据的自动封装
  • @JsonSerialize注解的使用