专栏首页wym牛客练习赛51 D 羊吃草

牛客练习赛51 D 羊吃草

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

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

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

#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;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 牛客练习赛23 D

      利用全排列函数加vector数组,开十个vector,存a到i字母出现的位置,最后每个vector再push_back(字符串长度加一)作为结束标志。

    用户2965768
  • 牛客练习赛59 A~~D

    杨鹏伟
  • 牛客练习赛61 - B - 吃水果

    最近米咔买了n个苹果和m个香蕉,他每天可以选择吃掉一个苹果和一个香蕉(必须都吃一个,即如果其中一种水果的数量为0,则他不能进行这个操作),或者使用魔法将某一种水...

    Michael阿明
  • 空降CTO是救世主?不,也可能是臭流氓

    但在疫情的影响下,不少企业都受到了不同程度的影响,为度过经济效益下降的暂时性困难期,很多企业迫于生存压力而选择减薪、降薪或人事调整来缓解运营压力。

    吃草的罗汉
  • 牛客练习赛34 D. little w and Exchange(思维)

    题目链接:https://ac.nowcoder.com/acm/contest/297/D

    Ch_Zaqdt
  • 【神经网络会梦到电子羊吗?】“匹配模式”暴露神经网络致命缺陷

    ---- 新智元报道 来源:aiweirdness、gizmodo 编译:肖琴 【新智元导读】神经网络的专长之一是图像识别。谷歌、微软、IBM、Fac...

    新智元
  • 类、抽象类、接口的综合小练习---运动员和教练案例

    黑泽君
  • 从田间到餐桌:GPU是如何影响我们的生活

    随着全球人口增加,许多人开始忧心粮食短缺的问题,全球各地的科学家和研究人员相继采用 GPU 来解决粮食相关的难题。 从照料家畜与作物到评估饮食内容,GPU 用于...

    GPUS Lady
  • 牛客练习赛33 D. tokitsukaze and Inverse Number(逆序数定理)

    题目链接:https://ac.nowcoder.com/acm/contest/308/D

    Ch_Zaqdt

扫码关注云+社区

领取腾讯云代金券