7.31 网络流

2023-10-15 03:10
文章标签 网络 7.31

本文主要是介绍7.31 网络流，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

A题：

Description

AveryBoy喜欢玩LOL，但是他技术太菜，总是被别人喷“这么菜玩什么游戏，回家养猪去吧”。终于有一天，他被喷的受不了了，于是回家养猪。不过他家的养猪场在下雨天的时候总是被淹，所以他用读书学来的知识设计了一套排水系统。他还设计了一套装置，可以控制排水管道的水流流量。现在有n个排水管道，m个排水节点，问你从1到m的最大排水流量。

Input

有多组测试数据，对于每组测试数据，第一行是两个整数n，m（0 <= n <= 200，2 <= m <= 200），分别表示排水管道数和排水节点数。之后n行每行包含3个整数，u，v，w（1<=u,v<=m，0<=w<=1e7，u!=v），表示从u到v的排水管道的水流流量是w。

Output

对于每种情况输出一个整数，表示从1到m的最大排水流量。

Sample Input

5 4 
1 2 40 
1 4 20 
2 4 20 
2 3 30 
3 4 10

Sample Output

50

HINT

模板题，直接套用邻接表-ISAP即可

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
#define MAXN 100010
#define MAXM 400010
#define INF 0x3f3f3f3f
struct Edge
{int to,next,cap,flow;
} edge[MAXM];
int tol;
int head[MAXN];
int gap[MAXN],dep[MAXN],pre[MAXN],cur[MAXN];
void init()
{tol=0;memset(head,-1,sizeof head);
}
void addedge(int u,int v,int w,int rw=0)
{edge[tol].to=v;edge[tol].cap=w;edge[tol].next=head[u];edge[tol].flow=0;head[u]=tol++;edge[tol].to=u;edge[tol].cap=rw;edge[tol].next=head[v];edge[tol].flow=0;head[v]=tol++;
}
int sap(int start,int endd,int N)
{memset(gap,0,sizeof gap);memset(dep,0,sizeof dep);memcpy(cur,head,sizeof head);int u=start;pre[u]=-1;gap[0]=N;int ans=0;while(dep[start]<N){if(u==endd){int Min=INF;for(int i=pre[u];i!=-1;i=pre[edge[i^1].to])if(Min>edge[i].cap-edge[i].flow)Min=edge[i].cap-edge[i].flow;for(int i=pre[u];i!=-1;i=pre[edge[i^1].to]){edge[i].flow+=Min;edge[i^1].flow-=Min;}u=start;ans+=Min;continue;}bool flag=false;int v;for(int i=cur[u];i!=-1;i=edge[i].next){v=edge[i].to;if(edge[i].cap-edge[i].flow&&dep[v]+1==dep[u]){flag=true;cur[u]=pre[v]=i;break;}}if(flag){u=v;continue;}int Min=N;for(int i=head[u];i!=-1;i=edge[i].next)if(edge[i].cap-edge[i].flow&&dep[edge[i].to]<Min){Min=dep[edge[i].to];cur[u]=i;}gap[dep[u]]--;if(!gap[dep[u]]) return ans;dep[u]=Min+1;gap[dep[u]]++;if(u!=start) u=edge[pre[u]^1].to;}return ans;
}
int main()
{int n,m;while(~scanf("%d%d",&n,&m)){int i;init();for(i=1;i<=n;i++){int u,v,w;scanf("%d%d%d",&u,&v,&w);addedge(u,v,w);}long long ans=sap(1,m,n);printf("%lld\n",ans);}return 0;
}
View Code

B题：

Description

如题，给你一个容量网络，请你找出最大流。

Input

第一行输入包含一个整数T，表示测试用例的数量。

对于每个测试用例，第一行包含两个整数N和M，表示图中顶点和边的数量。（2 <= N <= 15,0 <= M <= 1000）

接下来的M行，每行包含三个整数X，Y和C，表示从X到Y有一个边，它的容量是C.（1 <= X，Y <= N，1 <= C <= 1000）

Output

对于每个测试用例，您应该输出从源点1到汇点N的最大流量。

Sample Input

2
3 2
1 2 1
2 3 1
3 3
1 2 1
2 3 1
1 3 1

Sample Output

Case 1: 1
Case 2: 2

HINT

模板，too

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
#define MAXN 100010
#define MAXM 400010
#define INF 0x3f3f3f3f
struct Edge
{int to,next,cap,flow;
} edge[MAXM];
int tol;
int head[MAXN];
int gap[MAXN],dep[MAXN],pre[MAXN],cur[MAXN];
void init()
{tol=0;memset(head,-1,sizeof head);
}
void addedge(int u,int v,int w,int rw=0)
{edge[tol].to=v;edge[tol].cap=w;edge[tol].next=head[u];edge[tol].flow=0;head[u]=tol++;edge[tol].to=u;edge[tol].cap=rw;edge[tol].next=head[v];edge[tol].flow=0;head[v]=tol++;
}
int sap(int start,int endd,int N)  N是图中点的总个数
{memset(gap,0,sizeof gap);memset(dep,0,sizeof dep);memcpy(cur,head,sizeof head);int u=start;pre[u]=-1;gap[0]=N;int ans=0;while(dep[start]<N){if(u==endd){int Min=INF;for(int i=pre[u];i!=-1;i=pre[edge[i^1].to])if(Min>edge[i].cap-edge[i].flow)Min=edge[i].cap-edge[i].flow;for(int i=pre[u];i!=-1;i=pre[edge[i^1].to]){edge[i].flow+=Min;edge[i^1].flow-=Min;}u=start;ans+=Min;continue;}bool flag=false;int v;for(int i=cur[u];i!=-1;i=edge[i].next){v=edge[i].to;if(edge[i].cap-edge[i].flow&&dep[v]+1==dep[u]){flag=true;cur[u]=pre[v]=i;break;}}if(flag){u=v;continue;}int Min=N;for(int i=head[u];i!=-1;i=edge[i].next)if(edge[i].cap-edge[i].flow&&dep[edge[i].to]<Min){Min=dep[edge[i].to];cur[u]=i;}gap[dep[u]]--;if(!gap[dep[u]]) return ans;dep[u]=Min+1;gap[dep[u]]++;if(u!=start) u=edge[pre[u]^1].to;}return ans;
}
int main()
{int t;cin>>t;int d=1;while(t--){int n,m,i;scanf("%d%d",&n,&m);init();for(i=1;i<=m;i++){int x,y,c;scanf("%d%d%d",&x,&y,&c);addedge(x,y,c);}printf("Case %d: %d\n",d,sap(1,n,n));d++;}return 0;
}
View Code

C题：

 

Description

华中农业大学总共有n个老师，f种房子和d种车（1 <= n，f，d <= 200）。每个老师都有自己喜欢的一些房子和车的类型，现在要你把这些房子和车分配给这n个老师，每个老师只分配一套房子和一辆车。问你最多能使多少个老师满意对应的分配。

Input

有多组测试数据，每组测试数据第一行是3个正整数，n，f，d，表示老师个数，房子种数，车子种数。

第二行包含f个整数，其中第i个数表示第i种房子的个数。

第三行包含d个整数，其中第i个数表示第i种车子的个数。

之后n行，每行包含长度为f的字符串，其中第i行第j个字符表示第i个老师是否喜欢第j种房子，‘Y’表示喜欢，‘N’表示不喜欢。

之后n行，每行包含长度为d的字符串，其中第i行第j个字符表示第i个老师是否喜欢第j种车子，‘Y’表示喜欢，‘N’表示不喜欢。

Output

对于每组测试数据，输出一个整数，表示最大的老师满意的个数。

Sample Input

4 3 3
1 1 1
1 1 1
YYN
NYY
YNY
YNY
YNY
YYN
YYN
NNY

Sample Output

3

HINT

 

这题建图比较复杂

首先建立超级源点，与所有的房子连边，边的流量为房子的个数

然后建立超级汇点，与所有的车子连边，边的流量为车子的个数

然后关键的来了，把教师劈成两半，让教师自己与自己连边，边的流量为1，这样才能保证每个教师只能拥有一个房子和一辆车（老师拥有了一个房子之后那条路就流不了了）

然后把教师（1-n）和他喜欢的房子连边，边的流量为1（对于同一种房子老师当然只能拥有一个）

把教师（n+1-2*n）和他喜欢的车子连边，边的流量为1

注意标记清楚各个种类的点

超级源点-0

教师（1-n)(n+1-n*2)

房子（2*n+1-2*n+f)

车子（2*n+f+1,2*n+f+d)

超级汇点 2*n+f+d+1

总点数 2*n+f+d+2

还要注意边的流向，当然是单向边啊

邻接表模板

#include <bits/stdc++.h>
using namespace std;
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
#define MAXN 100010
#define MAXM 400010
#define INF 0x3f3f3f3f
struct Edge
{int to,next,cap,flow;
} edge[MAXM];
int tol;
int head[MAXN];
int gap[MAXN],dep[MAXN],pre[MAXN],cur[MAXN];
void init()
{tol=0;memset(head,-1,sizeof head);
}
void addedge(int u,int v,int w,int rw=0)
{edge[tol].to=v;edge[tol].cap=w;edge[tol].next=head[u];edge[tol].flow=0;head[u]=tol++;edge[tol].to=u;edge[tol].cap=rw;edge[tol].next=head[v];edge[tol].flow=0;head[v]=tol++;
}
int sap(int start,int endd,int N)
{memset(gap,0,sizeof gap);memset(dep,0,sizeof dep);memcpy(cur,head,sizeof head);int u=start;pre[u]=-1;gap[0]=N;int ans=0;while(dep[start]<N){if(u==endd){int Min=INF;for(int i=pre[u];i!=-1;i=pre[edge[i^1].to])if(Min>edge[i].cap-edge[i].flow)Min=edge[i].cap-edge[i].flow;for(int i=pre[u];i!=-1;i=pre[edge[i^1].to]){edge[i].flow+=Min;edge[i^1].flow-=Min;}u=start;ans+=Min;continue;}bool flag=false;int v;for(int i=cur[u];i!=-1;i=edge[i].next){v=edge[i].to;if(edge[i].cap-edge[i].flow&&dep[v]+1==dep[u]){flag=true;cur[u]=pre[v]=i;break;}}if(flag){u=v;continue;}int Min=N;for(int i=head[u];i!=-1;i=edge[i].next)if(edge[i].cap-edge[i].flow&&dep[edge[i].to]<Min){Min=dep[edge[i].to];cur[u]=i;}gap[dep[u]]--;if(!gap[dep[u]]) return ans;dep[u]=Min+1;gap[dep[u]]++;if(u!=start) u=edge[pre[u]^1].to;}return ans;
}
int main()
{int n,f,d;int dd[220],ff[220];while(~scanf("%d%d%d",&n,&f,&d)){int i,j;init();for(i=1;i<=f;i++)scanf("%d",&ff[i]);for(i=1;i<=d;i++)scanf("%d",&dd[i]);char str[210];for(i=1;i<=n;i++){addedge(i,i+n,1);}for(i=1;i<=n;i++){scanf("%s",str);getchar();for(j=0;j<f;j++){if(str[j]=='Y'){addedge(2*n+j+1,i,1);}}}for(i=1;i<=n;i++){scanf("%s",str);getchar();for(j=0;j<d;j++){if(str[j]=='Y'){addedge(i+n,2*n+f+j+1,1);}}}for(i=2*n+1;i<=2*n+f;i++){addedge(0,i,ff[i-2*n]);}for(i=2*n+f+1;i<=2*n+f+d;i++){addedge(i,2*n+f+d+1,dd[i-2*n-f]);}int ans=sap(0,2*n+f+d+1,2*n+f+d+2);cout<<ans<<endl;}return 0;
}
View Code

D题：

Description

在网格地图上有n个人和n个房子。在每个单位时间内，每个人都可以水平或垂直移动到相邻点。对于每个人，你需要为他移动的每一步支付1美元的旅行费，直到他进入房子。每个房子只能容纳一个人。现在问你所有人都回到房子所需要的最少费用是多少？输入是一个网格图，‘.’表示空地，‘H’表示房子，‘m’表示人。

Input

有多组测试数据，对于每组测试数据第一行是两个正整数n，m表示地图的行和列（2<=n，m<=100）。地图上有相同数量的房子和人，房子最多不超过100。输入以n=0，m=0结束。

Output

对于每组测试数据输出一个整数，表示所有人都回到房子所需的最小费用。

Sample Input

2 2
.m
H.
5 5
HH..m
.....
.....
.....
mm..H
7 8
...H....
...H....
...H....
mmmHmmmm
...H....
...H....
...H....
0 0

Sample Output

2
10
28

HINT

 

这题建图：

把超级源点和人连起来，cost为0，流量为1

把超级汇点和房子连起来，cost为0，流量为1

把人和房子连起来,cost为他俩的曼哈顿距离（横坐标绝对值之差+纵坐标绝对值之差），流量为1

最小费用流模板

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<vector>
#include<queue>
#include<malloc.h>
using namespace std;
typedef long long ll;
#define maxn 300
const int MAXN = 10000;
const int MAXM = 100000;
const int INF = 0x3f3f3f3f;
struct Edge
{int to,next,cap,flow,cost;
} edge[MAXM];
int head[MAXN],tol;
int pre[MAXN],dis[MAXN];
bool vis[MAXN];
int N;//节点总个数，节点编号从0~N-1
void init(int n)
{N = n;tol = 0;//tol要初始化为0，按位或才能对memset(head,-1,sizeof(head));
}
void addedge(int u,int v,int cap,int cost)//加边
{edge[tol].to = v;edge[tol].cap = cap;edge[tol].cost = cost;edge[tol].flow = 0;edge[tol].next = head[u];head[u] = tol++;edge[tol].to = u;edge[tol].cap = 0;edge[tol].cost = -cost;edge[tol].flow = 0;edge[tol].next = head[v];head[v] = tol++;
}
bool spfa(int s,int t)//找增广路
{queue<int>q;for(int i = 0; i <= t+2; i++){dis[i] = INF;vis[i] = false;pre[i] = -1;}dis[s] = 0;vis[s] = true;q.push(s);while(!q.empty()){int u = q.front();q.pop();vis[u] = false;for(int i = head[u]; i != -1; i = edge[i].next){int v = edge[i].to;if(edge[i].cap > edge[i].flow && dis[v] > dis[u] + edge[i].cost ){dis[v] = dis[u] + edge[i].cost;pre[v] = i;if(!vis[v]){vis[v] = true;q.push(v);}}}}if(pre[t] == -1)return false;else return true;
}
//int minCostMaxflow(int s,int t,int &cost)
int minCostMaxflow(int s,int t)//最小费用最大流
{int flow = 0;int ans=0;//cost = 0;while(spfa(s,t)){int Min = INF;for(int i = pre[t]; i != -1; i = pre[edge[i^1].to])if(Min > edge[i].cap - edge[i].flow)Min = edge[i].cap - edge[i].flow;for(int i = pre[t]; i != -1; i = pre[edge[i^1].to]){edge[i].flow += Min;edge[i^1].flow -= Min;//cost += edge[i].cost * Min;
        }ans+=dis[t];flow += Min;}return ans;
}
char maze[110][110];
int main()
{while(1){int n,m,j;int nx[110],ny[110],mx[110],my[110];scanf("%d%d",&n,&m);if(n==0&&m==0)break;memset(head,-1,sizeof head);int i;for(i=1;i<=n;i++){scanf("%s",maze[i]+1);}int tm=1,th=1;for(i=1;i<=n;i++){for(j=1;j<=m;j++){if(maze[i][j]=='m'){nx[tm]=i;ny[tm]=j;tm++;}else if(maze[i][j]=='H'){mx[th]=i;my[th]=j;th++;}}}tm--,th--;init(n);for(i=1;i<=tm;i++){addedge(0,i,1,0);}for(i=tm+1;i<=tm+th;i++){addedge(i,tm+th+1,1,0);}for(i=1;i<=tm;i++){for(j=1;j<=th;j++){int dis=abs(nx[i]-mx[j])+abs(ny[i]-my[j]);addedge(i,j+tm,1,dis);}}int ans=minCostMaxflow(0,tm+th+1);cout<<ans<<endl;}return 0;
}
View Code

 

转载于:https://www.cnblogs.com/raincle/p/9398121.html

这篇关于7.31 网络流的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/214981。

相关文章

Qt实现网络数据解析的方法总结

Qt实现网络数据解析的方法总结

《Qt实现网络数据解析的方法总结》在Qt中解析网络数据通常涉及接收原始字节流,并将其转换为有意义的应用层数据,这篇文章为大家介绍了详细步骤和示例,感兴趣的小伙伴可以了解下... 目录1. 网络数据接收2. 缓冲区管理（处理粘包/拆包）3. 常见数据格式解析3.1 jsON解析3.2 XML解析3.3 自定义
阅读更多...
Linux系统配置NAT网络模式的详细步骤(附图文)

Linux系统配置NAT网络模式的详细步骤(附图文)

《Linux系统配置NAT网络模式的详细步骤(附图文)》本文详细指导如何在VMware环境下配置NAT网络模式,包括设置主机和虚拟机的IP地址、网关,以及针对Linux和Windows系统的具体步骤,... 目录一、配置NAT网络模式二、设置虚拟机交换机网关2.1 打开虚拟机2.2 管理员授权2.3 设置子
阅读更多...
揭秘Python Socket网络编程的7种硬核用法

揭秘Python Socket网络编程的7种硬核用法

《揭秘PythonSocket网络编程的7种硬核用法》Socket不仅能做聊天室,还能干一大堆硬核操作,这篇文章就带大家看看Python网络编程的7种超实用玩法,感兴趣的小伙伴可以跟随小编一起... 目录1.端口扫描器：探测开放端口2.简易 HTTP 服务器：10 秒搭个网页3.局域网游戏：多人联机对战4.
阅读更多...
SpringBoot使用OkHttp完成高效网络请求详解

SpringBoot使用OkHttp完成高效网络请求详解

《SpringBoot使用OkHttp完成高效网络请求详解》OkHttp是一个高效的HTTP客户端,支持同步和异步请求,且具备自动处理cookie、缓存和连接池等高级功能,下面我们来看看SpringB... 目录一、OkHttp 简介二、在 Spring Boot 中集成 OkHttp三、封装 OkHttp
阅读更多...
Linux系统之主机网络配置方式

Linux系统之主机网络配置方式

《Linux系统之主机网络配置方式》：本文主要介绍Linux系统之主机网络配置方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、查看主机的网络参数1、查看主机名2、查看IP地址3、查看网关4、查看DNS二、配置网卡1、修改网卡配置文件2、nmcli工具【通用
阅读更多...
使用Python高效获取网络数据的操作指南

使用Python高效获取网络数据的操作指南

《使用Python高效获取网络数据的操作指南》网络爬虫是一种自动化程序,用于访问和提取网站上的数据,Python是进行网络爬虫开发的理想语言,拥有丰富的库和工具,使得编写和维护爬虫变得简单高效,本文将... 目录网络爬虫的基本概念常用库介绍安装库Requests和BeautifulSoup爬虫开发发送请求解
阅读更多...
如何通过海康威视设备网络SDK进行Java二次开发摄像头车牌识别详解

如何通过海康威视设备网络SDK进行Java二次开发摄像头车牌识别详解

《如何通过海康威视设备网络SDK进行Java二次开发摄像头车牌识别详解》：本文主要介绍如何通过海康威视设备网络SDK进行Java二次开发摄像头车牌识别的相关资料,描述了如何使用海康威视设备网络SD... 目录前言开发流程问题和解决方案dll库加载不到的问题老旧版本sdk不兼容的问题关键实现流程总结前言作为
阅读更多...
SSID究竟是什么? WiFi网络名称及工作方式解析

SSID究竟是什么? WiFi网络名称及工作方式解析

《SSID究竟是什么?WiFi网络名称及工作方式解析》SID可以看作是无线网络的名称，类似于有线网络中的网络名称或者路由器的名称,在无线网络中，设备通过SSID来识别和连接到特定的无线网络... 当提到 Wi-Fi 网络时，就避不开「SSID」这个术语。简单来说，SSID 就是 Wi-Fi 网络的名称。比如
阅读更多...
Java实现任务管理器性能网络监控数据的方法详解

Java实现任务管理器性能网络监控数据的方法详解

《Java实现任务管理器性能网络监控数据的方法详解》在现代操作系统中,任务管理器是一个非常重要的工具,用于监控和管理计算机的运行状态,包括CPU使用率、内存占用等,对于开发者和系统管理员来说,了解这些... 目录引言一、背景知识二、准备工作1. Maven依赖2. Gradle依赖三、代码实现四、代码详解五
阅读更多...
Linux 网络编程 --- 应用层

Linux 网络编程 --- 应用层

一、自定义协议和序列化反序列化 代码： 序列化反序列化实现网络版本计算器 二、HTTP协议 1、谈两个简单的预备知识 https://www.baidu.com/ --- 域名 --- 域名解析 --- IP地址 http的端口号为80端口，https的端口号为443 url为统一资源定位符。CSDNhttps://mp.csdn.net/mp_blog/creation/editor
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2