题目链接
题解：减去行列最大值，再通过二分图匹配加上多减的边。
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define dnt long long
const int N = 105;
int mp [N] [N] , sl [N] , sr [N] , lk [N] , vis [N] ;
int n , m ;
vector <int> G [N] ;
int find ( int u ){for ( int i = 0 ; i < G [u].size () ; ++ i ){int v = G [u] [i] ;if ( ! vis [v] ) {vis [v] = 1;if ( lk [v] == -1 || find ( lk [v] ) ){lk [v] = u ;return 1 ;}}}return 0 ;
}int main (){scanf ( "%d%d" , &n , &m ) ;dnt ans = 0;for ( int i = 1 ; i <= n ; ++ i )for ( int j = 1 ; j <= m ; ++ j ){scanf ( "%d" , & mp [i] [j] );sr [i] = max ( sr [i] , mp [i] [j] );sl [j] = max ( sl [j] , mp [i] [j] );ans += mp [i] [j] ;}
// for ( int i = 1 ; i <= m ; ++ i ) printf ( "%d\n" , sl [i] );for ( int i = 1 ; i <= n ; ++ i )for ( int j = 1 ; j <= m ; ++ j ) if ( mp [i] [j] ){ans -- ;if ( sr[i] > 1 && sr [i] == sl [j] ) G [i].push_back ( j );}for ( int i = 1 ; i <= n ; ++ i ) if ( sr [i] ) ans -= sr [i] - 1 ;for ( int i = 1 ; i <= m ; ++ i ) if ( sl [i] ) ans -= sl [i] - 1 ;
// printf ( "%d\n" , ans );memset ( lk , -1 , sizeof ( lk ) ) ;for ( int i = 1 ; i <= n ; ++ i ) {if ( sr [i] ) memset ( vis , 0 , sizeof ( vis ) ) , ans += find ( i ) * ( sr [i] - 1 ) ;} printf ( "%lld" , ans ) ;return 0 ;
}