boat's Blog

#include <stdio.h>
#include <iostream>
#include <string.h>
using namespace std;
const int N=210;
const int inf=0x7fffffff;
int match[N];
long long lack;
long long  w[N][N];
int n,m;
bool visx[N],visy[N];
long long lx[N],ly[N];
int wmax=300005;
bool dfs(int x)
{
     visx[x]=true;
     for(int y=1;y<=n;y++)
     {
       if(visy[y]) continue;
       int t=lx[x]+ly[y]-w[x][y];
       if(t==0)
       {
         visy[y]=true;
         if(match[y]==-1||dfs(match[y]))
         {
           match[y]=x;
           return true;
         }
       }
       else if(lack>t) lack=t;
     }
     return false;
}
void KM()
{
     memset(lx,0,sizeof(lx));
     memset(ly,0,sizeof(ly));
     memset(match,-1,sizeof(match));
     for(int i=1;i<=n;i++)
     for(int j=1;j<=n;j++)
     if(w[i][j]>lx[i]) lx[i]=w[i][j];
     for(int x=1;x<=n;x++)
     {
       for(;;)
       {
        memset(visx,0,sizeof(visx));
        memset(visy,0,sizeof(visy));
        lack=inf;
        if(dfs(x)) break;
        for(int i=1;i<=n;i++)
        {
           if(visx[i]) lx[i]-=lack;
           if(visy[i]) ly[i]+=lack;
        }
       }
     }
}
int main()
{
    int t;
    long long sum;
    cin>>t;
    while(t--)
    {
      memset(w,0,sizeof(w));
      scanf("%d%d",&n,&m);
      for(int i=0;i<m;i++)
      {
       int a,b,c;
       cin>>a>>b>>c;
       if(wmax-c>w[a][b])
       w[a][b]=wmax-c;
       
      }
      KM();
      sum=0;
     for(int i=1;i<=n;i++)
     {
    // printf("match[%d][%d]=%d\n",match[i],i,inf-w[match[i]][i]);
     sum+=wmax-w[match[i]][i];
     }
     printf("%d\n",sum);
    }
}