Krydom: 暁の水平线に胜利を刻むのです

ソロモンの悪夢、見せてあげる!

@krydom5月前

05/17
20:42
kruskal

[bzoj 4883] [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

♦♦♦♦♦♦   Sample Output   ♦♦♦♦♦♦

19

HINT
在(1,1),(2,2),(3,1)放置横向守卫,在(2,1),(1,2),(3,3),(2,4)放置纵向守卫。

♦♦♦♦♦♦   Hint   ♦♦♦♦♦♦

♦♦♦♦♦♦   题解  ♦♦♦♦♦♦

把行和列看成点,对于每个(i,j) 把第i行和第j列连上边权为 w[i][j] 的边,最后求一个最小环套树森林即可

 

[bzoj 4883] [Lydsy2017年5月月赛]棋盘上的守卫