首页 > 其他分享 >网络流建模之拆点，原理详解，OJ练习

网络流建模之拆点，原理详解，OJ练习

时间：2024-03-15 23:31:34浏览次数：22  
标签：OJ 容量 int 拆点 建模 入点 include dp

一、网络流建模之拆点

1.1问题引入

现有工厂s，仓库t，中转站若干，s到中转站有若干道路，中转站到仓库有道路若干，工厂要向仓库运输一定的货物，每条道路都有最大运输量限制，问最大运货量。

1.2转化为网络流问题

显然上述问题我们可以轻松的建模转化为网络流问题

该流网络的最大流就是问题的解

1.3带容量点的流网络

随着需求量越来越大，中转站工作人员的工作负担也越来越重，因此中转站也做出了中转量限制，问此时的最大运货量

1.4带容量点拆点

我们将每个中转站拆成两个点，一个入点，代表从工厂出发进入中转站，一个出点，代表从中转站出发进入仓库

然后入点和出点之间连边，边的容量为中转量，此时流网络的最大流就是问题的解

1.5拆点的应用

拆点法为我们网络流问题一种常用的建模方式，很多问题都可以抽象为带容量限制点的流网络问题，然后拆点建模求最大流/最小割解决。

二、OJ练习

POJ3281 Dining

原题链接

3281 – Dining (poj.org)

思路分析

题目讲每种食物或饮料只能被一头牛消耗，然后一头牛也只能选择一种饮料和食物，那么对于这样的条件我们就可以通过把牛拆点来简化问题（如上图）

每头牛拆成一个入点和一个出点，每头牛能吃的食物向该牛的入点连边，每头牛的出点又都向其能喝的饮料连边，然后源点向所有的食物连边，所有饮料向汇点连边，上述所有边的容量都是1

这样我们建立的这个网络的最大流就对应了原问题的最优解，因为最大流的一点流量代表遵守规则的同时一头牛被满足，而又是最大的，所以最大流就是原问题的解。

AC代码
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 410, M = (20000 + 300) << 1, inf = 1e9;
int n, F, D;
int s, t, q[N], f, b, d[N], head[N], cur[N], idx;
struct edge{
	int v, c, nxt;
}edges[M];
void addedge(int u, int v, int c){
	edges[idx].v = v, edges[idx].c = c, edges[idx].nxt = head[u], head[u] = idx++;
}
void add(int u, int v, int c){
	addedge(u, v, c), addedge(v, u, 0);
}
bool bfs(){
	memset(d, 0, sizeof d), f = b = 0, d[q[b++] = s] = 1;
	while(b - f){
		int u = q[f++];
		for(int i = head[u]; ~i; i = edges[i].nxt){
			int v = edges[i].v;
			if(!d[v] && edges[i].c){
				d[q[b++] = v] = d[u] + 1;
				if(v == t) return true;
			} 
		}
	}
	return false;
}
int dfs(int u, int lim){
	if(u == t) return lim;
	int res = 0;
	for(int i = cur[u]; ~i && lim; i = edges[i].nxt){
		cur[u] = i;
		int v = edges[i].v;
		if(d[v] == d[u] + 1 && edges[i].c){
			int incf = dfs(v, min(lim, edges[i].c));
			if(!incf) d[v] = 0;
			res += incf, lim -= incf, edges[i].c -= incf, edges[i ^ 1].c += incf;
		}
	}
	return res;
}
int dinic(){
	int res = 0;
	while(bfs())
		memcpy(cur, head, sizeof head), res += dfs(s, inf);
	return res;
}
int main()
{
	//freopen("in.txt", "r", stdin);
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> n >> F >> D, s = 0, t = n * 2 + F + D + 1, memset(head, -1, sizeof head);
	for(int i = 1, x, y; i <= n; i++){
		cin >> x >> y, add(i, i + n, 1);
		for(int j = 0, z; j < x; j++) cin >> z, add(2 * n + z, i, 1);
		for(int j = 0, z; j < y; j++) cin >> z, add(i + n, 2 * n + F + z, 1);
	}
	for(int i = 1; i <= F; i++) add(s, 2 * n + i, 1);
	for(int i = 1; i <= D; i++) add(2 * n + F + i, t, 1);
	cout << dinic();
    return 0;
}

P2766 最长不下降子序列问题

原题链接

P2766 最长不下降子序列问题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路分析

在这里插入图片描述

  • 问题一：直接O(n)动规解决（这里规定状态数组dp[]），答案记为ma

  • 问题二：我们把问题抽象成网络流模型

    • 每个dp[i]都看成一个节点，然后拆点为入点出点
    • 对于dp[i] = 1，从源点向入点连容量为1的边
    • 对于dp[i] = ma，从出点向汇点连容量为1的边
    • 入点和出点之间连容量为1的边

    这样答案就是最大流，因为最大流每一点流量对应了一个最长非下降子序列，容量的设定又保证了路径不交叉

  • 问题三：将源点到dp[1]入点的边设置为容量为无穷，dp[1]的入点和出点的边也容量为正无穷，dp[n]和汇点同理，然后在残留网络上再次跑最大流加到上一问的最大流上就是答案

AC代码
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1010, M = (505 * 3 + 505 * 505) << 1, inf = 1e9;
using namespace std;
struct edge{
	int v, c, nxt;
}edges[M];
int head[N], cur[N], idx;
int q[N], d[N], f, b, s, t;
int a[505], dp[505], n, ma;
void addedge(int u, int v, int c){
	edges[idx] = {v, c, head[u]}, head[u] = idx++;
}
void add(int u, int v, int c){
	addedge(u, v, c), addedge(v, u, 0);
}
bool bfs(){
	memset(d, 0, sizeof d), b = f = 0, d[q[b ++] = s] = 1;
	while(b - f){
		int u = q[f++];
		for(int i = head[u]; ~i; i = edges[i].nxt){
			int v = edges[i].v;
			if(!d[v] && edges[i].c){
				d[q[b++] = v] = d[u] + 1;
				if(v == t) return true;
			}
		}
	}
	return false;
}
int dfs(int u, int lim){
	if(u == t) return lim;
	int res = 0;
	for(int i = cur[u], v; ~i && lim; i = edges[i].nxt){
		v = edges[i].v;
		if(d[v] == d[u] + 1 && edges[i].c){
			int incf = dfs(v, min(lim, edges[i].c));
			if(!incf) d[v] = 0;
			res += incf, edges[i].c -= incf, edges[i^1].c += incf, lim -= incf;
		} 
	}
	return res;
}
int dinic(){
	int res = 0;
	while(bfs())
		memcpy(cur, head, sizeof head), res += dfs(s, inf);
	return res;
}
int main(){
	//freopen("in.txt", "r", stdin);
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	cin >> n, s = 0, t = n << 1 | 1, memset(head, -1, sizeof head);
	for(int i = 1; i <= n; i++) cin >> a[i];
	for(int i = 1; i <= n; i++){
		add(i, i + n, 1), dp[i] = 1;
		for(int j = 1; j < i; j++) if(a[i] >= a[j]) dp[i] = max(dp[i], dp[j] + 1);
		for(int j = 1; j < i; j++) if(a[i] >= a[j] && dp[i] == dp[j] + 1) add(j + n, i, 1);
		ma = max(ma, dp[i]);
	}
	for(int i = 1; i <= n; i++) if(dp[i] == ma) add(i + n, t, 1); else if(dp[i] == 1) add(s, i, 1);
	cout << ma << '\n';
	if(ma == 1) cout << n << '\n' << n;
	else{
		int res = dinic();
		cout << res << '\n';
		for(int i = 0, u, v; i < idx; i++){
			u = edges[i ^ 1].v, v = edges[i].v;
			if(u == s && v == 1) edges[i].c = inf;
			else if(u == 1 && v == n + 1) edges[i].c = inf;
			else if(u == n && v == 2 * n) edges[i].c = inf;
			else if(u == n * 2 && v == t) edges[i].c = inf;
		}	
		res += dinic(), cout << res;
	}
	return 0;
}
//task1——lis
//task2——dinic
//task3——inf ——dinic

POJ3498 March of the Penguins

原题链接

3498 – March of the Penguins (poj.org)

思路分析

在这里插入图片描述

考虑建立虚拟源点，每个冰块上的企鹅都是从虚拟源点输送过去的，然后可以会面的冰块我们作为汇点

将每个冰块拆点为入点和出点，入点到出点边的容量即最大起跳次数

源点到入点的边的容量为初始企鹅数目

出点到其它距离在最大跳程内冰块的入点的边容量为正无穷

然后枚举每个冰块作为汇点时的最大流，如果最大流是总企鹅数目，那么该冰块就可以作为会面冰块

建模后，源点到汇点的最大流的每一点流量就是若干次跳跃跳到会面冰块上的一个企鹅，并且保证了所有冰块的起跳次数的限制并且保证最大，所以是原问题的解。

AC代码
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 210, M = (105 * 105 + 105 * 3) << 1, inf = 1e9;
const double eps = 1e-8;
int head[N], cur[N], idx;
int q[N], d[N], b, f, s, t, tot, ans;
int n;
double dst;
struct pos{
	double x, y;
}p[N];
struct edge{
	int v, c, nxt; 
}edges[M];
void addedge(int u, int v, int c){
	edges[idx].v = v, edges[idx].c = c, edges[idx].nxt = head[u], head[u] = idx++;
}
void add(int u, int v, int c){
	addedge(u, v, c), addedge(v, u, 0);
}
bool bfs(){
	memset(d, 0, sizeof d),f = b = 0, d[q[b++] = s] = 1;
	while(b	- f){
		int u = q[f++];
		for(int i = head[u]; ~i; i = edges[i].nxt){
			int v = edges[i].v;
			if(!d[v] && edges[i].c){
				d[q[b++] = v] = d[u] + 1;
				if(v == t) return true;
			}
		}	
	}
	return false;
}
int dfs(int u, int lim){
	if(u == t) return lim;
	int res = 0;
	for(int i = cur[u]; ~i && lim; i = edges[i].nxt){
		int v = edges[i].v;
		cur[u] = i;
		if(d[v] == d[u] + 1 && edges[i].c){
			int incf = dfs(v, min(edges[i].c, lim));
			if(!incf) d[v] = 0;
			lim -= incf, edges[i].c -= incf, edges[i ^ 1].c += incf, res += incf;
		}
	}
	return res;
} 
int dinic(){
	int res = 0;
	while(bfs())
		memcpy(cur, head, sizeof head), res += dfs(s, inf);
	return res;
}
bool check(double dx, double dy){
	return dx * dx + dy * dy < dst * dst + eps;
}
int main(){
	//freopen("in.txt", "r", stdin);
	ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
	int _ = 1;
	cin >> _;
	while(_--){
		cin >> n >> dst, memset(head, -1, sizeof head), idx = tot = ans = 0;
		for(int i = 1, a, b; i <= n; i++)
			cin >> p[i].x >> p[i].y >> a >> b, tot += a, add(s, i, a), add(i, i + n, b);
		for(int i = 1; i <= n; i++)	
			for(int j = i + 1; j <= n; j++)	
				if(check(p[i].x - p[j].x, p[i].y - p[j].y)) add(i + n, j, inf), add(j + n, i, inf);
		for(t = 1; t <= n; t++)	{
			for(int i = 0; i < idx; i += 2) edges[i].c += edges[i ^ 1].c, edges[i ^ 1].c = 0;
			if(dinic() == tot) ans++, cout << t - 1 << ' ';
		}
		ans ? cout << '\n' : cout << "-1\n";
	}
	return 0;
}

标签：OJ,容量,int,拆点,建模,入点,include,dp
From： https://blog.csdn.net/EQUINOX1/article/details/136752397

相关文章

  • csproj技巧
    1、在项目中我们经常写string?Message{get;set;}明明是引用类型，它底下还是会出现波浪线，我们可以打开csproj找到Nullable将它改为disable，或者删除，它默认是disable<Nullable>disable</Nullable>2、我们的WPF中可能会使用到Winform的类库，添加UseWindowsForms，一定要写在UseWPF......
  • javabean:VO和POJO的区别？
    实体类都是JavaBean的一种 实际上没区别 功能都一样 使用的时候区别（VO一般在命名结尾有大写VO 以做区别）参考：https://blog.csdn.net/huang_ftpjh/article/details/90232922关于java的几种对象(PO,VO,DAO,BO,POJO，DTO)解释摘抄参考2：https://blog.csdn.net/weixin_6938139......
  • 55 人见人爱A-B 东华oj
    1.问题描述A和B是两个集合，A-B求的是两个集合的差，就是做集合的减法运算。2.输入说明输入数据包含T个测试实例。首先输入数字T，然后输入T组测试数据，每组输入数据占1行,每行数据的开始是2个整数n(0<=n<=100)和m(0<=m<=100),分别表示集合A和集合B的元素个数，然后紧跟着n+m个元素......
  • ESD电子枪建模与系统仿真方法概述
    0引言        ESD电子枪的全尺寸建模对于电子枪内部器件的还原度虽然很高，但是该方法受限于时域算法，需要许多时间步长来稳定静态场，并且需要许多单元才能达到所需的精度，非常耗时，且对于大多数的ESD应用场景来说，并不需要充分考虑其内部的物理过程。关于全尺寸建模，参考......
  • HDOJ 2037
    今年暑假不ACProblemDescription“今年暑假不AC？”“是的。”“那你干什么呢？”“看世界杯呀，笨蛋！”“@#$%^&*%…”确实如此，世界杯来了，球迷的节日也来了，估计很多ACMer也会抛开电脑，奔向电视了。作为球迷，一定想看尽量多的完整的比赛，当然，作为新时代的好青年，你一定还会看......
  • 论面向对象的建模及应用
        本文旨在探讨面向对象的建模在软件系统开发中的应用。首先，概述了作者参与的一个实际的软件系统开发项目，并详细描述了在该项目中担任的主要工作。接着，深入阐述了用例模型和分析模型的概念、作用以及在实际项目中的具体应用。最后，分析了在使用这两种模型过程中遇到的......
  • 数字控制系统Simulink仿真建模（1）(仿真步长和中断触发的设置)
    仿真步长的设置 对于数字控制系统而言，在Simulink仿真环境中，总的来说有三个步长需要考虑。首先由于数字控制系统是离散系统，因此需要在仿真模型的模型设置中将求解器类型设置为固定步长，求解器设置为离散，固定步长大小为整个模型的最小执行步长，即在该模型中的模块将默认按照此步......
  • 清风数学建模论文写作方法学习笔记
    标题对论文题目的要求是:简短精炼、高度概括、准确得体、恰如其分。既要准确表达论文内容，恰当反映所研究的范围和深度;又要尽可能概括、精炼，力求题目的字数少。论文题目的字数一般不要超过20个字。不过，当希望题目字数少与恰当反映论文内容两者发生矛盾时，宁可多用几个字也要力......
  • 【OJ】K 个一组翻转链表
    题目基本思路：用计数+栈实现分段，K个一组地翻转链表。#include<bits/stdc++.h>#include<stack>usingnamespacestd;structlist_node{intval;structlist_node*next;};list_node*input_list(){intval,n;scanf("%d",&n);list_node*phea......
  • 【OJ】猫狗队列
    猫狗队列思路用两个队列分别保存猫、狗，用各个的入队计数判断任一出队时选择哪一种，指定类别出队则直接从相应队列出队。实现Python输入测试testCatDogQ.txt65adddog29addcat9adddog40adddog38addcat32adddog20addcat45pollAlladdcat37isDogEm......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99