当前位置: 首页 > news >正文

叠爱心(love.*)

叠爱心(love.*)

题目背景

在柯中热烈的校庆闭幕式上,校长张老大首先做了简短而深刻的讲话,按照此进程,很快就可以放学回家了。然而,不幸降临了。书记 92 同志上台开始了他那代表性的冗长而无味的讲话:“下面,我讲 \(3\) 句话,@#%@#¥#&%#&×!@#¥~!@#¥%……”。在 \(92\) 同志的

狂轰滥炸下,同学们纷纷感到昏昏欲睡。LZT 坐在台下,对这种浪费生命的行为感到无比地愤慨。于是他环视全场,突然眼前一亮,心中萌发出一个对他的人生具有重大意义的念头……

题目描述

台下的童鞋们坐成一个 \(m\)\(n\) 列的方阵,由于平时太过不遵守纪律,LZT 非常悲剧地被学部的副校长大人安排在了方阵的左上角 \((1,1)\),而他所倾心的乖女孩 FYT 童鞋,则被安排在方阵的右下角 \((m,n)\)。LZT 终于体味到了“溯洄从之,道阻且长”的感觉。于是,他决定利用这一段差点被 \(92\) 同志荒废的时间来叠爱心向 FYT 童鞋表达爱慕之情。

由于 LZT 和 FYT 他们两个之间人海茫茫,LZT 叠的爱心不得不通过方阵中的童鞋们传递给女孩 FYT,而每个童鞋只能给相邻的同学传递爱心。LZT 很快就叠好了无数的爱心,但他突然想到了一个非常严峻的问题:虽然两个童鞋间爱心的传递是双向的,但由于两个童鞋间的友好程度不同,他们之间能够传递的爱心数量是有限的。这样, LZT 所叠的爱心就不能源源不断地送给 FYT 了。LZT 由于这个无法避免的事实瞬时从亢奋状态跌落。而此时 FYT 已经收到了传递出的第一颗爱心。于是她想知道,她最终能够收到多少颗 LZT 叠的爱心。

由于 LZT 实在太弱了,而且还沉浸在不能用无限的爱心来表达深沉的爱意的巨大悲伤中不可自拔,所以他暂时无法计算出 FYT 想知道的问题答案。他举目四望,却发现最强的 zyc 神犇坐在方阵的右上角而无法联系到。由于这个问题关系到 LZT 后半生的幸福,他只能求助于你,希望尽快得到 FYT 想要的这个答案,这样就可以得到 FYT 的倾心。事成之后,作为酬谢,LZT 会付给你 \(10^{100000} \mod 10\) 的 RMB。

输入描述

第一行两个整数 \(m\)\(n\)

接下来 \(m\) 行,每行有 \(n-1\) 个非负整数,第 \(i+1\) 行的第 \(j\) 个数表示坐在 \((i,j)\)\((i,j+1)\) 位置的同学之间能传递爱心的最大数量。

再接下来 \(m-1\) 行,每行有 \(n\) 个非负整数,第 \(i+m+1\) 行的第 \(j\) 个数表示坐在 \((i,j)\)\((i+1,j)\) 位置的同学之间能传递爱心的最大数量。

输出描述

仅有一行,表示 FYT 最多能收到的爱心数量。

输入输出样例 #1

输入样例 #1

2 2
2
4
1 3

输出样例 #1

4

说明/提示

抽象化题面

给出一个 \(m\)\(n\) 列的网格图,每条格边都有一个容量,求从 \((1,1)\)\((m,n)\) 的最大流。

数据范围

  • 对于 \(20\)% 的数据,\(n,m \leq 10\)

  • 对于 \(40\)% 的数据,\(n,m \leq 200\)

  • 对于 \(100\)% 的数据,\(n,m \leq 1000\)


解题报告

没见过的套路......

首先想到裸跑 Dinic 的方法,但是只有 \(40\text{pts}\)

看了题解才知道,这是一个经典的平面图最小割转对偶图最短路

解释一下概念:

  • 平面图:一个图可以画在平面上,使得边之间没有交叉。网格图是平面图的一个典型例子。
  • 对偶图:对于一个平面图,我们可以构造其对偶图。原图的每个面(包括外部面)对应对偶图的一个节点。原图的每条边对应对偶图的一条边,连接两个相邻的面。

怎么把平面图改成对偶图?具体方法为:

  • 把原平面图中各边所围成的面都映射为对偶图的一个点,注意:也包括最外部的面。
  • 对于原平面图中每条边,把这条边所隔开的两个面相连,作为对偶图的一条边。

怎么转化?

首先人为的把外部面按 \((1,1)-(m,n)\) 一线割成两个面,作为对偶图的起始点 \(s\)\(t\),以原平面图的边的容量作为对偶图对应边的边权,然后就是标准的平面图改成对偶图。

按照平面图改成对偶图的过程,对偶图的每一条边都把原平面图中的对应的一条边割掉了。

那么从 \(s\)\(t\) 的任意一条通路都是原平面图的一个割集(把原平面图割成了两个不连通的图),同时原平面图的边的容量作为对偶图对应边的边权,那么对偶图中从 \(s\)\(t\) 的最短路就是原平面图的最小割,也就是原平面图的最大流。

这题就解决了,代码如下:

#include<bits/stdc++.h>
using namespace std;
const int INF=0x3f3f3f3f;
const int N=1001;#define ckmax(x,y) ( x=max(x,y) )
#define ckmin(x,y) ( x=min(x,y) )inline int read()
{int f=1,x=0; char ch=getchar();while(!isdigit(ch)) { if(ch=='-') f=-1; ch=getchar(); }while(isdigit(ch))  { x=x*10+ch-'0';    ch=getchar(); }return f*x;
}int m,n,s,t;
int c[N][N][2];
int pos[N][N],idx;#define pos(x,y) pos[x][y]struct edge
{int next;int to,dis;
}e[N*N<<1];
int head[N*N],tot;inline void add_edge(int u,int v,int w)
{e[++tot]=(edge){ head[u],v,w };head[u]=tot;e[++tot]=(edge){ head[v],u,w };head[v]=tot;
}struct node
{int pos,dis;bool operator < ( const node &x )const{ return x.dis <dis; }
};
int dis[N*N];
bool vis[N*N];void Dijkstra(int s)
{memset(dis,0x3f,sizeof(dis));memset(vis,false,sizeof(vis));priority_queue<node> q;q.push( (node){ s,dis[s]=0 } );while(!q.empty()){int u=q.top().pos;q.pop();if(vis[u]) continue;vis[u]=true;for(int i=head[u];i;i=e[i].next){int v=e[i].to;if(dis[v]>dis[u]+e[i].dis){dis[v]=dis[u]+e[i].dis;if(!vis[v]) q.push( (node){ v,dis[v] } );}}}
}signed main()
{freopen("love.in","r",stdin);freopen("love.out","w",stdout);m=read(),n=read();for(int i=1;i<=m;i++)for(int j=1;j<n;j++)c[i][j][0]=read();for(int i=1;i<m;i++)for(int j=1;j<=n;j++)c[i][j][1]=read();for(int i=1;i<=m;i++)for(int j=1;j<=n;j++)pos[i][j]=++idx;s=++idx,t=++idx;for(int j=1;j<n;j++){add_edge(s,pos(1,j),c[1][j][0]);add_edge(pos(m-1,j),t,c[m][j][0]);}for(int i=2;i<m;i++)for(int j=1;j<n;j++)add_edge(pos(i-1,j),pos(i,j),c[i][j][0]);for(int i=1;i<m;i++){add_edge(t,pos(i,1),c[i][1][1]);add_edge(pos(i,n-1),s,c[i][n][1]);}for(int i=1;i<m;i++)for(int j=2;j<n;j++)add_edge(pos(i,j-1),pos(i,j),c[i][j][1]);Dijkstra(s);printf("%d",dis[t]);return 0;
}
http://www.hskmm.com/?act=detail&tid=24112

相关文章:

  • 从单层感知机到多层感知机(MLP)
  • 机电公司管理小工具|基于微信小应用的机电公司管理小程序设计与实现(源码+数据库+文档)
  • 【性质】CF689D Friends and Subsequences
  • Arduino+数码管 = 量电压 | A+B problem | alphabet
  • 详细介绍:【数据库知识】TxSQL 主从数据库同步底层原理深度解析
  • 2025.10.3 NOIP 模拟赛
  • Python 之操作excel
  • 国家生物信息数据下载
  • linux jenkins服务启动异常等,排查是否日志磁盘空间满 du df命令
  • 详细介绍:LeetCode 391 完美矩形
  • [NOI2025] 集合 题解
  • bi数据报表发送周期,周报和月报获取日期时间
  • 技术Leader的1-3-5沟通法则:向上管理的艺术 - 指南
  • cannot resolve method add in T 及 T 泛型类型生成Excel文件,区别是数据Model不同
  • 测试环境elasticSearch数据泄露排查
  • 深入解析:Spring boot中 限制 Mybatis SQL日志的大字段输出
  • 【AI时代速通QT】第九节:揭秘Qt编译全流程-从.pro材料到可执行程序
  • 考试心得5
  • javascript高级 - Ref
  • Solar9月赛wp - 场
  • 实用指南:深度解析Sora2:技术革命与创意产业的未来图景
  • 自动化安全工具的双刃剑:红队演练揭示安全响应盲区
  • Elastic Search 安装部署最全教程(Docker)
  • 详细介绍:图像分割:PyTorch从零开始实现SegFormer语义分割
  • 深入解析:Playwright同步、异步、并行、串行执行效率比较
  • 2025十一集训——Day2模拟赛
  • 2025十一集训——Day模拟赛
  • Qt纯代码实现智能安防集中管理平台/楼宇对讲管理系统/门禁管理/视频监控
  • 汉文博士词典库源文件已在 github 开放
  • 读人形机器人30未来20年