HDU 3435 KM A new Graph Game

和HDU 3488一样的，只不过要判断一下是否有解。

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 #include <vector>

 using namespace std;

 const int maxn =  + ;

 const int INF = 0x3f3f3f3f;

 int n, m;

 int W[maxn][maxn], lft[maxn];

 int slack[maxn];

 int Lx[maxn], Ly[maxn];

 bool S[maxn], T[maxn];

 bool match(int u)

 {

     S[u] = true;

     for(int v = ; v <= n; v++) if(!T[v])

     {

         int t = Lx[u] + Ly[v] - W[u][v];

         if( == t)

         {

             T[v] = true;

             if(!lft[v] || match(lft[v]))

             {

                 lft[v] = u;

                 return true;

             }

         }

         else slack[v] = min(slack[v], t);

     }

     return false;

 }

 void update()

 {

     int a = INF;

     for(int i = ; i <= n; i++) if(!T[i]) a =  min(a, slack[i]);

     for(int i = ; i <= n; i++)

     {

         if(S[i]) Lx[i] -= a;

         if(T[i]) Ly[i] += a;

         else  slack[i] -= a;

     }

 }

 void KM()

 {

     memset(Ly, , sizeof(Ly));

     memset(lft, , sizeof(lft));

     for(int i = ; i <= n; i++) Lx[i] = -INF;

     for(int i = ; i <= n; i++)

         for(int j = ; j <= n; j++) Lx[i] = max(Lx[i], W[i][j]);

     for(int i = ; i <= n; i++)

     {

         memset(slack, 0x3f, sizeof(slack));

         for(;;)

         {

             memset(S, false, sizeof(S));

             memset(T, false, sizeof(T));

             if(match(i)) break;

             update();

         }

     }

 }

 int main()

 {

     int T; scanf("%d", &T);

     for(int kase = ; kase <= T; kase++)

     {

         scanf("%d%d", &n, &m);

         for(int i = ; i <= n; i++)

             for(int j = ; j <= n; j++)

                 W[i][j] = -INF;

         for(int i = ; i < m; i++)

         {

             int u, v, d; scanf("%d%d%d", &u, &v, &d);

             if(W[u][v] < -d) W[u][v] = W[v][u] = -d;

         }

         KM();

         bool ok = true;

         int ans = ;

         for(int i = ; i <= n; i++)

         {

             if(W[lft[i]][i] == -INF) { ok = false; break; }

             ans += W[lft[i]][i];

         }

         printf("Case %d: ", kase);

         if(!ok) puts("NO");

         else printf("%d\n", -ans);

     }

     return ;

 }

代码君