大家都用的是网络流的做法，本人才疏学浅，想不到这种方法，于是写一个线性规划做法。

前置知识

你要会单纯形算法。

做法

考虑每行每列都至少有一个黑色节点，相当于如果设 $x_i$ 表示第 $i$ 个点黑色为 $1$，白色为 $0$，则相当于：

$$\min \sum_{i=1}^n c_i x_i\\ \forall 1 \leq i \leq H,\sum_{a_j=i}x_j \geq 1\\ \forall 1 \leq i \leq W,\sum_{b_j=i}x_j \geq 1$$

使用线性规划对偶原理，转换为标准型：

$$\max \sum_{i=1}^{H}y_i+\sum_{i=1}^{W}z_i\\ \forall 1 \leq i \leq n,y_{a_i}+z_{b_i} \leq c_i$$

实际上对 $c_i,y_i,z_i$ 同时取相反数也可以达到转换为标准型的效果，但是用对偶的方法能使得有基本解（零解），不需要写 init() 函数。

直接套模板即可。

代码：

#include<bits/stdc++.h>
#define rg int
#define ll long long
#define ci const int
#define ld double 
using namespace std;
ci N=60005;
const ld eps=1e-12;
const ll inf=1e12;
ll n,m;
ld a[2001][2001];
inline ll read(){ll u,f=1;char o;while((o=getchar())<48||o>57)if(o==45)f=-1;u=(o^48);while((o=getchar())>=48&&o<=57)u=(u<<1)+(u<<3)+(o^48);return u*f;}
void write(ll x){if(x<0)putchar(45),x=-x;if(x>9)write(x/10);putchar(x%10+48);}
mt19937 rd(time(0));
void Pivot(ci l,ci e){
	const ld u=a[l][e];a[l][e]=1;
	for(rg i=0;i<=n;++i)a[l][i]/=u;
	for(rg i=0;i<=m;++i)if(i!=l&&fabs(a[i][e])>eps){
		const ld u=a[i][e];a[i][e]=0;
		for(rg j=0;j<=n;++j)a[i][j]-=a[l][j]*u;
	}
}
ld Simplex()
{
	while(1){
		int e=0,l=0;
		for(rg i=1;i<=n;++i)if(a[0][i]>eps){
			e=i;
			break;
		}
		if(!e)return a[0][0];
		ld minn=inf;
		for(rg i=1;i<=m;++i)if(a[i][e]>eps&&minn>a[i][0]/a[i][e])minn=a[i][0]/a[i][e],l=i;
		Pivot(l,e);
	}
}
int main()
{
	int id=0,T=1;
	while(T--)
	{
		ll nn=read();ll mm=read();m=read();
		n=nn+mm;
		for(rg i=1;i<=n;++i)a[0][i]=1;
		for(rg i=1;i<=m;++i)
		{
			ll x=read(),y=read(),z=read();
			a[i][x]=1;
			a[i][nn+y]=1;
			a[i][0]=z;
		}
		write(-Simplex()+0.5),putchar('\n');
	}
	return 0;
}