Description：

在一个 $n\times m$ 的棋盘上放置若干个守卫。每行放置一个横向守卫；每列放置一个纵向守卫。一个守卫不能同时兼顾行列的防御。计算控制整个棋盘的最小代价。

$1\leqslant n\times m\leqslant10^5$

Solution：

棋盘问题的套路，把行和列看作点，中间的格子看作之间的边，那么问题就变成了选出一些边并给他们定向，使得每个点入度都为 $1$ ，发现这其实就是一个最小基环生成树森林问题，可以用类似 $kruskal$ 的做法解决，即把边排序，如果两端点不连通且两个联通块至少有一个还没有环，就把他们联通，如果他们联通且联通块还没有环，也把他们联通并打标记。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

#define MAXN 100010

#define R register

inline int rd()

{

	R int res = 0,f = 1;

	R char c = getchar();

	while(!isdigit(c))

	{

		if(c == '-')f = -1;

		c = getchar();

	}

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res * f;

}

int n,m;

struct edges

{

	int u,v,w;

}es[MAXN];

bool cmp_w(edges a,edges b){return a.w < b.w;}

int tot = 0;

int f[MAXN];

bool g[MAXN];

int find(int x){return (x == f[x] ? x : f[x] = find(f[x]));}

int main()

{

	scanf("%d%d",&n,&m);

	for(int i = 1;i <= n;++i)

		for(int j = 1;j <= m;++j)

			es[++tot] = (edges){i,j + n,rd()};

	for(int i = 1;i <= n;++i)f[i] = i;

	for(int j = 1;j <= m;++j)f[n + j] = n + j;

	sort(es + 1,es + 1 + tot,cmp_w);

	long long ans = 0;

	for(int i = 1;i <= tot;++i)

	{

		int p = find(es[i].u),q = find(es[i].v);

		if(p == q)

		{

			if(!g[p])

			{

				g[p] = true;

				ans += es[i].w;

			}

		}

		else

		{

			if(g[p] && g[q])continue; 

			f[p] = q;

			g[q] |= g[p];

			ans += es[i].w;

		}

	}

	cout << ans << endl;

	return 0;

}