Soldier and Traveling

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

传送门
题目要求士兵只能从所在城市移动一次或不移动
所以可以考虑从源点到汇点的网络流
将每个点 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 关注

相关帖子

欢迎来到这里!

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

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

推荐标签 标签

  • Node.js

    Node.js 是一个基于 Chrome JavaScript 运行时建立的平台, 用于方便地搭建响应速度快、易于扩展的网络应用。Node.js 使用事件驱动, 非阻塞 I/O 模型而得以轻量和高效。

    139 引用 • 269 回帖 • 1 关注
  • 30Seconds

    📙 前端知识精选集,包含 HTML、CSS、JavaScript、React、Node、安全等方面,每天仅需 30 秒。

    • 精选常见面试题,帮助您准备下一次面试
    • 精选常见交互,帮助您拥有简洁酷炫的站点
    • 精选有用的 React 片段,帮助你获取最佳实践
    • 精选常见代码集,帮助您提高打码效率
    • 整理前端界的最新资讯,邀您一同探索新世界
    488 引用 • 384 回帖 • 5 关注
  • 域名

    域名(Domain Name),简称域名、网域,是由一串用点分隔的名字组成的 Internet 上某一台计算机或计算机组的名称,用于在数据传输时标识计算机的电子方位(有时也指地理位置)。

    43 引用 • 208 回帖 • 3 关注
  • H2

    H2 是一个开源的嵌入式数据库引擎,采用 Java 语言编写,不受平台的限制,同时 H2 提供了一个十分方便的 web 控制台用于操作和管理数据库内容。H2 还提供兼容模式,可以兼容一些主流的数据库,因此采用 H2 作为开发期的数据库非常方便。

    11 引用 • 54 回帖 • 659 关注
  • GAE

    Google App Engine(GAE)是 Google 管理的数据中心中用于 WEB 应用程序的开发和托管的平台。2008 年 4 月 发布第一个测试版本。目前支持 Python、Java 和 Go 开发部署。全球已有数十万的开发者在其上开发了众多的应用。

    14 引用 • 42 回帖 • 801 关注
  • Hibernate

    Hibernate 是一个开放源代码的对象关系映射框架,它对 JDBC 进行了非常轻量级的对象封装,使得 Java 程序员可以随心所欲的使用对象编程思维来操纵数据库。

    39 引用 • 103 回帖 • 717 关注
  • Google

    Google(Google Inc.,NASDAQ:GOOG)是一家美国上市公司(公有股份公司),于 1998 年 9 月 7 日以私有股份公司的形式创立,设计并管理一个互联网搜索引擎。Google 公司的总部称作“Googleplex”,它位于加利福尼亚山景城。Google 目前被公认为是全球规模最大的搜索引擎,它提供了简单易用的免费服务。不作恶(Don't be evil)是谷歌公司的一项非正式的公司口号。

    49 引用 • 192 回帖
  • 阿里巴巴

    阿里巴巴网络技术有限公司(简称:阿里巴巴集团)是以曾担任英语教师的马云为首的 18 人,于 1999 年在中国杭州创立,他们相信互联网能够创造公平的竞争环境,让小企业通过创新与科技扩展业务,并在参与国内或全球市场竞争时处于更有利的位置。

    43 引用 • 221 回帖 • 88 关注
  • Spring

    Spring 是一个开源框架,是于 2003 年兴起的一个轻量级的 Java 开发框架,由 Rod Johnson 在其著作《Expert One-On-One J2EE Development and Design》中阐述的部分理念和原型衍生而来。它是为了解决企业应用开发的复杂性而创建的。框架的主要优势之一就是其分层架构,分层架构允许使用者选择使用哪一个组件,同时为 JavaEE 应用程序开发提供集成的框架。

    943 引用 • 1460 回帖
  • 音乐

    你听到信仰的声音了么?

    61 引用 • 512 回帖
  • 程序员

    程序员是从事程序开发、程序维护的专业人员。

    581 引用 • 3535 回帖
  • 架构

    我们平时所说的“架构”主要是指软件架构,这是有关软件整体结构与组件的抽象描述,用于指导软件系统各个方面的设计。另外还有“业务架构”、“网络架构”、“硬件架构”等细分领域。

    143 引用 • 442 回帖
  • 持续集成

    持续集成(Continuous Integration)是一种软件开发实践,即团队开发成员经常集成他们的工作,通过每个成员每天至少集成一次,也就意味着每天可能会发生多次集成。每次集成都通过自动化的构建(包括编译,发布,自动化测试)来验证,从而尽早地发现集成错误。

    15 引用 • 7 回帖
  • Kotlin

    Kotlin 是一种在 Java 虚拟机上运行的静态类型编程语言,由 JetBrains 设计开发并开源。Kotlin 可以编译成 Java 字节码,也可以编译成 JavaScript,方便在没有 JVM 的设备上运行。在 Google I/O 2017 中,Google 宣布 Kotlin 成为 Android 官方开发语言。

    19 引用 • 33 回帖 • 74 关注
  • 倾城之链
    23 引用 • 66 回帖 • 156 关注
  • Sym

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

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

    524 引用 • 4601 回帖 • 697 关注
  • LaTeX

    LaTeX(音译“拉泰赫”)是一种基于 ΤΕΧ 的排版系统,由美国计算机学家莱斯利·兰伯特(Leslie Lamport)在 20 世纪 80 年代初期开发,利用这种格式,即使使用者没有排版和程序设计的知识也可以充分发挥由 TeX 所提供的强大功能,能在几天,甚至几小时内生成很多具有书籍质量的印刷品。对于生成复杂表格和数学公式,这一点表现得尤为突出。因此它非常适用于生成高印刷质量的科技和数学类文档。

    12 引用 • 54 回帖 • 23 关注
  • 旅游

    希望你我能在旅途中找到人生的下一站。

    93 引用 • 901 回帖
  • Spark

    Spark 是 UC Berkeley AMP lab 所开源的类 Hadoop MapReduce 的通用并行框架。Spark 拥有 Hadoop MapReduce 所具有的优点;但不同于 MapReduce 的是 Job 中间输出结果可以保存在内存中,从而不再需要读写 HDFS,因此 Spark 能更好地适用于数据挖掘与机器学习等需要迭代的 MapReduce 的算法。

    74 引用 • 46 回帖 • 564 关注
  • Ant-Design

    Ant Design 是服务于企业级产品的设计体系,基于确定和自然的设计价值观上的模块化解决方案,让设计者和开发者专注于更好的用户体验。

    17 引用 • 23 回帖 • 3 关注
  • Thymeleaf

    Thymeleaf 是一款用于渲染 XML/XHTML/HTML5 内容的模板引擎。类似 Velocity、 FreeMarker 等,它也可以轻易的与 Spring 等 Web 框架进行集成作为 Web 应用的模板引擎。与其它模板引擎相比,Thymeleaf 最大的特点是能够直接在浏览器中打开并正确显示模板页面,而不需要启动整个 Web 应用。

    11 引用 • 19 回帖 • 380 关注
  • 黑曜石

    黑曜石是一款强大的知识库工具,支持本地 Markdown 文件编辑,支持双向链接和关系图。

    A second brain, for you, forever.

    20 引用 • 193 回帖
  • 开源

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

    409 引用 • 3579 回帖
  • 国际化

    i18n(其来源是英文单词 internationalization 的首末字符 i 和 n,18 为中间的字符数)是“国际化”的简称。对程序来说,国际化是指在不修改代码的情况下,能根据不同语言及地区显示相应的界面。

    8 引用 • 26 回帖 • 5 关注
  • 外包

    有空闲时间是接外包好呢还是学习好呢?

    26 引用 • 232 回帖
  • 安装

    你若安好,便是晴天。

    132 引用 • 1184 回帖 • 2 关注
  • JSON

    JSON (JavaScript Object Notation)是一种轻量级的数据交换格式。易于人类阅读和编写。同时也易于机器解析和生成。

    52 引用 • 190 回帖 • 1 关注