hdu2426

题解：

KM模板题

如果n>m，输出-1

如果a[match[i]][i]==-1输出-1

负的边不用考虑

初始都赋值为-1

代码：

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=505;
int a[N][N],z,e,cas;
int visr[N],T,x,y,exl[N],exr[N],visl[N],match[N],slack[N],n,m;
int dfs(int x)
{
    visl[x]=1;
    for (int i=1;i<=m;i++)
     if (!visr[i])
      {
          int k=exl[x]+exr[i]-a[x][i];
          if (k==0)
           {
               visr[i]=1;
               if (!match[i]||dfs(match[i]))
                {
                    match[i]=x;
                    return 1;
                }
           }
          else slack[i]=min(slack[i],k); 
      }
    return 0;  
}
int main()
{
    while (~scanf("%d%d%d",&n,&m,&e))
     {
         printf("Case %d: ",++cas);
         for (int i=1;i<=n;i++)
          for (int j=1;j<=m;j++)a[i][j]=-1e9;
         while (e--)
          {
              scanf("%d%d%d",&x,&y,&z);
              if (z>=0)a[x+1][y+1]=z;
          } 
         if (n>m)
         {
              puts("-1");
              continue;
         } 
         memset(exl,0,sizeof exl);
         memset(exr,0,sizeof exr);
        for (int i=1;i<=n;i++)
         for (int j=1;j<=m;j++)exl[i]=max(exl[i],a[i][j]);
        memset(match,0,sizeof match); 
         for (int i=1;i<=n;i++)
         {
              memset(slack,0x3f,sizeof slack);
              while (1)
               {
                   memset(visl,0,sizeof visl);
                   memset(visr,0,sizeof visr);
                   if (dfs(i))break;
                   int d=1e9;
                   for (int j=1;j<=m;j++)
                    if (!visr[j])d=min(d,slack[j]);
                   for (int j=1;j<=n;j++)
                 if (visl[j])exl[j]-=d;
                for (int j=1;j<=m;j++)
                 if (visr[j])exr[j]+=d;
                 else slack[j]-=d;
               }
         } 
        int ans=0,flag=0; 
        for (int i=1;i<=m;i++)
         {
             if (a[match[i]][i]==-1e9)flag=1;
             ans+=a[match[i]][i];
         }
        if (flag)puts("-1");else printf("%d
",ans);
     }
}