首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >牛客练习赛51 D 羊吃草

牛客练习赛51 D 羊吃草

作者头像
用户2965768
发布于 2019-09-18 02:43:32
发布于 2019-09-18 02:43:32
43800
代码可运行
举报
文章被收录于专栏:wymwym
运行总次数:0
代码可运行

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

本文链接:https://blog.csdn.net/qq_41603898/article/details/100593523

建图没什么好说的,跑最大流原来的权值会被破坏,需要记录重新赋值。

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 0x7ffffff
const int M = 1000005;
const int inf = 0x7fffffff;
struct E {
	int nxt,u,v,w;
	int yuanw;
};
E edg[M];
int d[M],head[M],cnt;
int s,t,n,m;
void init() {
	cnt = 0;
	memset(head,-1,sizeof head);
}
void add(int u,int v,int w) {
	edg[cnt].v = v;
	edg[cnt].u = u;
	edg[cnt].w = w;
	edg[cnt].yuanw = w;
	edg[cnt].nxt = head[u];
	head[u] = cnt++;
	edg[cnt].v = u;
	edg[cnt].u = v;
	edg[cnt].w = 0;
	edg[cnt].yuanw = 0;
	edg[cnt].nxt = head[v];
	head[v] = cnt++;
}
bool bfs(int s,int t,int l,int r) {
	queue<int> q;
	memset(d,0,sizeof d);
	q.push(s);
	d[s] = 1;
	while(!q.empty()) {
		int top = q.front();
		q.pop();
		for(int i = head[top]; i + 1; i = edg[i].nxt) {
			int v = edg[i].v,w = edg[i].w;
			if(v>400&&v!=s&&v!=t) {
				if(v<l||v>r)continue;
			}
			if(!d[v] && w) {
				d[v] = d[top] + 1;
				q.push(v);
			}
		}
	}
	return d[t] > 0;
}
int dfs(int s,int t,int inflow,int l,int r) {
	if(s == t || !inflow) return inflow;
	int flow = 0;
	for(int i = head[s]; i + 1; i = edg[i].nxt) {
		int v = edg[i].v,w = edg[i].w;
		if(v>400&&v!=s&&v!=t) {
			if(v<l||v>r)continue;
		}
		if(w && d[v] == d[s] + 1) {
			int x = dfs(v,t,min(inflow,w),l,r);
			edg[i].w -= x;
			edg[i ^ 1].w += x;
			inflow -= x;
			flow += x;
			if(!inflow) break;
		}
	}
	if(!flow) d[s] = -2;
	return flow;
}
long long dinic(int s,int t,int l,int r) {
	long long ans = 0;
	while(bfs(s,t,l,r))
		ans += dfs(s,t,inf,l,r);
	return ans;
}
struct N {
	int l,r;
} no[405];
int main() {
	int a,b,c;
	scanf("%d %d",&n,&m);
	int s = 1001, t = 1002;
	init();
	ll ans = 0;
	for(int i=1; i<=n; i++) {
		scanf("%d",&no[i].l);
	}
	for(int i=1; i<=n; i++) {
		scanf("%d",&no[i].r);
	}
	for(int i=1; i<=n; i++) {
		add(s,i,1);
		for(int l = no[i].l;l<=no[i].r; l++) {
			add(i,l+400,1);
		}
	}
	for(int i=1;i<=400;i++){
		add(i+400,t,1);
	} 
	int l,r;
	while(m--) {
		scanf("%d %d",&l,&r);
		printf("%lld\n",dinic(s,t,l+400,r+400));
		for(int i=0;i<cnt;++i){
			edg[i].w = edg[i].yuanw;
		}
	}
	return 0;
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2019年09月07日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
编辑精选文章
换一批
2019 牛客暑期多校训练营 第五场 F maximum clique 1 最大独立集
解:至少两位 补集是 至多一位不同也即恰好一位不同,因为这些数相异 ,不存在0为不同。
用户2965768
2019/08/14
3800
[2019HDU多校第一场][HDU 6582][E. Path]
题意: t 组样例,n个点,m条边。i 行a到b距离c. 要求去掉最短路的最小代价。去掉每条路代价等于长度。
用户2965768
2019/08/01
3070
2019 CCPC 秦皇岛 Escape 最大流
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
用户2965768
2019/09/29
8240
2019  CCPC 秦皇岛 Escape  最大流
POJ 2987 Firing
Description You’ve finally got mad at “the world’s most stupid” employees of yours and decided to do
attack
2018/04/12
6090
【模板】网络最大流 Dinic
【模板】网络最大流 #include <bits/stdc++.h> using namespace std; #define INF 0x7ffffff const int M = 1000005; struct E{ int nxt,v,w; }; E edge[M]; int dpth[M],head[M],cnt; int n,m,s,t; void add(int u,int v,int w){ cnt++; edge[cnt].v = v; edge[cnt].w = w; edge
用户2965768
2019/04/22
5830
POJ - 3281 Dining 网络流
题意:n个奶牛,有 f 种食物, d种饮料。 接下来n行,每行先是f1,d1,接下来f1个食物,d1个饮料 表示该奶牛喜欢的食物和水。求最多有多少奶牛能得到自己喜欢的食物。
用户2965768
2019/08/14
4580
YbtOJ 582「网络流」大收藏家
共有 n 名收藏家参加了这次大会,每个人都带了一种与众不同的藏品来,其中第 i 个收藏家带了 a_i 个自己类型的藏品。
yzxoi
2022/09/19
3350
洛谷P2774 方格取数问题(最小割)
题意 $n \times m$的矩阵,不能取相邻的元素,问最大能取多少 Sol 首先补集转化一下:最大权值 = sum - 使图不连通的最小权值 进行黑白染色 从S向黑点连权值为点权的边 从白点向T连权值为点券的边 黑点向白点连权值为INF的边 这样就转化成了最小割问题,跑Dinic即可 /* 首先补集转化一下:最大权值 = sum - 使图不连通的最小权值 进行黑白染色 从S向黑点连权值为点权的边 从白点向T连权值为点券的边 黑点向白点连权值为INF的边 跑Dinic */ #include<cstdio
attack
2018/07/27
5340
POJ 3308 Paratroopers
Description It is year 2500 A.D. and there is a terrible war between the forces of the Earth and the Mars. Recently, the commanders of the Earth are informed by their spies that the invaders of Mars want to land some paratroopers in the m × ngrid yard of
attack
2018/04/11
6150
PAT「1003 Universal Travel Sites (35分)」
题目链接:PAT「1003 Universal Travel Sites (35分)」 。
hotarugali
2022/03/01
5020
P3227 [HNOI2013]切糕
题目描述 经过千辛万苦小 A 得到了一块切糕,切糕的形状是长方体,小 A 打算拦腰将切糕切成两半分给小 B。出于美观考虑,小 A 希望切面能尽量光滑且和谐。于是她找到你,希望你能帮她找出最好的切割方案。 出于简便考虑,我们将切糕视作一个长 P、宽 Q、高 R 的长方体点阵。我们将位于第 z层中第 x 行、第 y 列上(1≤x≤P, 1≤y≤Q, 1≤z≤R)的点称为(x,y,z),它有一个非负的不和谐值 v(x,y,z)。一个合法的切面满足以下两个条件: 与每个纵轴(一共有 P*Q 个纵轴)有且仅有一个交
attack
2018/04/12
6250
P2756 飞行员配对方案问题
题目背景 第二次世界大战时期.. 题目描述 英国皇家空军从沦陷国征募了大量外籍飞行员。由皇家空军派出的每一架飞机都需要配备在航行技能和语言上能互相配合的2 名飞行员,其中1 名是英国飞行员,另1名是外籍飞行员。在众多的飞行员中,每一名外籍飞行员都可以与其他若干名英国飞行员很好地配合。如何选择配对飞行的飞行员才能使一次派出最多的飞机。对于给定的外籍飞行员与英国飞行员的配合情况,试设计一个算法找出最佳飞行员配对方案,使皇家空军一次能派出最多的飞机。 对于给定的外籍飞行员与英国飞行员的配合情况,编程找出一个最佳飞
attack
2018/04/12
5930
LOJ#505. 「LibreOJ β Round」ZQC 的游戏(最大流)
题意 题目链接 Sol 首先把第一个人能吃掉的食物删掉 然后对每个人预处理出能吃到的食物,直接限流跑最大流就行了 判断一下最后的最大流是否等于重量和 注意一个非常恶心的地方是需要把除1外所有人都吃不到的食物删掉 #include<bits/stdc++.h> using namespace std; const int MAXN = 1e6 + 10, INF = 1e9 + 10; int sqr(int x) {return x * x;} inline int read() { char c
attack
2019/02/26
4230
种树 差分约束|贪心
每次种的树在重叠区间越多,种的树越少。只有结束位置才会重合,就对区间结束的位置从小到大排序。
用户2965768
2019/04/18
3430
洛谷P2598 [ZJOI2009]狼和羊的故事
题目描述 “狼爱上羊啊爱的疯狂,谁让他们真爱了一场;狼爱上羊啊并不荒唐,他们说有爱就有方向......” Orez听到这首歌,心想:狼和羊如此和谐,为什么不尝试羊狼合养呢?说干就干! Orez的羊狼圈可以看作一个n*m个矩阵格子,这个矩阵的边缘已经装上了篱笆。可是Drake很快发现狼再怎么也是狼,它们总是对羊垂涎三尺,那首歌只不过是一个动人的传说而已。所以Orez决定在羊狼圈中再加入一些篱笆,还是要将羊狼分开来养。 通过仔细观察,Orez发现狼和羊都有属于自己领地,若狼和羊们不能呆在自己的领地,那它们就会变
attack
2018/04/11
6170
图论--网络流--最小割 HDU 2485 Destroying the bus stations(最短路+限流建图)
Gabiluso is one of the greatest spies in his country. Now he’s trying to complete an “impossible” mission ----- to make it slow for the army of City Colugu to reach the airport. City Colugu has n bus stations and m roads. Each road connects two bus stations directly, and all roads are one way streets. In order to keep the air clean, the government bans all military vehicles. So the army must take buses to go to the airport. There may be more than one road between two bus stations. If a bus station is destroyed, all roads connecting that station will become no use. What’s Gabiluso needs to do is destroying some bus stations to make the army can’t get to the airport in k minutes. It takes exactly one minute for a bus to pass any road. All bus stations are numbered from 1 to n. The No.1 bus station is in the barrack and the No. n station is in the airport. The army always set out from the No. 1 station. No.1 station and No. n station can’t be destroyed because of the heavy guard. Of course there is no road from No.1 station to No. n station. Please help Gabiluso to calculate the minimum number of bus stations he must destroy to complete his mission.
风骨散人Chiam
2020/10/28
3730
网络流详解(流网图一般能够反映什么信息)
https://www.cnblogs.com/ZJUT-jiangnan/p/3632525.html
全栈程序员站长
2022/08/02
9910
网络流详解(流网图一般能够反映什么信息)
YbtOJ 581「网络流」图上旅行
小 C 来到了 F 国,小 C 想好好地参观 F 国。F 国可以看一个有 n 个点 m 条边的有向无环图,小 C 刚开始站在 1 号点。
yzxoi
2022/09/19
7090
CDQZ 0003:jubeeeeeat
总时间限制: 1000ms 内存限制: 256000kB描述 众所周知,LZF很喜欢打一个叫Jubeat的游戏。这是个音乐游戏,游戏界面是4×4的方阵,会根据音乐节奏要求玩家按下一些指定方块(以下称combo)。LZF觉得这太简单了,于是自己仿了个游戏叫Jubeeeeeat,唯一不同之处就是界面大小,Jubeeeeeat的界面为n×n的方阵。 在某一刻,界面同时出现了若干个combo。LZF终于觉得有些困难了,但毕竟LZF不是普通人,他有很多只手。LZF的手分为m只“肉质手”和q只“意念手”。顾名思义,
attack
2018/04/11
6070
CDQZ 0003:jubeeeeeat
Day5下午解题报告1
预计分数:100+60+30=190 实际分数:100+60+30=190 终于有一道无脑T1了哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈
attack
2018/04/11
5950
相关推荐
2019 牛客暑期多校训练营 第五场 F maximum clique 1 最大独立集
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档
本文部分代码块支持一键运行,欢迎体验
本文部分代码块支持一键运行,欢迎体验