思路：

将问题转化成最小费用流

代码：

#pragma GCC optimize(2)#pragma GCC optimize(3)#pragma GCC optimize(4)#include
     
      using namespace std;#define y1 y11#define fi first#define se second#define pi acos(-1.0)#define LL long long//#define mp make_pair#define pb push_back#define ls rt<<1, l, m#define rs rt<<1|1, m+1, r#define ULL unsigned LL#define pll pair
      
       #define pli pair
       
        #define pii pair
        
         #define piii pair
         
          #define pdd pair
          
           #define mem(a, b) memset(a, b, sizeof(a))#define debug(x) cerr << #x << " = " << x << "\n";#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);//headconst int N = 200 + 10;const int INF = 0x3f3f3f3f;int a[N][N];struct edge { int to, cap, cost, rev;};int V;vector
           
            g[N];int h[N], dis[N], prevv[N], preve[N];void add_edge(int u, int v, int cap, int cost) { g[u].pb({v, cap, cost, g[v].size()}); g[v].pb({u, 0, -cost, g[u].size()-1});}int min_cost_flow(int s, int t, int f) { int res = 0; mem(h, 0); while(f > 0) { priority_queue
            
             , greater
             
               > q; mem(dis, 0x3f); dis[s] = 0; q.push({ 0, s}); while(!q.empty()) { pii p = q.top(); q.pop(); int v = p.se; if(dis[v] < p.fi) continue; for (int i = 0; i < g[v].size(); ++i) { edge &e = g[v][i]; if(e.cap > 0 && dis[e.to] > dis[v] + e.cost + h[v] - h[e.to]) { dis[e.to] = dis[v] + e.cost + h[v] - h[e.to]; prevv[e.to] = v; preve[e.to] = i; q.push({dis[e.to], e.to}); } } } if(dis[t] == INF) return -1; for (int v = 0; v < V; ++v) h[v] += dis[v]; int d = f; for (int v = t; v != s; v = prevv[v]) d = min(d, g[prevv[v]][preve[v]].cap); f -= d; res += d*h[t]; for (int v = t; v != s; v = prevv[v]) { edge &e = g[prevv[v]][preve[v]]; e.cap -= d; g[v][e.rev].cap += d; } } return res;}int main() { int n = 15; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= n; ++j) { scanf("%d", &a[i][j]); add_edge(i, j+n, 1, 1000-a[i][j]); } } int s = 0, t = n+n+1; V = t+1; for (int i = 1; i <= n; ++i) add_edge(s, i, 1, 0); for (int i = 1; i <= n; ++i) add_edge(i+n, t, 1, 0); cout << 1000*n - min_cost_flow(s, t, n); return 0;}