判断不可行 + 左右点数不同的模板
#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,e,m; int ca = 0; while(3==scanf("%d%d%d",&n,&m,&e)){ KM::init(n,m); int u,v,w; for( int i = 1;i <= e;i++ ){ scanf("%d%d%d",&u,&v,&w); u++;v++; if(w >= 0) KM::cost[u][v] = max( KM::cost[u][v],w); } int ans; if( n > m ){ ans = -1; }else { bool flag = KM::KM(ans); if (!flag) { ans = -1; } } printf("Case %d: %d\n",++ca,ans); }; return 0; }
