1 /* 2     KM： 相比HDOJ_1533，多了重边的处理，还有完美匹配的判定方法 3 */ 4 #include 
     
       5 #include 
      
        6 #include 
       
         7 #include 
        
          8 using namespace std; 9 10 const int MAXN = 1e2 + 10;11 const int INF = 0x3f3f3f3f;12 int x[MAXN], y[MAXN];13 int w[MAXN][MAXN];14 int visx[MAXN], visy[MAXN];15 int ly[MAXN];16 int n, m, d;17 18 bool DFS(int u) {19     visx[u] = true;20     for (int i=1; i<=n; ++i)   {21         if (!visy[i] && x[u] + y[i] == w[u][i]) {22             visy[i] = true;23             if (ly[i] == -1 || DFS (ly[i])) {24                 ly[i] = u;  return true;25             }26         }27         else if (x[u] + y[i] > w[u][i]) d = min (d, x[u] + y[i] - w[u][i]);28     }29     return false;30 }31 32 int KM(void)    {33     for (int i=1; i<=n; ++i)   {34         x[i] = -INF;35         for (int j=1; j<=n; ++j)   {36             x[i] = max (x[i], w[i][j]);            37         }38     }39 40     memset (ly, -1, sizeof (ly));41     memset (y, 0, sizeof (y));42     for (int i=1; i<=n; ++i)    {43         while (true)    {44             memset (visx, false, sizeof (visx));45             memset (visy, false, sizeof (visy));46             d = INF;47             if (DFS (i))    break;48             for (int i=1; i<=n; ++i)   {49                 if (visx[i])    x[i] -= d;50             }51             for (int j=1; j<=n; ++j)   {52                 if (visy[j])    y[j] += d;53             }54         }55     }56 57     for (int i=1; i<=n; ++i)    {58         if (ly[i] == -1 || w[ly[i]][i] == -INF) return -1;59     }60 61     int res = 0;62     for (int i=1; i<=n; ++i)   {63         res += x[i] + y[i];64     }65 66     return -res;67 }68 69 int main(void)  {       //HDOJ 1853 Cyclic Tour70     //freopen ("HDOJ_1853.in", "r", stdin);71 72     while (scanf ("%d%d", &n, &m) == 2) {73         if (!n && !m)   break;74         for (int i=1; i<=n; ++i)    {75             for (int j=1; j<=n; ++j)    w[i][j] = -INF;76         }77         for (int i=1; i<=m; ++i)    {78             int u, v, c;    scanf ("%d%d%d", &u, &v, &c);79             if (-c > w[u][v])   w[u][v] = -c;80         }81         printf ("%d\n", KM ());82     }83 84     return 0;85 }