热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

【费用流】【CODEVS】1227方格取数2

【算法】最小费用最大流(费用流)【题解】费用流:http:www.cnblogs.comonioncycp6496532.html本题构图:在有限的k次

【算法】最小费用最大流(费用流)

【题解】

费用流:http://www.cnblogs.com/onioncyc/p/6496532.html 

本题构图:

在有限的k次行走中尽可能多的拿到数字,明显的取舍问题,可以用网络流解决。

一共只有k次行走,因此流量至多为k。

而在起点到终点的所有最大流应该使价值最大化(取得数字最大),因此就可以构图了。

为每个节点x复制一个分点x’,从x向x'连一条容量1,费用-num[x]的边(限制数字只能取一次,代价变成负数就可以跑最小费用)

注意:因为每个点其实可以重复经过,但数字不能重复取,因此再从x向x'连一条容量k(相当于inf),费用0的边。

从x’向右和下连容量k,费用0的边。

S向第一格顶连容量k,费用0的边。

最后一格底向T连容量k,费用0的边。

构图完毕。

本题的核心是满足走k次(最大流)的前提下取的数字尽可能大(费用尽可能小),流只是前提,关键在每个节点那条带费用的边。

费用为负数的边越小当然越能吸引水流过去,最后就能跑出最小费用流。

---

注意数组范围!

spfa的vis只决定进不进队列,不妨碍松弛!

#include
#include

#include

using namespace std;
const int inf=0x3f3f3f3f,maxn=60,maxN=5100;
int n,N,k,p[maxn][maxn],first[maxN],tot=1,d[maxN],q[1010],S,T,ans;
bool vis[maxN];
struct edge{int from,v,flow,cost;}e[30000];
void insert(int u,int v,int flow,int cost)
{tot
++;e[tot].v=v;e[tot].flow=flow;e[tot].cost=cost;e[tot].from=first[u];first[u]=tot;tot++;e[tot].v=u;e[tot].flow=0;e[tot].cost=-cost;e[tot].from=first[v];first[v]=tot;
}
bool spfa()
{memset(d,
0x3f,4*(N&#43;N&#43;2));memset(vis,0,N&#43;N&#43;2);int head&#61;0,tail&#61;1;q[0]&#61;T;vis[T]&#61;1;d[T]&#61;0;while(head!&#61;tail){int x&#61;q[head&#43;&#43;];if(head>&#61;1001)head&#61;0;for(int i&#61;first[x];i;i&#61;e[i].from)if(e[i^1].flow&&d[x]&#43;e[i^1].cost<d[e[i].v]){d[e[i].v]&#61;d[x]&#43;e[i^1].cost;if(!vis[e[i].v]){q[tail&#43;&#43;]&#61;e[i].v;if(tail>&#61;1001)tail&#61;0;vis[e[i].v]&#61;1;}}vis[x]&#61;0;}return d[S]<inf;
}
int dfs(int x,int a)
{vis[x]
&#61;1;if(x&#61;&#61;T||a&#61;&#61;0)return a;int flow&#61;0,f;for(int i&#61;first[x];i;i&#61;e[i].from)if(!vis[e[i].v]&&d[x]&#61;&#61;e[i].cost&#43;d[e[i].v]&&(f&#61;dfs(e[i].v,min(a,e[i].flow)))>0){e[i].flow-&#61;f;e[i^1].flow&#43;&#61;f;ans&#43;&#61;e[i].cost*f;a-&#61;f;flow&#43;&#61;f;if(a&#61;&#61;0)break;}return flow;
}
int main()
{scanf(
"%d%d",&n,&k);N&#61;n*n;S&#61;0,T&#61;N&#43;N&#43;1;for(int i&#61;1;i<&#61;n;i&#43;&#43;){for(int j&#61;1;j<&#61;n;j&#43;&#43;){int x;p[i][j]&#61;(i-1)*n&#43;j;scanf("%d",&x);insert(p[i][j],p[i][j]&#43;N,1,-x);insert(p[i][j],p[i][j]&#43;N,k,0);//建立仅供行走的无价值边
}}for(int i&#61;1;i<&#61;n;i&#43;&#43;){for(int j&#61;1;j<&#61;n;j&#43;&#43;){if(j1],k,0);if(i1][j],k,0);}}insert(S,1,k,0);insert(N&#43;N,T,k,0);ans&#61;0;while(spfa()){while(dfs(S,inf))memset(vis,0,N&#43;N&#43;2);}printf("%d",-ans);return 0;
}

View Code

 

 

#include
#include

#include

using namespace std;
int n,k,S,T;namespace nwf2{const int maxn&#61;5010,maxm&#61;10010,inf&#61;0x3f3f3f3f,N&#61;5005;int first[maxn],cur[maxn],tot&#61;1,q[maxn],d[maxn],ans&#61;0;//
bool vis[maxn];struct edge{int v,f,c,from;}e[maxm*2];void insert(int u,int v,int f,int c){tot&#43;&#43;;e[tot].v&#61;v;e[tot].f&#61;f;e[tot].c&#61;c;e[tot].from&#61;first[u];first[u]&#61;tot;tot&#43;&#43;;e[tot].v&#61;u;e[tot].f&#61;0;e[tot].c&#61;-c;e[tot].from&#61;first[v];first[v]&#61;tot;}bool spfa(){memset(d,0x3f,sizeof(d));d[T]&#61;0;vis[T]&#61;1;int head&#61;0,tail&#61;1;q[head]&#61;T;while(head!&#61;tail){//
int x&#61;q[head&#43;&#43;];if(head>N)head&#61;0;for(int i&#61;first[x];i;i&#61;e[i].from)if(e[i^1].f&&d[x]&#43;e[i^1].c//
d[e[i].v]&#61;d[x]&#43;e[i^1].c;if(!vis[e[i].v]){if(d[e[i].v]if(head<0)head&#61;N;q[head]&#61;e[i].v;}else{q[tail&#43;&#43;]&#61;e[i].v;if(tail>N)tail&#61;0;}vis[e[i].v]&#61;1;}}vis[x]&#61;0;}return d[S]<inf;}int dfs(int x,int a){if(x&#61;&#61;T||a&#61;&#61;0)return a;vis[x]&#61;1;int flow&#61;0,f;for(int& i&#61;cur[x];i;i&#61;e[i].from)if(!vis[e[i].v]&&d[e[i].v]&#43;e[i].c&#61;&#61;d[x]&&(f&#61;dfs(e[i].v,min(e[i].f,a)))){//
e[i].f-&#61;f;e[i^1].f&#43;&#61;f;ans&#43;&#61;e[i].c*f;flow&#43;&#61;f;a-&#61;f;if(a&#61;&#61;0)break;}vis[x]&#61;0;return flow;}int dinic(){ans&#61;0;while(spfa()){for(int i&#61;S;i<&#61;T;i&#43;&#43;)cur[i]&#61;first[i];dfs(S,inf);}return ans;}
}
int main(){scanf("%d%d",&n,&k);S&#61;0;T&#61;5001;for(int i&#61;1;i<&#61;n;i&#43;&#43;){for(int j&#61;1;j<&#61;n;j&#43;&#43;){int u;scanf("%d",&u);nwf2::insert((i-1)*n&#43;j,(i-1)*n&#43;j&#43;2500,1,-u);nwf2::insert((i-1)*n&#43;j,(i-1)*n&#43;j&#43;2500,k-1,0);if(i!&#61;n)nwf2::insert((i-1)*n&#43;j&#43;2500,i*n&#43;j,k,0);if(j!&#61;n)nwf2::insert((i-1)*n&#43;j&#43;2500,(i-1)*n&#43;j&#43;1,k,0);}}nwf2::insert(S,1,k,0);nwf2::insert(n*n&#43;2500,T,k,0);printf("%d",-nwf2::dinic());return 0;
}

View Code

 

转:https://www.cnblogs.com/onioncyc/p/6445896.html



推荐阅读
  • 本文主要解析了Open judge C16H问题中涉及到的Magical Balls的快速幂和逆元算法,并给出了问题的解析和解决方法。详细介绍了问题的背景和规则,并给出了相应的算法解析和实现步骤。通过本文的解析,读者可以更好地理解和解决Open judge C16H问题中的Magical Balls部分。 ... [详细]
  • 云原生边缘计算之KubeEdge简介及功能特点
    本文介绍了云原生边缘计算中的KubeEdge系统,该系统是一个开源系统,用于将容器化应用程序编排功能扩展到Edge的主机。它基于Kubernetes构建,并为网络应用程序提供基础架构支持。同时,KubeEdge具有离线模式、基于Kubernetes的节点、群集、应用程序和设备管理、资源优化等特点。此外,KubeEdge还支持跨平台工作,在私有、公共和混合云中都可以运行。同时,KubeEdge还提供数据管理和数据分析管道引擎的支持。最后,本文还介绍了KubeEdge系统生成证书的方法。 ... [详细]
  • Go GUIlxn/walk 学习3.菜单栏和工具栏的具体实现
    本文介绍了使用Go语言的GUI库lxn/walk实现菜单栏和工具栏的具体方法,包括消息窗口的产生、文件放置动作响应和提示框的应用。部分代码来自上一篇博客和lxn/walk官方示例。文章提供了学习GUI开发的实际案例和代码示例。 ... [详细]
  • 使用nodejs爬取b站番剧数据,计算最佳追番推荐
    本文介绍了如何使用nodejs爬取b站番剧数据,并通过计算得出最佳追番推荐。通过调用相关接口获取番剧数据和评分数据,以及使用相应的算法进行计算。该方法可以帮助用户找到适合自己的番剧进行观看。 ... [详细]
  • vue使用
    关键词: ... [详细]
  • Iamtryingtomakeaclassthatwillreadatextfileofnamesintoanarray,thenreturnthatarra ... [详细]
  • 在Android开发中,使用Picasso库可以实现对网络图片的等比例缩放。本文介绍了使用Picasso库进行图片缩放的方法,并提供了具体的代码实现。通过获取图片的宽高,计算目标宽度和高度,并创建新图实现等比例缩放。 ... [详细]
  • IhaveconfiguredanactionforaremotenotificationwhenitarrivestomyiOsapp.Iwanttwodiff ... [详细]
  • 本文讨论了使用差分约束系统求解House Man跳跃问题的思路与方法。给定一组不同高度,要求从最低点跳跃到最高点,每次跳跃的距离不超过D,并且不能改变给定的顺序。通过建立差分约束系统,将问题转化为图的建立和查询距离的问题。文章详细介绍了建立约束条件的方法,并使用SPFA算法判环并输出结果。同时还讨论了建边方向和跳跃顺序的关系。 ... [详细]
  • 本文介绍了P1651题目的描述和要求,以及计算能搭建的塔的最大高度的方法。通过动态规划和状压技术,将问题转化为求解差值的问题,并定义了相应的状态。最终得出了计算最大高度的解法。 ... [详细]
  • Linux环境变量函数getenv、putenv、setenv和unsetenv详解
    本文详细解释了Linux中的环境变量函数getenv、putenv、setenv和unsetenv的用法和功能。通过使用这些函数,可以获取、设置和删除环境变量的值。同时给出了相应的函数原型、参数说明和返回值。通过示例代码演示了如何使用getenv函数获取环境变量的值,并打印出来。 ... [详细]
  • 本文介绍了一个题目的解法,通过二分答案来解决问题,但困难在于如何进行检查。文章提供了一种逃逸方式,通过移动最慢的宿管来锁门时跑到更居中的位置,从而使所有合格的寝室都居中。文章还提到可以分开判断两边的情况,并使用前缀和的方式来求出在任意时刻能够到达宿管即将锁门的寝室的人数。最后,文章提到可以改成O(n)的直接枚举来解决问题。 ... [详细]
  • Android开发实现的计时器功能示例
    本文分享了Android开发实现的计时器功能示例,包括效果图、布局和按钮的使用。通过使用Chronometer控件,可以实现计时器功能。该示例适用于Android平台,供开发者参考。 ... [详细]
  • 浏览器中的异常检测算法及其在深度学习中的应用
    本文介绍了在浏览器中进行异常检测的算法,包括统计学方法和机器学习方法,并探讨了异常检测在深度学习中的应用。异常检测在金融领域的信用卡欺诈、企业安全领域的非法入侵、IT运维中的设备维护时间点预测等方面具有广泛的应用。通过使用TensorFlow.js进行异常检测,可以实现对单变量和多变量异常的检测。统计学方法通过估计数据的分布概率来计算数据点的异常概率,而机器学习方法则通过训练数据来建立异常检测模型。 ... [详细]
  • 预备知识可参考我整理的博客Windows编程之线程:https:www.cnblogs.comZhuSenlinp16662075.htmlWindows编程之线程同步:https ... [详细]
author-avatar
经典调剂行570
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有