$\quad $ 初看就发现不对劲了，模板紫题，一看就不简单，就交了个裸\(KM\)，哎，果然\(T\)了。
$\quad $ 然后就是大力卡常（当然\(O(n^4)\)）的复杂度不是卡常能解决的。遂看题解，发现一个据说\(O(n^3)\)的复杂度的\(KM\)，也是非常抽象。
具体解释详见 https://www.luogu.com.cn/article/ip2m1gut
$\quad $ 当我还在研究题解的时候\(luobutianle\)直接就是溜过来跟我说倒着遍历可以起飞。我当时就是蒙，他就直接让我试了试，也是确实起飞了。
$\quad $ 大抵是造数据的人想卡\(KM\)，认为人们都是正着遍历，就正着卡了。
献上我的大力卡常代码（当然过了）
点击查看代码
#include<bits/stdc++.h>using namespace std;#define int long longconst int N=550,M=250500;int match[N],slack[N],a[N],b[N],w[N][N],n,m,vis[N],rnd;int r(){int ans=0;bool f=0;char ch=getchar();while(ch<'0' || ch>'9'){if(ch=='-')f=1;ch=getchar();}while(ch>='0' && ch<='9'){ans=(ans<<1)+(ans<<3)+(ch^48);ch=getchar();}return f?~ans+1:ans;}bool dfs(int x){for(int i=1;i<=n;i=-~i){if(vis[i]^rnd){if(!((a[x]+b[i])^w[x][i])){vis[i]=rnd;if(!match[i]||dfs(match[i])){match[i]=x;return true;}}else slack[i]=min(slack[i],a[x]+b[i]-w[x][i]);}}return false;}void write(long long n){if(n>9)write(n/10);putchar(n%10+'0');}signed main(){freopen("1.in","r",stdin);n=r(),m=r();for(int i=0;i<=n;i=-~i){for(int j=0;j<=n;j=-~j){w[i][j]=-9999999999;}}for(int i=1;i<=m;i=-~i)w[r()][r()]=r();for(int i=0;i<=n;i=-~i)a[i]=-99999999999;for(int i=1;i<=n;i=-~i){for(int j=1;j<=n;j=-~j){a[i]=max(a[i],w[i][j]);}}for(int i=0;i<=n;i=-~i)slack[i]=99999999999;for(int i=n;i>=1;i--){while(1){rnd++;if(dfs(i))break;int d=1e18;for(int j=1;j<=n;j++)if(vis[j]^rnd)d=min(d,slack[j]),slack[j]=99999999999;for(int j=1;j<=n;j++)if(vis[j]==rnd)b[j]+=d,a[match[j]]-=d;a[i]-=d;}}int ans=0;for(int i=1;i<=n;i=-~i)ans+=a[i]+b[i];ans<0?putchar('-'),ans=-ans:0;write(ans);putchar('\n');for(int i=1;i<=n;i=-~i)write(match[i]),putchar(' ');return 0;}
还有优化代码：
点击查看代码
#include<bits/stdc++.h>using namespace std;#define int long longconst int N=550,M=250500;int match[N],slack[N],a[N],b[N];int vis[N],rnd,pre[N];bool vx[N],vy[N];int matchy[N],matchx[N];int w[N][N],n,m;queue<int>q;long long r(){long long ans=0;bool f=0;char ch=getchar();while(ch<'0' || ch>'9'){if(ch=='-')f=1;ch=getchar();}while(ch>='0' && ch<='9'){ans=(ans<<1)+(ans<<3)+(ch^48);ch=getchar();}return f?~ans+1:ans;}void fl(int x){int t;while(x){t=matchx[pre[x]];matchx[pre[x]]=x;matchy[x]=pre[x];x=t;}return;}void dfs(int l){memset(vx,0,sizeof vx);memset(vy,0,sizeof vy);memset(slack,0x7f,sizeof slack);while(q.size())q.pop();q.push(l);while(1){while(q.size()){int x=q.front();q.pop();vx[x]=1;for(int i=1;i<=n;i++){if(vy[i]!=1){if(a[x]+b[i]-w[x][i]<slack[i]){slack[i]=a[x]+b[i]-w[x][i];pre[i]=x;if(!slack[i]){vy[i]=1;if(!matchy[i]){fl(i);return;}else q.push(matchy[i]);}}}}}int d=1e18;for(int i=1;i<=n;i++)if(vy[i]!=1)d=min(d,slack[i]);for(int i=1;i<=n;i++){if(vx[i]==1)a[i]-=d;if(vy[i]==1)b[i]+=d;else slack[i]-=d;}for(int i=1;i<=n;i++){if(vy[i]!=1){if(!slack[i]){vy[i]=1;if(!matchy[i]){fl(i);return;}else q.push(matchy[i]);}}} }}void wr(int x){if(x>9)wr(x/10);putchar(x%10+'0');}signed main(){n=r(),m=r();memset(w,0xcf,sizeof w);for(int i=1;i<=m;i++){w[r()][r()]=r();}memset(a,0xcf,sizeof a);for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)a[i]=max(a[i],w[i][j]);for(int i=1;i<=n;i++)dfs(i);int ans=0;for(int i=1;i<=n;i++)ans+=a[i]+b[i];ans<0?putchar('-'),ans=-ans:0;wr(ans);putchar('\n');for(int i=1;i<=n;i++)wr(matchy[i]),putchar(' ');return 0;}
