Soldier and Traveling

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

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

相关帖子

欢迎来到这里!

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

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

推荐标签 标签

  • CAP

    CAP 指的是在一个分布式系统中, Consistency(一致性)、 Availability(可用性)、Partition tolerance(分区容错性),三者不可兼得。

    12 引用 • 5 回帖 • 623 关注
  • 叶归
    5 引用 • 14 回帖 • 5 关注
  • Q&A

    提问之前请先看《提问的智慧》,好的问题比好的答案更有价值。

    9095 引用 • 41350 回帖 • 125 关注
  • ZooKeeper

    ZooKeeper 是一个分布式的,开放源码的分布式应用程序协调服务,是 Google 的 Chubby 一个开源的实现,是 Hadoop 和 HBase 的重要组件。它是一个为分布式应用提供一致性服务的软件,提供的功能包括:配置维护、域名服务、分布式同步、组服务等。

    59 引用 • 29 回帖 • 8 关注
  • 域名

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

    43 引用 • 208 回帖 • 3 关注
  • 资讯

    资讯是用户因为及时地获得它并利用它而能够在相对短的时间内给自己带来价值的信息,资讯有时效性和地域性。

    56 引用 • 85 回帖
  • Laravel

    Laravel 是一套简洁、优雅的 PHP Web 开发框架。它采用 MVC 设计,是一款崇尚开发效率的全栈框架。

    20 引用 • 23 回帖 • 737 关注
  • 服务器

    服务器,也称伺服器,是提供计算服务的设备。由于服务器需要响应服务请求,并进行处理,因此一般来说服务器应具备承担服务并且保障服务的能力。

    125 引用 • 585 回帖
  • 运维

    互联网运维工作,以服务为中心,以稳定、安全、高效为三个基本点,确保公司的互联网业务能够 7×24 小时为用户提供高质量的服务。

    150 引用 • 257 回帖 • 2 关注
  • 架构

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

    143 引用 • 442 回帖
  • webpack

    webpack 是一个用于前端开发的模块加载器和打包工具,它能把各种资源,例如 JS、CSS(less/sass)、图片等都作为模块来使用和处理。

    41 引用 • 130 回帖 • 253 关注
  • Webswing

    Webswing 是一个能将任何 Swing 应用通过纯 HTML5 运行在浏览器中的 Web 服务器,详细介绍请看 将 Java Swing 应用变成 Web 应用

    1 引用 • 15 回帖 • 633 关注
  • V2Ray
    1 引用 • 15 回帖
  • Eclipse

    Eclipse 是一个开放源代码的、基于 Java 的可扩展开发平台。就其本身而言,它只是一个框架和一组服务,用于通过插件组件构建开发环境。

    75 引用 • 258 回帖 • 634 关注
  • Windows

    Microsoft Windows 是美国微软公司研发的一套操作系统,它问世于 1985 年,起初仅仅是 Microsoft-DOS 模拟环境,后续的系统版本由于微软不断的更新升级,不但易用,也慢慢的成为家家户户人们最喜爱的操作系统。

    224 引用 • 475 回帖
  • Oracle

    Oracle(甲骨文)公司,全称甲骨文股份有限公司(甲骨文软件系统有限公司),是全球最大的企业级软件公司,总部位于美国加利福尼亚州的红木滩。1989 年正式进入中国市场。2013 年,甲骨文已超越 IBM,成为继 Microsoft 后全球第二大软件公司。

    107 引用 • 127 回帖 • 364 关注
  • Follow
    4 引用 • 12 回帖 • 2 关注
  • Hprose

    Hprose 是一款先进的轻量级、跨语言、跨平台、无侵入式、高性能动态远程对象调用引擎库。它不仅简单易用,而且功能强大。你无需专门学习,只需看上几眼,就能用它轻松构建分布式应用系统。

    9 引用 • 17 回帖 • 616 关注
  • PHP

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

    179 引用 • 407 回帖 • 485 关注
  • JWT

    JWT(JSON Web Token)是一种用于双方之间传递信息的简洁的、安全的表述性声明规范。JWT 作为一个开放的标准(RFC 7519),定义了一种简洁的,自包含的方法用于通信双方之间以 JSON 的形式安全的传递信息。

    20 引用 • 15 回帖 • 16 关注
  • QQ

    1999 年 2 月腾讯正式推出“腾讯 QQ”,在线用户由 1999 年的 2 人(马化腾和张志东)到现在已经发展到上亿用户了,在线人数超过一亿,是目前使用最广泛的聊天软件之一。

    45 引用 • 557 回帖
  • Markdown

    Markdown 是一种轻量级标记语言,用户可使用纯文本编辑器来排版文档,最终通过 Markdown 引擎将文档转换为所需格式(比如 HTML、PDF 等)。

    169 引用 • 1526 回帖
  • 支付宝

    支付宝是全球领先的独立第三方支付平台,致力于为广大用户提供安全快速的电子支付/网上支付/安全支付/手机支付体验,及转账收款/水电煤缴费/信用卡还款/AA 收款等生活服务应用。

    29 引用 • 347 回帖
  • 小薇

    小薇是一个用 Java 写的 QQ 聊天机器人 Web 服务,可以用于社群互动。

    由于 Smart QQ 从 2019 年 1 月 1 日起停止服务,所以该项目也已经停止维护了!

    34 引用 • 467 回帖 • 754 关注
  • FreeMarker

    FreeMarker 是一款好用且功能强大的 Java 模版引擎。

    23 引用 • 20 回帖 • 462 关注
  • InfluxDB

    InfluxDB 是一个开源的没有外部依赖的时间序列数据库。适用于记录度量,事件及实时分析。

    2 引用 • 90 关注
  • 周末

    星期六到星期天晚,实行五天工作制后,指每周的最后两天。再过几年可能就是三天了。

    14 引用 • 297 回帖