【BZOJ4883】[Lydsy2017年5月月赛]棋盘上的守卫 KM算法
算法 棋盘 守卫
2023-09-11 14:15:27 时间
【BZOJ4883】[Lydsy2017年5月月赛]棋盘上的守卫
Description
在一个n*m的棋盘上要放置若干个守卫。对于n行来说,每行必须恰好放置一个横向守卫;同理对于m列来说,每列
必须恰好放置一个纵向守卫。每个位置放置守卫的代价是不一样的,且每个位置最多只能放置一个守卫,一个守卫
不能同时兼顾行列的防御。请计算控制整个棋盘的最小代价。
Input
第一行包含两个正整数n,m(2<=n,m<=100000,n*m<=100000),分别表示棋盘的行数与列数。
接下来n行,每行m个正整数
其中第i行第j列的数w[i][j](1<=w[i][j]<=10^9)表示在第i行第j列放置守卫的代价。
Output
输出一行一个整数,即占领棋盘的最小代价。
Sample Input
3 4
1 3 10 8
2 1 9 2
6 7 4 6
1 3 10 8
2 1 9 2
6 7 4 6
Sample Output
19
HINT
在(1,1),(2,2),(3,1)放置横向守卫,在(2,1),(1,2),(3,3),(2,4)放置纵向守卫。
HINT
在(1,1),(2,2),(3,1)放置横向守卫,在(2,1),(1,2),(3,3),(2,4)放置纵向守卫。
题解:从来没想过KM的时间复杂度能完虐费用流~
将 行、列 和 格点 分成两个集合,集合间连边,边权就是该格点的费用,然后将边权变成相反数,用KM跑最大匹配,最后再将答案取相反数就行了
考场上写(chao)的zkw费用流被虐暴了
#include <cstdio> #include <cstring> #include <iostream> using namespace std; typedef long long ll; int n,m,now,cnt; ll ans,temp; int va[200010],vb[200010],to[200010],next[200010],head[200010],from[200010]; ll la[200010],lb[200010],val[200010]; int rd() { int ret=0; char gc=getchar(); while(gc<'0'||gc>'9') gc=getchar(); while(gc>='0'&&gc<='9') ret=ret*10+gc-'0',gc=getchar(); return ret; } void add(int a,int b,int c) { to[cnt]=b,val[cnt]=c,next[cnt]=head[a],head[a]=cnt++; } int dfs(int x) { va[x]=now; for(int i=head[x];i!=-1;i=next[i]) { if(vb[to[i]]!=now) { if(!(la[x]+lb[to[i]]-val[i])) { vb[to[i]]=now; if(!from[to[i]]||dfs(from[to[i]])) { from[to[i]]=x; return 1; } } else temp=min(temp,la[x]+lb[to[i]]-val[i]); } } return 0; } int main() { n=rd(),m=rd(); int i,j,a; ll b; memset(head,-1,sizeof(head)); memset(la,0x80,sizeof(la)); for(i=1;i<=n;i++) for(j=1;j<=m;j++) a=(i-1)*m+j,b=-rd(),add(i,a,b),la[i]=max(la[i],b),add(j+n,a,b),la[j+n]=max(la[j+n],b); for(i=1;i<=n+m;i++) { while(1) { now++; temp=1ll<<60; if(dfs(i)) break; for(j=1;j<=n+m;j++) if(va[j]==now) la[j]-=temp; for(j=1;j<=n*m;j++) if(vb[j]==now) lb[j]+=temp; } } for(i=1;i<=n+m;i++) ans+=la[i]; for(i=1;i<=n*m;i++) ans+=lb[i]; printf("%lld",-ans); return 0; }
相关文章
- Java实现 蓝桥杯 算法提高 菱形
- Java实现 蓝桥杯VIP 算法提高 棋盘多项式
- Java实现 蓝桥杯VIP 算法提高 棋盘多项式
- Java实现 蓝桥杯VIP 算法提高 彩票
- Java实现 蓝桥杯VIP 算法训练 字符串编辑
- 某研究院的二叉树深度优先遍历变种的算法面试题以及答案
- 机器学习&深度学习基础(tensorflow版本实现的算法概述0)
- 浅谈压缩感知(九):正交匹配追踪算法OMP
- 程序员的算法趣题Q06: 改版考拉兹猜想
- Algorithm:C++语言实现之动态规划算法相关(矩阵连乘状态转移方程、字符串的交替连接、分析格网棋盘的特点、最短路线问题、生产计划问题、动态规划解下列非线性规划)
- Pytorch之CNN:从代码认知CNN经典架构—基于Pytorch框架的代码实现经典卷积神经网络的算法集合(LeNet/AlexNet/VGG/NIN/GoogleNet/ResNet)
- 基于蚁群优化算法的直流电机模糊PID控制(Matlab实现)
- 【电力系统】基于凸松弛算法的电力市场策略(Matlab代码实现)
- 【阶段三】Python机器学习10篇:机器学习项目实战:K近邻算法的基本原理、计算步骤与KNN(K近邻)分类模型
- 【数据结构与算法】编译原理基础知识 / 禅与计算机程序设计艺术 & ChatGPT
- 重拾算法(1)——优雅地非递归遍历二叉树及其它
- hash算法
- 数据结构和算法 数论 中国余数定理