76 lines
1.7 KiB
C++
76 lines
1.7 KiB
C++
#include<stdio.h>
|
|
#include<string.h>
|
|
#define inf 1000000
|
|
#define N 205
|
|
int n,y[N],g[N][N],lx[N],ly[N],slack[N];
|
|
char vx[N],vy[N];
|
|
int search(int u)
|
|
{
|
|
vx[u]=1;
|
|
for(int v=1;v<=n;v++)
|
|
if(lx[u]+ly[v]==g[u][v])
|
|
{
|
|
if(vy[v]==1) continue;
|
|
vy[v]=1;
|
|
if(y[v]==-1||search(y[v]))
|
|
{
|
|
y[v]=u;
|
|
return 1;
|
|
}
|
|
}
|
|
else if(lx[u]+ly[v]-g[u][v]<slack[v])
|
|
slack[v]=lx[u]+ly[v]-g[u][v];
|
|
return 0;
|
|
}
|
|
int KM()
|
|
{
|
|
int i,j,min;
|
|
memset(y,-1,sizeof(y));
|
|
memset(ly,0,sizeof(ly));
|
|
memset(lx,0,sizeof(lx));
|
|
for(i=1;i<=n;i++)
|
|
{
|
|
for(j=1;j<=n;j++)
|
|
slack[j]=inf;
|
|
while(1)
|
|
{
|
|
memset(vx,0,sizeof(vx));
|
|
memset(vy,0,sizeof(vy));
|
|
if(search(i)) break;
|
|
for(min=inf,j=1;j<=n;j++)
|
|
if(!vy[j]&&slack[j]<min)
|
|
min=slack[j];
|
|
for(j=1;j<=n;j++)
|
|
if(vx[j]) lx[j]-=min;
|
|
for(j=1;j<=n;j++)
|
|
if(vy[j]) ly[j]+=min;
|
|
else slack[j]-=min;
|
|
}
|
|
}
|
|
int ans=0;
|
|
for(i=1;i<=n;i++)
|
|
ans+=g[y[i]][i];
|
|
return ans;
|
|
}
|
|
int main()
|
|
{
|
|
int t,m,i,j,u,v,w;
|
|
scanf("%d",&t);
|
|
while(t--)
|
|
{
|
|
scanf("%d%d",&n,&m);
|
|
for(i=1;i<=n;i++)
|
|
for(j=1;j<=n;j++)
|
|
g[i][j]=-inf;
|
|
for(i=0;i<m;i++)
|
|
{
|
|
scanf("%d%d%d",&u,&v,&w);
|
|
if(g[u][v]<-w)
|
|
g[u][v]=-w;
|
|
}
|
|
int ans=-1*KM();
|
|
printf("%d\n",ans);
|
|
}
|
|
return 0;
|
|
}
|