思路：有向图中每个点存在且仅存在于一个环中：每个点出度为1，入度为1.
#include <bits/stdc++.h> using namespace std; typedef long long LL; typedef LL lint; const int maxn = 205; const lint inf = 0x3f3f3f3f3f3f3f3f; namespace KM { const int N = 205; int n; lint cost[N][N]; lint lx[N], ly[N], match[N], slack[N]; int prev[N]; bool vy[N]; void init(int n) { KM::n = n; for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) cost[i][j] = -inf; } bool augment(int root) { fill(vy + 1, vy + n + 1, false); fill(slack + 1, slack + n + 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 <= n; 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 <= n; 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; } lint KM() { for (int i = 1; i <= n; i++) { lx[i] = ly[i] = 0; match[i] = -1; for (int j = 1; j <= n; j++) lx[i] = max(lx[i], cost[i][j]); } lint answer = 0; for (int root = 1; root <= n; root++) { if(!augment(root))return -1; } for (int i = 1; i <= n; i++) { answer += lx[i]; answer += ly[i]; } return answer; } } int main(){ int n,m; while( 2 == scanf("%d%d",&n,&m) ){ KM::init(n); int x,y,z; for( int i = 1;i <= m;i++ ){ scanf("%d%d%d",&x,&y,&z); z = -z; KM::cost[x][y] = KM::cost[x][y] == -inf ? z : max( KM::cost[x][y],(LL)z ); } LL ans = KM::KM(); if( ans == -1 ){ puts("-1"); }else{ printf("%lld\n",-ans); } } return 0; }
