题意: 有N个点，M个单向边,现在要你设计N条路线覆盖所有的点,每个点都属于且值属于一个环。（为什么是N条边：和最小生成树为什么有N-1条边是一样的证明）。
解析： 每个点都有一个喜欢对象（出度）和被喜欢对象（入度）,故将一个点拆成男点和女点,然后用最佳匹配即可!
坑die：有重边！MMP
相似的题目：1853 3435
（好像还可以用网络流来解决，容我想两天）
HDU3844
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<memory.h>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=310;
const int inf=0x7ffffff;
int map[maxn][maxn];
int vis1[maxn],vis2[maxn];
int ex1[maxn],ex2[maxn];
int lack[maxn];
int link[maxn];
int ans,n;
int x1[maxn],x2[maxn],y[maxn],y2[maxn];
int Abs(int v){
if(v<0) v=-v;
return v;
}
bool _bfs(int v)
{
vis1[v]=true;
for(int i=1;i<=n;i++){
if(!vis2[i]){
int tmp=ex1[v]+ex2[i]-map[v][i];
if(tmp==0){
vis2[i]=true;
if(!link[i]||_bfs(link[i])){
link[i]=v;
return true;
}
}
else if(tmp<lack[i]) lack[i]=tmp;
}
}
return false;
}
void _KM()
{
int t,i,j;
memset(link,0,sizeof(link));
memset(ex2,0,sizeof(ex2));
for(i=1;i<=n;i++){
ex1[i]=map[i][1];
for(j=2;j<=n;j++)
if(ex1[i]<map[i][j]) ex1[i]=map[i][j];
}
for(t=1;t<=n;t++){
for(i=1;i<=n;i++) lack[i]=inf;
while(true){
memset(vis1,0,sizeof(vis1));
memset(vis2,0,sizeof(vis2));
if(_bfs(t)) break;
int gap=inf;
for(i=1;i<=n;i++)
if(!vis2[i]&&lack[i]<gap) gap=lack[i];
for(i=1;i<=n;i++) if(vis1[i]) ex1[i]-=gap;
for(i=1;i<=n;i++) if(vis2[i]) ex2[i]+=gap;
for(i=1;i<=n;i++) if(!vis2[i])lack[i]-=gap;
}
}
ans=0;
for(i=1;i<=n;i++)
ans-=map[link[i]][i];
ans=ans;
printf("%d
",ans);
}
int main()
{
int i,j,m,T,u,v,w;
scanf("%d",&T);
while(T--){
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
for(j=1;j<=n;j++) map[i][j]=inf;
for(i=1;i<=m;i++){
scanf("%d%d%d",&u,&v,&w);
if(w<map[u][v]) map[u][v]=w;//消灭重边
}
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)map[i][j]=-map[i][j];
_KM();
}
return 0;
}
HDU1853 ：普通匈牙利算法算是否false得到-1 。
或者直接KM，若有map[link[i]][i]=-inf，即匹配到不存在的边，也得到-1.
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<memory.h>
#include<algorithm>
#include<cmath>
using namespace std;
const int maxn=310;
const int inf=0x7ffffff;
int map[maxn][maxn];
int vis1[maxn],vis2[maxn];
int ex1[maxn],ex2[maxn];
int lack[maxn];
int link[maxn];
int ans,n;
bool _bfs2(int v)
{
vis1[v]=true;
for(int i=1;i<=n;i++){
if(!vis2[i]&&-map[v][i]!=inf){
vis2[i]=true;
if(!link[i]||_bfs2(link[i])){
link[i]=v;
return true;
}
}
}
return false;
}
bool _bfs(int v)
{
vis1[v]=true;
for(int i=1;i<=n;i++){
if(!vis2[i]){
int tmp=ex1[v]+ex2[i]-map[v][i];
if(tmp==0){
vis2[i]=true;
if(!link[i]||_bfs(link[i])){
link[i]=v;
return true;
}
}
else if(tmp<lack[i]) lack[i]=tmp;
}
}
return false;
}
void _KM()
{
int t,i,j;
memset(link,0,sizeof(link));
for(i=1;i<=n;i++){
memset(vis2,0,sizeof(vis2));
if(!_bfs2(i)){
printf("-1
");
return ;
}
}
memset(link,0,sizeof(link));
memset(ex2,0,sizeof(ex2));
for(i=1;i<=n;i++){
ex1[i]=map[i][1];
for(j=2;j<=n;j++)
if(ex1[i]<map[i][j]) ex1[i]=map[i][j];
}
for(t=1;t<=n;t++){
for(i=1;i<=n;i++) lack[i]=inf;
while(true){
memset(vis1,0,sizeof(vis1));
memset(vis2,0,sizeof(vis2));
if(_bfs(t)) break;
int gap=inf;
for(i=1;i<=n;i++)
if(!vis2[i]&&lack[i]<gap) gap=lack[i];
for(i=1;i<=n;i++) if(vis1[i]) ex1[i]-=gap;
for(i=1;i<=n;i++) if(vis2[i]) ex2[i]+=gap;
for(i=1;i<=n;i++) if(!vis2[i])lack[i]-=gap;
}
}
ans=0;
for(i=1;i<=n;i++){
ans-=map[link[i]][i];
}
printf("%d
",ans);
}
int main()
{
int i,j,m,T,u,v,w;
while(~scanf("%d%d",&n,&m))
{
for(i=1;i<=n;i++)
for(j=1;j<=n;j++) map[i][j]=inf;
for(i=1;i<=m;i++){
scanf("%d%d%d",&u,&v,&w);
if(w<map[u][v]) map[u][v]=w;//消灭重边
}
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)map[i][j]=-map[i][j];
_KM();
}
return 0;
}