\(\mathbf{} \begin{Bmatrix} \frac{{\Large 朱刘模版} }{{\color{Blue}\Large Template} }\mathbf{} {No.3} \end{Bmatrix}\times{}\) NeeDna
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=210,inf=1e18;
struct node{int v,val;};
vector<node> g[N];
int mi[N],fr[N],fa[N],cnt;
int n,m,r;
int find(int x){if(x==fa[x]) return x;return fa[x]=find(fa[x]);
}
int zl(int rt){cnt=n;for(int i=1;i<=n*2;i++) fa[i]=i;int in=0,f=0;while(1){int sum=0;for(int u=1;u<=cnt;u++){if(fa[u]!=u||u==rt) continue;mi[u]=inf;for(node t:g[u]){int v=t.v,val=t.val;if(u!=find(v)&&val<mi[u]){mi[u]=val,fr[u]=find(v);} }if(mi[u]==inf) return -1;sum+=mi[u];}bool vis[N]={0},stk[N]={0};vis[rt]=1,f=0;for(int i=1;i<=cnt;i++){if(fa[i]!=i||vis[i]) continue;for(int x=i;!vis[x];x=fr[x]){vis[x]=stk[x]=1;if(stk[fr[x]]){cnt++;for(int j=x;find(j)!=cnt;j=fr[j]){fa[j]=cnt,in+=mi[j];for(int k=0;k<g[j].size();k++){g[cnt].push_back({g[j][k].v,g[j][k].val-mi[j]});}}f=1; goto loop;}} memset(stk,0,sizeof(stk));}loop:;if(!f) return sum+in;}
}
signed main(){cin>>n>>m>>r;for(int i=1;i<=m;i++){int u,v,w;cin>>u>>v>>w;g[v].push_back({u,w});}cout<<zl(r)<<'\n';
}