题目链接
Cyclic Tour HDU - 1853
题意
我国有N个城市，并且有M条单向路连接着城市。小汤姆要做几个环游旅行计划，要求计划满足每个环游至少包含两个城市，每个城市恰好出现一次。给定M条路的距离，求旅行完后走的最小距离。
分析
注意到题干信息“每个城市恰好出现一次”，用图论术语表示等价为“每个点恰好有一个入度和一个出度”。现在N个点已经给你了，要连N条边使得每个点恰好有一个入度和一个出度。
将N个城市作为左侧顶点集，同时将N个城市复制一份作为右侧顶点集，根据M条单向路去连边，边的权值为距离的相反数。如此建立一个完全二分图后，跑一遍KM算法看是否存在完备匹配，如果存在，则输出最大权的相反数；否则输出-1。
代码
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#define INF 0x3f3f3f3f
using namespace std;const int maxn=110;
int w[maxn][maxn],from[maxn];
int lx[maxn],ly[maxn],visx[maxn],visy[maxn];
int nx,ny,slack[maxn];bool Find(int u)
{visx[u]=1;for(int v=1;v<=ny;v++)if(!visy[v]){int tmp=lx[u]+ly[v]-w[u][v];if(tmp==0){visy[v]=1;if(from[v]==-1 || Find(from[v])){from[v]=u;return true;}}else slack[v]=min(slack[v],tmp);}return false;
}
int KM()
{memset(ly,0,sizeof(ly));for(int i=1;i<=nx;i++){lx[i]=-INF;for(int j=1;j<=ny;j++)lx[i]=max(lx[i],w[i][j]);}memset(from,-1,sizeof(from));for(int u=1;u<=nx;u++){memset(slack,0x3f,sizeof(slack));while(true){memset(visx,0,sizeof(visx));memset(visy,0,sizeof(visy));if(Find(u)) break;int d=INF;for(int i=1;i<=ny;i++)if(!visy[i])d=min(d,slack[i]);for(int i=1;i<=nx;i++)if(visx[i])lx[i]-=d;for(int i=1;i<=ny;i++){if(visy[i]) ly[i]+=d;else slack[i]-=d;}}}int ans=0;for(int i=1;i<=ny;i++){if(from[i]!=-1){int val=w[from[i]][i];if(val==-INF) return 1;ans+=val;}else return 1;}return ans;
}
int main()
{int n,m;while(~scanf("%d%d",&n,&m)){nx=ny=n;for(int i=1;i<=nx;i++)for(int j=1;j<=ny;j++)w[i][j]=-INF;for(int i=0;i<m;i++){int u,v,val;scanf("%d%d%d",&u,&v,&val);w[u][v]=max(-val,w[u][v]);//重边的处理}printf("%d\n",-KM());}return 0;
}
参考博客
模板总结——二分图最大权匹配