对于二分图的最大匹配和对于带权二分图的最优匹配，B站上
CSU ACM—ICPC 的大佬们讲的已经很清楚了。
有需求的同学们可以去B站上学习一下。
悄悄说一声，讲课的陈佳妮小姐姐也曾经是位OIer，曾在CTSC2016上夺得银牌（因为在HN，好像没能去成NOI），讲解的方式也令OIers十分舒适。
题目大意：给一张有向图，要求选择任意多个环（可重复，非自环，环可以任选，不用相连），使得每个点都被访问过，而且经过的边权之和最小，求最小值。
乍一看和二分图没有关系，但是仔细想一下，如果给图中每个点拆成两个（一个连接这个点的入点，一个连出点），那么因为要走环，那么最优情况肯定是每个环中有一个点会被访问两次，其他点都是一次，那这不就是赤果果的在拆点图上求最优匹配吗？
假设我们有一张图：1——>2——>3——>1,设拆出来的点i，用来连接入点的是i，连接出点的是i+n(此处n=4)，那么我们拆点图长这样：5——>2，6——>3,
7——>1,这样就实际上是对拆出来的六个点进行了一次完全匹配。
那么，我们只要先判断拆点图能不能形成完美匹配，然后再跑一边KM就可以了（KM算法要求二分图存在完美匹配，否则会陷入死循环）。
放代码吧：
#include<iostream> #include<cstdio> #include<vector> #include<algorithm> #include<cstring> using namespace std; vector<int>b[101]; int n,m; struct PE { int s,t,val; }; PE E[20001]; int mp[101][101]; bool Function(PE x,PE y) { return x.val<y.val; } int QWx[101],QWy[101],use[101],pre[101],stx[101]; int visx[101],visy[101],fpre[101]; bool Hungary(int x) { int temp=0; visx[x]=1; for(int i=0;i<b[x].size();i++) { int to=b[x][i]; if(visy[to]) { continue; } temp=QWx[x]+QWy[to]-mp[x][to]; if(temp==0) { visy[to]=1; if(pre[to]==0||Hungary(pre[to])) { fpre[x]=to; pre[to]=x; return 1; } } else stx[to]=min(stx[to],temp); } return 0; } bool PDHungary(int x) { for(int i=0;i<b[x].size();i++) { int to=b[x][i]; if(visy[to]) continue; visy[to]=1; if(pre[to]==0||PDHungary(pre[to])) { pre[to]=x; return 1; } } return 0; } void KM() { for(int i=1;i<=n;i++) { memset(stx,0x3f3f3f3f,sizeof(stx)); while(1) { memset(visx,0,sizeof(visx)); memset(visy,0,sizeof(visy)); if(Hungary(i)) { break; } else { int date=0x3f3f3f3f; for(int j=1;j<=n;j++) { if(!visy[j]) date=min(date,stx[j]); } for(int j=1;j<=n;j++) { if(visx[j]) QWx[j]-=date; if(visy[j]) QWy[j]+=date; else stx[j]-=date; } } } } } int LINYIN() { //scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { b[i].clear(); } int ans=0; memset(mp,-0x3f3f3f3f,sizeof(mp)); memset(QWx,-0x3f3f3f3f,sizeof(QWx)); memset(QWy,0,sizeof(QWy)); memset(pre,0,sizeof(pre)); for(int i=1;i<=m;i++) { scanf("%d%d%d",&E[i].s,&E[i].t,&E[i].val); E[i].val*=-1; } sort(E+1,E+1+m,Function); mp[E[1].s][E[1].t]=E[1].val; b[E[1].s].push_back(E[1].t); for(int i=2;i<=m;i++) { if(E[i].s==E[i-1].s&&E[i].t==E[i-1].t&&E[i].val==E[i-1].val) continue; mp[E[i].s][E[i].t]=max(mp[E[i].s][E[i].t],E[i].val); b[E[i].s].push_back(E[i].t); QWx[E[i].s]=max(QWx[E[i].s],E[i].val); } for(int i=1;i<=n;i++) { memset(visy,0,sizeof(visy)); if(!PDHungary(i)) { printf("%d ",-1); return 0; } } memset(pre,0,sizeof(pre)); memset(visy,0,sizeof(visy)); KM(); for(int i=1;i<=n;i++) { ans+=mp[pre[i]][i]; } ans*=-1; printf("%d ",ans); return 0; } int main() { while(scanf("%d%d",&n,&m)!=EOF) { LINYIN(); } return 0; }
完结撒花！