思路：我们把所有边权扩大100倍，然后将原来有的边边权+1，用来处理相等的情况。
#include <bits/stdc++.h> using namespace std; typedef long long LL; typedef int lint; namespace KM { const int N = 505; const lint inf = 0x3f3f3f3f; int n,m; lint cost[N][N]; lint lx[N], ly[N], match[N], slack[N]; int prev[N]; bool vy[N]; void init(int _n,int _m) { n = _n; m = _m; for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) cost[i][j] = -inf; } bool augment(int root) { fill(vy, vy + m + 1, false); fill(slack, slack + m + 1, inf); int py; match[py = 0] = root; do { vy[py] = true; int x = match[py], yy; lint delta = inf; for (int y = 1; y <= m; y++) { if (!vy[y]) { if (lx[x] + ly[y] - cost[x][y] < slack[y]) { slack[y] = lx[x] + ly[y] - cost[x][y]; prev[y] = py; } if (slack[y] < delta) { delta = slack[y]; yy = y; } } } if( delta >= inf || delta <= -inf ) return false; for (int y = 0; y <= m; y++) { if (vy[y]) { lx[match[y]] -= delta; ly[y] += delta; } else slack[y] -= delta; } py = yy; } while (match[py] != -1); do { int pre = prev[py]; match[py] = match[pre]; py = pre; } while (py); return true; } bool KM(lint& Cost) { for( int i = 1;i <= m;i++ ) { ly[i] = 0;match[i] = -1; } for (int i = 1; i <= n; i++) { lx[i] = 0; for (int j = 1; j <= m; j++) lx[i] = max(lx[i], cost[i][j]); } for (int root = 1; root <= n; root++) { if(!augment(root))return false; } Cost = 0; for( int i = 1;i <= m;i++ ){ if( match[i] != -1 ){ Cost += cost[match[i]][i]; } } return true; } } int main(){ int n,m; while( 2 == scanf("%d%d",&n,&m) ){ int u,v,w; KM::init(n,m); int res = 0; for( int i = 1;i <= n;i++ ) { for (int j = 1; j <= m; j++) { scanf("%d",&w); w *= 100; KM::cost[i][j] = w; } } for( int i = 1;i <= n;i++ ){ scanf("%d",&u); res += KM::cost[i][u]/100; KM::cost[i][u]++; } int ans; KM::KM(ans); printf("%d %d\n",n-ans%100,ans/100-res); } return 0; }
