题解：
首先把每一个点拆到两边
然后做KM求最大
吧没一条边相反即可
代码：
#include<cstdio> #include<cmath> #include<algorithm> #include<cstring> using namespace std; const int N=205; 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]=1; for (int i=1;i<=n;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 read() { char c;int x=0; for (;c<'0'||c>'9';c=getchar()); for (;c>='0'&&c<='9';c=getchar())x=x*10+c-48; return x; } int main() { T=read(); while (T--) { n=read();m=read(); for (int i=1;i<=n;i++) for (int j=1;j<=n;j++)a[i][j]=-(n*10000+1); while (m--) { x=read();y=read();z=read(); a[x][y]=max(-z,a[x][y]); } for (int i=1;i<=n;i++)exl[i]=-(n*10000+1); memset(exr,0,sizeof exr); for (int i=1;i<=n;i++) for (int j=1;j<=n;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<=n;j++) if (!visr[j])d=min(d,slack[j]); for (int j=1;j<=n;j++) { if (visl[j])exl[j]-=d; if (visr[j])exr[j]+=d; else slack[j]-=d; } } } int ans=0; for (int i=1;i<=n;i++) ans+=a[match[i]][i]; printf("%d ",-ans); } }