题意：对一个带权有向图，将所有点纳入一个或多个环中，且每个点只出现一次，求其所有环的路径之和最小值。
分析：每个点都只出现一次，那么换个思路想，每个点入度出度都为1。将一个点拆成两个点，一个作为入度点，一个作为出度点。每个入度点都和一个出度点匹配，且不为自己。那么可以将问题转化为二分图最优匹配的问题，这里我们求得是最短路径，那么建图时，把权值取反。这样最优匹配后取反就是最短的路径。
#include <cstdio> #include <vector> #include <algorithm> #include <cstring> #include <iostream> using namespace std; typedef long long LL; const int maxn =205; const int INF=0x3f3f3f3f; int w[maxn][maxn]; int m,n;//n左m右 int cx[maxn],cy[maxn];//顶标 bool usex[maxn],usey[maxn];//本回合使用的x，y int link[maxn];//link[i]=x代表：在y图中的i与x相连 void init() { for(int i=0;i<=n;++i) for(int j=0;j<=n;++j) w[i][j]=-INF; //初始为负 } bool dfs(int u){ usex[u]=1; for(int i=1;i<=m;i++) if(!usey[i]&&cx[u]+cy[i]==w[u][i]){ usey[i]=1; if(link[i]==-1||dfs(link[i])){ link[i]=u; return true; } } return false; } int KM(){ memset(cy,0,sizeof(cy)); memset(cx,-1,sizeof(cx)); memset(link,-1,sizeof(link)); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) cx[i]=max(cx[i],w[i][j]); for(int i=1;i<=n;i++){ while(1){ int d=INF; memset(usex,0,sizeof(usex)); memset(usey,0,sizeof(usey)); if(dfs(i))break; for(int i=1;i<=n;i++) if(usex[i]) for(int j=1;j<=m;j++) if(!usey[j])d=min(d,cx[i]+cy[j]-w[i][j]); if(d==INF)return -1; for(int i=1;i<=n;i++) if(usex[i])cx[i]-=d; for(int i=1;i<=m;i++) if(usey[i])cy[i]+=d; } } int ans=0; for(int i=1;i<=m;i++) if(~link[i]) ans+=w[link[i]][i]; return ans; } int main(){ #ifndef ONLINE_JUDGE freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); #endif int T,N,M,u,v,tmp; scanf("%d",&T); while(T--){ scanf("%d%d",&N,&M); n=m=N; init(); for(int i=1;i<=M;++i){ scanf("%d%d%d",&u,&v,&tmp); w[u][v]=max(w[u][v],-tmp); //可能有重边，坑点 } int res=-KM(); printf("%d ",res); } return 0; }