hdu3488

题解：

首先把每一个点拆到两边

然后做KM求最大

吧没一条边相反即可

代码：

#include<cstdio>

#include<cmath>

#include<algorithm>

#include<cstring>

using namespace std;

const int N=;

int a[N][N],z;

int visr[N],T,x,y,exl[N],exr[N],visl[N],match[N],slack[N],n,m;

int dfs(int x)

{

    visl[x]=;

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

     if (!visr[i])

      {

          int k=exl[x]+exr[i]-a[x][i];

          if (k==)

           {

               visr[i]=;

               if (!match[i]||dfs(match[i]))

                {

                    match[i]=x;

                    return ;

                }

           }

          else slack[i]=min(slack[i],k);

      }

    return ;

}

int read()

{

    char c;int x=;

    for (;c<''||c>'';c=getchar());

    for (;c>=''&&c<='';c=getchar())x=x*+c-;

    return x;

}

int main()

{

    T=read();

    while (T--)

     {

         n=read();m=read();

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

          for (int j=;j<=n;j++)a[i][j]=-(n*+);

         while (m--)

          {

              x=read();y=read();z=read();

              a[x][y]=max(-z,a[x][y]);

          }

         for (int i=;i<=n;i++)exl[i]=-(n*+);

         memset(exr,,sizeof exr);

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

         for (int j=;j<=n;j++)exl[i]=max(exl[i],a[i][j]);

        memset(match,,sizeof match);

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

         {

              memset(slack,0x3f,sizeof slack);

              while ()

               {

                   memset(visl,,sizeof visl);

                   memset(visr,,sizeof visr);

                   if (dfs(i))break;

                   int d=1e9;

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

                    if (!visr[j])d=min(d,slack[j]);

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

                 {

                     if (visl[j])exl[j]-=d;

                     if (visr[j])exr[j]+=d;

                     else slack[j]-=d;

                 }

               }

         }

        int ans=;

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

         ans+=a[match[i]][i];

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

     }

}