(最大权闭合子图)poweroj2909: 黑暗料理

news/2024/2/27 21:10:42

poweroj2909: 黑暗料理

思路:

我们要选择做一道菜,就要选择其原材料。这可以转换为最大权闭合子图的问题。
什么是闭合子图?闭合子图在有向无环图中,对于其中任意点,从它出发能够达到的所有点都在用一个子图之中。
为什么这么转换?因为我们要选择一道菜,它的食材也必须选择,如果我们把菜连向它需要的所有的食材,那么就可以得到,选一道菜的同时,它所需的食材的点也必须在这个子图之中。
求法就是,对于通过源点 S S S向所有点权为正的点建边,权值为点权;权值为负的点向汇点 T T T建边,权值为点权的绝对值;按照题目需要的关系建边,权值为 i n f inf inf。然后答案就是:最大权值=正权点值和-最小割

代码:

#include<bits/stdc++.h>
#define pii pair<int,int>
#define int long long
#define cl(x,y) memset(x,y,sizeof(x))
#define ct cerr<<"Time elapsed:"<<1.0*clock()/CLOCKS_PER_SEC<<"s.\n";
const int N=3e6+210;
const int M=1e5+10; 
const int mod=1e9+7;
const int inf=0x3f3f3f3f;
const int minn=0xc0c0c0c0;
using namespace std;
struct edge
{int u,v,w;
}maze[N<<1];
int len=1,head[M]={0};
int dep[M];//深度 
void add(int u,int v,int w)
{maze[++len]={head[u],v,w};head[u]=len;
}
void inc(int u,int v,int w)
{add(u,v,w);add(v,u,0);
} 
int dfs(int u,int f,int t)
{int ans=0,i;if(u==t)return f;for(i=head[u];i && f;i=maze[i].u){int v=maze[i].v,w=maze[i].w;if(dep[v]==dep[u]+1 && w)//符合深度关系且能流 {int sum=dfs(v,min(f,w),t);maze[i].w-=sum;maze[i^1].w+=sum;f-=sum;ans+=sum;}	}if(!ans)dep[u]=-2;return ans;
}
int bfs(int s,int t)
{queue<int> q;cl(dep,0);dep[s]=1;//源点深度为1q.push(s);while(!q.empty()){int u=q.front(),i;q.pop();for(i=head[u];i;i=maze[i].u){int v=maze[i].v,w=maze[i].w;if(w && !dep[v])//有深度且能流 {dep[v]=dep[u]+1;q.push(v); }}}return dep[t];
}
int dinic(int s,int t)
{int ans=0;while(bfs(s,t))ans+=dfs(s,inf,t);return ans;
}
signed main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);int n,m,i;cin>>n>>m;int s=0,t=n+m+1,sum=0;for(i=1;i<=n;i++){int w,k;cin>>w>>k;sum+=w;inc(s,i,w);while(k--){int v;cin>>v;inc(i,v+n,inf);}}for(i=1;i<=m;i++){int w;cin>>w;inc(i+n,t,w);}cout<<sum-dinic(s,t)<<endl;return 0;
}

http://www.ppmy.cn/news/935897.html

相关文章

力扣杯春赛 ,宝石补给、烹饪料理Easy

写在前面&#xff0c;本文是博主打春赛的记录&#xff0c;另外&#xff0c;博主是“菜鸡” 比赛来晚了&#xff0c;打开电脑&#xff0c;进入竞赛界面&#xff0c;ohhhhhhhhhhhh&#xff0c;有点高端&#xff0c;还有动态榜&#xff0c;有点ICPC和ACM的味道了&#xff0c;总体…

料理材料

题目描述 牛牛想尝试一些新的料理&#xff0c;每个料理需要一些不同的材料&#xff0c;问完成所有的料理需要准备多少种不同的材料。 输入描述: 每个输入包含 1 个测试用例。每个测试用例的第 i 行&#xff0c;表示完成第 i 件料理需要哪些材料&#xff0c;各个材料用空格隔…

练习(牛牛吃料理)

import java.util.HashSet; import java.util.Scanner; //输出一行一个数字表示完成所有料理需要多少种不同的材料。 public class Main_141 {public static void main(String[] args) {Scanner scanner new Scanner(System.in);HashSet<String> hashSet new HashSet&l…

爱美食android源代码,爱料理app下载

爱料理app一款美食类app&#xff0c;喜欢吃美食&#xff0c;喜欢做美食的朋友不要错过&#xff0c;集合全台湾30000多款独特料理&#xff0c;马上变身美食达人&#xff0c;内容详尽&#xff0c;爱做菜的你赶紧get起来吧&#xff01; 软件介绍&#xff1a; 在爱料理App这里您可以…

LeetCode LCP 51. 烹饪料理(状态枚举)

文章目录 1. 题目2. 解题 1. 题目 欢迎各位勇者来到力扣城&#xff0c;城内设有烹饪锅供勇者制作料理&#xff0c;为自己恢复状态。 勇者背包内共有编号为 0 ~ 4 的五种食材&#xff0c;其中 meterials[j] 表示第 j 种食材的数量。 通过这些食材可以制作若干料理&#xff0c;…

料理鼠鼠——团队展示

这个作业属于哪个课程<软件工程>这个作业要求在哪里<作业要求>这个作业的目标<组建团队&#xff0c;确定项目&#xff0c;确定绩效考核方案&#xff0c;撰写博客>其他参考文献《构建之法》 文章目录 响亮的队名料理鼠鼠 队员风采222000218龙林222000210黄荣强…

图片对象转换工具

该工具用于保存图片到其他介质的方法 /// <summary>/// 图片对象转换工具/// </summary>public sealed class ImageConvert{/// <summary>/// byte数组转换为Image/// </summary>/// <param name"inputBytes">传入byte数组参数</pa…

图片缩放转换类

在处理图片显示的时候&#xff0c;我们经常会用到图片的缩放功能。 /// <summary>/// 图片大小规格变换工具/// </summary>public sealed class ZoomPicture{/// <summary>/// 缩放图片/// </summary>/// <param name"srcPicPath">来源…

LCP 51. 烹饪料理(回溯)

【问题描述】&#xff1a; 欢迎各位勇者来到力扣城&#xff0c;城内设有烹饪锅供勇者制作料理&#xff0c;为自己恢复状态。 勇者背包内共有编号为 0 ~ 4 的五种食材&#xff0c;其中 materials[j] 表示第 j 种食材的数量。通过这些食材可以制作若干料理&#xff0c;cookbook…

LeetCodeCup 2. 烹饪料理

思路&#xff1a; 用状态压缩举出每一种状态&#xff0c;在判断是否可以满足大于limit的目标&#xff0c;满足则记录当前选取的cookbooks 的ans。 eg &#xff1a;共三本书。选取第一本第二本 &#xff1a;i 3 。 二进制表示则为 0 1 1 小菜鸡一个&#xff0c;做了两个来小时…

android 打开图片选择文件格式,FilePicker: :fire::fire::fire:Android文件、图片选择器,可按文件夹查找,文件类型查找,支持自定义相机...

介绍 可在文件浏览器中选择指定后缀名文件 可通过扫描全盘的方式&#xff0c;选择指定后缀名的文件 类似微信图片选择器选择图片或视频 图片选择页面可以自定义主题 支持Activity、Fragment Example 可下载APK直接体验 用法 implementation cn.imlibo:FilePicker:v0.0.5_alpha …

leetcode 烹饪料理

欢迎各位勇者来到力扣城&#xff0c;城内设有烹饪锅供勇者制作料理&#xff0c;为自己恢复状态。 勇者背包内共有编号为 0 ~ 4 的五种食材&#xff0c;其中 materials[j] 表示第 j 种食材的数量。通过这些食材可以制作若干料理&#xff0c;cookbooks[i][j] 表示制作第 i 种料理…

宝可梦探险寻宝料理php,宝可梦探险寻宝料理怎样搭配_宝可梦探险寻宝料理配方搭配方式详解_玩游戏网...

《宝可梦大探险》寻宝一周目攻略 在宝可梦大探险手游中寻宝一周目究竟该怎么过呢&#xff1f;在宝可梦大探险手游中寻宝一共有十大关卡&#xff0c;小伙伴们能在一周目里全部收集齐吗&#xff1f;下面就来给大家介绍一下吧&#xff01;宝可梦探险寻宝一周目通关攻略首先说一下&…

食物图片变菜谱:这篇CVPR论文让人人都可以学习新料理

根据 Facebook 的统计&#xff0c;Instgram 上的美食图片数量已经超过 3 亿张。然而&#xff0c;获取食物烹饪方法的途径依然有限&#xff0c;例如&#xff0c;通过烹饪网站或相关教程。怎样能够挖掘丰富食物图片背后的烹饪方法&#xff0c;让每个人都可以在家方便地学习新菜式…

ph值图片_[图]酸碱性食物怎样区分_常见食物的PH值图片

酸碱性食物怎样区分?近年来流行的“酸性食物”和“碱性食物”说法,让很多人觉得一头雾水。酸性食物应该很酸,所以柠檬、番茄应该是酸性食物吧?牛肉、鸡肉等肉类怎么会是酸性食物?其实,食物的酸碱性,和我们常说的化学物质的酸碱性不同。 以下是常见食物的PH值图片: 什么…

鸿蒙燃脂料理炉,美的蒸烤料理炉在华为商城开启众测 内置鸿蒙OS芯片

【宅秘新闻】4月27日&#xff0c;华为商城官方宣布&#xff0c;美的蒸烤料理炉PS20C2W现已在华为商城开启众测。该蒸烤料理炉内置鸿蒙OS智能感应芯片&#xff0c;支持华为手机NFC一碰联网&#xff0c;拥有1800W直喷蒸汽及4大烹饪模式&#xff0c;现已在华为商城开启众测&#x…

宝可梦探险寻宝料理php,宝可梦探险寻宝所有料理配方汇总 超梦等稀有烹饪配方...

宝可梦探险寻宝料理可谓是游戏中最为重要的要素了吧&#xff0c;一只好的宝可梦比其他的要好用出不少&#xff0c;下面就来为大家分享一下宝可梦探险寻宝中的料理配方&#xff0c;其中有大岩蛇超梦等等超级好用的宝可梦料理配方。 食谱大全 注意&#xff0c;这图片只是参考作用…

宝可梦探险寻宝料理php,宝可梦探险寻宝料理配方 宝可梦探险寻宝食谱一览

宝可梦探险寻宝料理配方。宝可梦探险寻宝中不同的烹饪可以吸引不同的宝可梦加入你的队伍&#xff0c;好的配方则可以吸引更强大的宝可梦&#xff0c;下面就一起来看看宝可梦探险寻宝食谱一览吧。 食谱大全 注意&#xff0c;这图片只是参考作用&#xff0c;不要迷信&#xff0c;…

【Leetcode】42.接雨水(困难)

一、题目 1、题目描述 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。 示例1: 输入:height = [0,1,0,2,1,0,1,3,2,1,2,1] 输出:6 解释:上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6…

假设一个定态不含空间的运动过程

“如果将你的手指放到灯泡前&#xff0c;并观察它在远处屏幕上产生的阴影&#xff0c;那么你将发现&#xff0c;当你移动自己的手指时阴影的移动速度与灯泡到屏幕的距离成正比。如果这一跟离足够大&#xff0c;原则上阴影可以以你所希望的任意大的速度移动 但是&#xff0c;当…
最新文章