考虑如下问题:
一个牧场由R*C个点组成。牧场内有若干条运输通道,通道流量上限是Ci,连接水平或者垂直相邻的的点。(1,1)内有很多干草,Farmer John希望将干草运送到点(R,C)。问最大流量是多少。1<R,C<=200。
一种直观的解法:
将每个站点看成点,相邻的点之间有边,流量上限为Ci。将(1,1)作为源,(R,C)作为汇,求最大流即可。
是否可行?
上述解法,点数最多为40000,边数最大为80000。用最大流sap求解复杂度为(n*n*m),显然不合理。
分析:
题目给出的是一个平面图,并且s和t都在图中无边界面的边界上。在这里,我们称之为S-T平面图。同时利用对偶图(面f-->点f*,边属于两个面f1、f2,有点(f1*,f2*))和原图的关系,转化为最短路径求解。
具体步骤:
首先连一条边(s,t),它将无边界面分解为2个面。求该图的对偶图G*,设无边界面为点t*,附加面为点s*。删去边(s*,t*)。这样,s*到t*的任意一条路径就对应了原图的一个割,显然,最短路径即为最小割。
例:HDU3870
题意:裸体。给一个n*n的格子,求从(1,1)到(n,n)的最大流。
解:同上。
/*
S-T平面图最小割转最短路径
建模:
1.在原图中添加一条从s到t的边,得到一个附加面,变为图G。
2.求图G的对偶图G*:
G的面i-->G*的点i,G的一条边若属于两个平面i,j,G*中连边(i,j,w)。另附加面为点s*,无界面为t*。
(G和G*的关系:面数=点数,点数=面数,边数=边数)
3.s*到t*的任意一条路径对应原图的一个割。求最短路径即可。
平面图相关知识:面数 = 边数-点数+2。
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxv = 400*400+10; //原图中最大的面数 = 2*n*(n-1)-n*n+2=(n-1)^2 + 1。
int mx[405][405];
struct Edge
{
int to;
int w;
int next;
}e[6*maxv];
int head[maxv],edgeNum;
bool vis[maxv];
int dis[maxv];
void addEdge(int from, int to, int w)
{
e[edgeNum].to = to;
e[edgeNum].w = w;
e[edgeNum].next = head[from];
head[from] = edgeNum++;
}
int spfa(int start, int end)
{
int i;
queue<int> que;
memset(vis,0,sizeof(vis));
for(i = 0; i <= end; i++)
dis[i] = INF;
dis[start] = 0;
vis[start] = true;
que.push(start);
while(!que.empty())
{
int now = que.front();
que.pop();
vis[now] = false;
for(i = head[now]; i != -1; i = e[i].next)
{
int to = e[i].to;
if(dis[now] + e[i].w < dis[to])
{
dis[to] = dis[now] + e[i].w;
if(!vis[to])
{
vis[to] = true;
que.push(to);
}
}
}
}
return dis[end];
}
int main()
{
int i,j;
int t;
int n;
int now,right,down;
scanf("%d",&t);
while(t--)
{
edgeNum = 0;
memset(head,-1,sizeof(head));
scanf("%d",&n);
for(i = 1; i <= n; i++)
for(j = 1; j <= n; j++)
scanf("%d",&mx[i][j]);
int start = 0;
int end = (n-1)*(n-1)+1;
for(i = 1; i < n; i++)
{
for(j = 1; j < n; j++)
{
now = (i-1)*(n-1)+j;
right = now + 1;
down = now + n-1;
if(j < n-1)
{
addEdge(right,now,mx[i][j+1]);
addEdge(now,right,mx[i][j+1]);
}
if(i < n-1)
{
addEdge(now,down,mx[i+1][j]);
addEdge(down,now,mx[i+1][j]);
}
}
}
for(j = 1; j < n; j++)
{
addEdge(start,j,mx[1][j]);
addEdge((n-2)*(n-1)+j,end,mx[n][j]);
}
for(i = 1; i < n; i++)
{
addEdge(start,i*(n-1),mx[i][n]);
addEdge((i-1)*(n-1)+1,end,mx[i][1]);
}
printf("%d\n",spfa(start,end));
}
return 0;
}
- 大小: 47 KB
分享到:
相关推荐
跳舞蝇 从一道题目的解法试谈网络流的构造与算法 平面图在信息学中的应用 平面嵌入 生成树的计数及其应用 由对称性解2-SAT问题 ...最短路算法及其应用 数与图的完美结合—浅析差分约束系统 数据关系的简化
+ [最短路](#最短路) + [欧拉路](#欧拉路) + [差分约束系统](#差分约束系统) + [平面图](#平面图) + [2-SAT](#2-sat) + [最小生成树](#最小生成树) + [二分图](#二分图) + [Voronoi图](#voronoi图) + [偶图...
- **割平面法**:利用割平面技术逐步逼近整数解。 - **隐枚举法**:在可行域内搜索所有可能的整数解。 - **指派问题**:特定类型的整数规划问题及其求解方法。 - **图论**: - **基本概念**:图的基本元素和术语...
本文将深入探讨一个基于DSP的最小系统板,包括其原理图设计与PCB布局,以TI公司的TMS320C2812 DSP为例,结合提供的文件"2812.PCBDOC"、"DSP2812.PRJPCB"和"2812.SCHDOC"进行解析。 一、DSP最小系统构成 一个基本的...
"ATMega8最小系统"是指在保证ATMega8正常工作所需的最基本组件构成的电路,这些组件通常包括电源、时钟、复位电路和编程接口。 一、电源部分 ATMega8的工作电压范围为1.8V到5.5V,因此最小系统中必须提供稳定可靠的...
- **割平面法的基本原理**:理解割平面法的基本思想及其应用。 - **分支定界法的基本原理**:掌握分支定界法的基本思想和步骤。 - **匈牙利法的基本原理**:理解匈牙利法的基本原理及其在求解指派问题中的应用。 - *...
- **最小割最大流定理**:最大流等于最小割的容量。 - **最小费用最大流算法**:同时考虑流量和费用,找到最优解。 #### 计算几何 - **平面解几及其应用**:涉及点、线、多边形的操作。 - **向量**:向量的基本运算...
- **最短路问题的求解与应用**:介绍最短路径问题的求解算法及其应用场景。 - **最大流问题的建模、求解与应用**:提供最大流问题的建模方法及其求解算法。 - **最小费用最大流问题的求解与应用**:探讨最小费用最大...
在布局和设计时,应当考虑到PW5410A由于高开关频率而产生的高瞬态电流,为了确保性能和正确的调节,建议使用真正的接地平面,并与所有电容器作短连接。此外,根据芯片手册,应按照典型应用电路图进行设计,并关注PIN...
* 1423 魔王 bug 的 2 色定理:构图求网络的最小割。 * 1173 Reliable Nets:无向图求最小的二连通子图。(数据小可以搜索)。 * 1192 Guardian of Decency:求最大独立集,比较特殊可以转二分匹配做。 图论 * ...
- **传输和转换电能**:通过电路将电能从电源传输到负载,并可能在传输过程中转换为其他形式的能量。 - **传递和处理电信号**:电路不仅能传输电能,还能传递电信号并对其进行处理,如放大、滤波等。 - **激励与...
- 考虑制造过程中的限制条件,如最小线宽、最小间隙、过孔大小等; - 确保设计符合装配要求,如元件的贴装精度、高度限制等。 3. **热管理** - 通过合理布局和散热设计,确保高功率元件的温度控制; - 使用散热...
10. **网络流问题**:包括网络流模型与线性规划的关系,最大流最小割定理等。 四、组合数学与计算几何 1. **组合数学**:利用逼近、递推和动态规划解决组合问题。 2. **概率问题**:应用Polya定理处理概率计算。 ...
2. **分层图最短路**: - 对于分层图的最短路径问题,可以使用动态规划或者线性规划的方法解决。面试中提到的可能是指广义表或树的层次遍历。 3. **内存中的堆区与栈区**: - 栈区主要存放函数调用时的局部变量,...
与传统的平面结构相比,沟槽技术能够在减小芯片尺寸的同时保持或提升性能。 ### 标签解析:“mosfet vbsemi” “mosfet”标签表明这是一种MOSFET器件。“vbsemi”则可能是指生产该器件的公司VBsemi。 ### 部分...
- **设置设计规则**:设计规则控制了PCB布局的各种约束,如最小线宽、线间距、过孔大小等,以确保设计的电气安全性和可制造性。 - **设置栅格**:栅格设置对于精确放置元件至关重要,它决定了在PCB上移动或定位...
两者之间的转换只需将复平面旋转180度。导纳圆图同样包含等电导圆和等电纳圆,为处理并联电路提供便利。 4. **YZ-Smith chart** YZ-Smith chart将阻抗圆图和导纳圆图结合在一个坐标系统中,这样无论处理串联还是...
- **4.2.6 设置间距约束规则**:定义不同导体之间的最小间距,避免短路等问题。 - **4.2.7 设置相同网络间距规则**:当多个导体属于同一网络时,设置其间的最小间距。 **4.3 布线** - **4.3.1 手工拉线**:手动...
STM32通常需要3.3V或5V电源,需要一个适当的稳压器将其转换为MCU所需的电压。 3. **复位电路**:确保MCU在启动或异常情况后能正确重置。可以是简单的上拉电阻和按钮,也可以是带电源监控的复位IC。 4. **晶振**:...