Soldier and Traveling

本贴最后更新于 2145 天前,其中的信息可能已经斗转星移

传送门
题目要求士兵只能从所在城市移动一次或不移动
所以可以考虑从源点到汇点的网络流
将每个点 x 拆成入点 x 和出点 x+n,他们之间流量为 inf
源点为 0,汇点为 2n+1
源点到入点的流量限制为 a[i]
出点到汇点的流量限制为 b[i]
对于每一条边 x 和 y
x 的入点到 y 的出点建边,流量为 inf
y 的入点到 x 的出点建边,流量为 inf
对于样例一构图:
Alt
当 mxflow=sum a[i]=sum b[i]时
说明满足题意输出 yes
否则输出 no
对于士兵的流动,判断一下每条边流了多少流量即可

程序:

//by xxj
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define ll long long
#define pii pair<int,int>
#define lowbit(x) x&-x
using namespace std;
const int inf=1e9+7;
const double eps=1e-10;
const ll linf=1e18+7;
const ll hh=523;
//const int mod=;
const int maxn=207;
struct edge{
	int des,cap,rev;
};
vector<edge> G[maxn];
bool visited[maxn];
int a[maxn],b[maxn];
int ans[maxn][maxn];
int n,m;
int dfs(int s,int t,int f){
	visited[s]=true;
	if (s==t){
		return f;
	}
	for (int i=0;i<G[s].size();i++){
		edge e=G[s][i];
		if (!visited[e.des] && e.cap>0){
			int d=dfs(e.des,t,min(f,e.cap));
			if (d>0){
				G[s][i].cap-=d;
				G[e.des][e.rev].cap+=d;
				return d;
			}
		}
	}
	return 0;
}
int maxflow(){
	int flows=0;
	while(true){
		memset(visited,false,sizeof(visited));
		int f=dfs(0,2*n+1,inf);
		if (f==0){
			return flows;
		}
		flows+=f;
	}
}
int main(){
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	int x,y;
	scanf("%d%d",&n,&m);
	int suma=0,sumb=0; 
	for (int i=1;i<=n;i++){
		scanf("%d",a+i);
		suma+=a[i]; 
	}
	for (int i=1;i<=n;i++){
		scanf("%d",b+i);
		sumb+=b[i];
	}
	if (suma!=sumb){
		puts("NO");
		return 0;
	}
	for (int i=1;i<=n;i++){
		G[0].push_back((edge){i,a[i],G[i].size()});
		G[i].push_back((edge){0,0,G[0].size()-1});
	}
	for (int i=n+1;i<=2*n;i++){
		G[2*n+1].push_back((edge){i,0,G[i].size()});
		G[i].push_back((edge){2*n+1,b[i-n],G[2*n+1].size()-1});
	}
	for (int i=1;i<=n;i++){
		G[i].push_back((edge){i+n,inf,G[i+n].size()});
		G[i+n].push_back((edge){i,0,G[i].size()-1});
	}
	for (int i=1;i<=m;i++){
		int x,y;
		scanf("%d%d",&x,&y);
		G[x].push_back((edge){y+n,inf,G[y+n].size()});
		G[y+n].push_back((edge){x,0,G[x].size()-1});
		G[y].push_back((edge){x+n,inf,G[x+n].size()});
		G[x+n].push_back((edge){y,0,G[y].size()-1});
	} 
	int mx=maxflow();
	if (mx!=suma){
		puts("NO");
		return 0;
	}
	puts("YES");
	for (int i=1;i<=n;i++){
		for (int j=0;j<G[i].size();j++){
			if (G[i][j].des==0 || G[i][j].des==2*n+1){
				continue;
			}
			ans[i][G[i][j].des-n]=G[G[i][j].des][G[i][j].rev].cap;
		}
	}
	for (int i=1;i<=n;i++){
		printf("%d",ans[i][1]);
		for (int j=2;j<=n;j++){
			printf(" %d",ans[i][j]);
		}
		printf("\n");
	}
	return 0;
}
/*
input:
*/

  • OI
    7 引用 • 8 回帖
  • 网络
    138 引用 • 177 回帖 • 4 关注

相关帖子

欢迎来到这里!

我们正在构建一个小众社区,大家在这里相互信任,以平等 • 自由 • 奔放的价值观进行分享交流。最终,希望大家能够找到与自己志同道合的伙伴,共同成长。

注册 关于
请输入回帖内容 ...

推荐标签 标签

  • RYMCU

    RYMCU 致力于打造一个即严谨又活泼、专业又不失有趣,为数百万人服务的开源嵌入式知识学习交流平台。

    4 引用 • 6 回帖 • 51 关注
  • jQuery

    jQuery 是一套跨浏览器的 JavaScript 库,强化 HTML 与 JavaScript 之间的操作。由 John Resig 在 2006 年 1 月的 BarCamp NYC 上释出第一个版本。全球约有 28% 的网站使用 jQuery,是非常受欢迎的 JavaScript 库。

    63 引用 • 134 回帖 • 724 关注
  • 新人

    让我们欢迎这对新人。哦,不好意思说错了,让我们欢迎这位新人!
    新手上路,请谨慎驾驶!

    52 引用 • 228 回帖 • 1 关注
  • 开源

    Open Source, Open Mind, Open Sight, Open Future!

    408 引用 • 3574 回帖
  • RESTful

    一种软件架构设计风格而不是标准,提供了一组设计原则和约束条件,主要用于客户端和服务器交互类的软件。基于这个风格设计的软件可以更简洁,更有层次,更易于实现缓存等机制。

    30 引用 • 114 回帖 • 2 关注
  • abitmean

    有点意思就行了

    29 关注
  • C

    C 语言是一门通用计算机编程语言,应用广泛。C 语言的设计目标是提供一种能以简易的方式编译、处理低级存储器、产生少量的机器码以及不需要任何运行环境支持便能运行的编程语言。

    85 引用 • 165 回帖 • 2 关注
  • NGINX

    NGINX 是一个高性能的 HTTP 和反向代理服务器,也是一个 IMAP/POP3/SMTP 代理服务器。 NGINX 是由 Igor Sysoev 为俄罗斯访问量第二的 Rambler.ru 站点开发的,第一个公开版本 0.1.0 发布于 2004 年 10 月 4 日。

    311 引用 • 546 回帖
  • iOS

    iOS 是由苹果公司开发的移动操作系统,最早于 2007 年 1 月 9 日的 Macworld 大会上公布这个系统,最初是设计给 iPhone 使用的,后来陆续套用到 iPod touch、iPad 以及 Apple TV 等产品上。iOS 与苹果的 Mac OS X 操作系统一样,属于类 Unix 的商业操作系统。

    85 引用 • 139 回帖 • 1 关注
  • PHP

    PHP(Hypertext Preprocessor)是一种开源脚本语言。语法吸收了 C 语言、 Java 和 Perl 的特点,主要适用于 Web 开发领域,据说是世界上最好的编程语言。

    179 引用 • 407 回帖 • 488 关注
  • GitLab

    GitLab 是利用 Ruby 一个开源的版本管理系统,实现一个自托管的 Git 项目仓库,可通过 Web 界面操作公开或私有项目。

    46 引用 • 72 回帖
  • VirtualBox

    VirtualBox 是一款开源虚拟机软件,最早由德国 Innotek 公司开发,由 Sun Microsystems 公司出品的软件,使用 Qt 编写,在 Sun 被 Oracle 收购后正式更名成 Oracle VM VirtualBox。

    10 引用 • 2 回帖 • 6 关注
  • TextBundle

    TextBundle 文件格式旨在应用程序之间交换 Markdown 或 Fountain 之类的纯文本文件时,提供更无缝的用户体验。

    1 引用 • 2 回帖 • 47 关注
  • DNSPod

    DNSPod 建立于 2006 年 3 月份,是一款免费智能 DNS 产品。 DNSPod 可以为同时有电信、网通、教育网服务器的网站提供智能的解析,让电信用户访问电信的服务器,网通的用户访问网通的服务器,教育网的用户访问教育网的服务器,达到互联互通的效果。

    6 引用 • 26 回帖 • 510 关注
  • 大数据

    大数据(big data)是指无法在一定时间范围内用常规软件工具进行捕捉、管理和处理的数据集合,是需要新处理模式才能具有更强的决策力、洞察发现力和流程优化能力的海量、高增长率和多样化的信息资产。

    93 引用 • 113 回帖
  • TensorFlow

    TensorFlow 是一个采用数据流图(data flow graphs),用于数值计算的开源软件库。节点(Nodes)在图中表示数学操作,图中的线(edges)则表示在节点间相互联系的多维数据数组,即张量(tensor)。

    20 引用 • 19 回帖
  • Sym

    Sym 是一款用 Java 实现的现代化社区(论坛/BBS/社交网络/博客)系统平台。

    下一代的社区系统,为未来而构建

    524 引用 • 4601 回帖 • 700 关注
  • Bug

    Bug 本意是指臭虫、缺陷、损坏、犯贫、窃听器、小虫等。现在人们把在程序中一些缺陷或问题统称为 bug(漏洞)。

    75 引用 • 1737 回帖 • 5 关注
  • 职场

    找到自己的位置,萌新烦恼少。

    127 引用 • 1705 回帖 • 1 关注
  • HBase

    HBase 是一个分布式的、面向列的开源数据库,该技术来源于 Fay Chang 所撰写的 Google 论文 “Bigtable:一个结构化数据的分布式存储系统”。就像 Bigtable 利用了 Google 文件系统所提供的分布式数据存储一样,HBase 在 Hadoop 之上提供了类似于 Bigtable 的能力。

    17 引用 • 6 回帖 • 73 关注
  • Vim

    Vim 是类 UNIX 系统文本编辑器 Vi 的加强版本,加入了更多特性来帮助编辑源代码。Vim 的部分增强功能包括文件比较(vimdiff)、语法高亮、全面的帮助系统、本地脚本(Vimscript)和便于选择的可视化模式。

    29 引用 • 66 回帖
  • ActiveMQ

    ActiveMQ 是 Apache 旗下的一款开源消息总线系统,它完整实现了 JMS 规范,是一个企业级的消息中间件。

    19 引用 • 13 回帖 • 670 关注
  • 导航

    各种网址链接、内容导航。

    40 引用 • 173 回帖
  • 服务

    提供一个服务绝不仅仅是简单的把硬件和软件累加在一起,它包括了服务的可靠性、服务的标准化、以及对服务的监控、维护、技术支持等。

    41 引用 • 24 回帖 • 2 关注
  • 锤子科技

    锤子科技(Smartisan)成立于 2012 年 5 月,是一家制造移动互联网终端设备的公司,公司的使命是用完美主义的工匠精神,打造用户体验一流的数码消费类产品(智能手机为主),改善人们的生活质量。

    4 引用 • 31 回帖 • 4 关注
  • Dubbo

    Dubbo 是一个分布式服务框架,致力于提供高性能和透明化的 RPC 远程服务调用方案,是 [阿里巴巴] SOA 服务化治理方案的核心框架,每天为 2,000+ 个服务提供 3,000,000,000+ 次访问量支持,并被广泛应用于阿里巴巴集团的各成员站点。

    60 引用 • 82 回帖 • 595 关注
  • Hexo

    Hexo 是一款快速、简洁且高效的博客框架,使用 Node.js 编写。

    21 引用 • 140 回帖 • 1 关注