题意：
给出n个城市和m条路，每个城市只能经过一次，想要旅游所有的城市，求需要的最小花费（路径的长度）。
分析：
做题之前，首先要知道什么是完美匹配。不然题目做了却不知道为什么可以用这个方法来做。完美匹配｛X,Y| E｝，X、Y集合都有n个点（必须相等），它们必须一对一的匹配，并且所有点都要匹配。
对于此题，每个点都有且只有走一次。把每个点都拆为 i与 i'两个点，i值负责出边（就是i点只有出度），i'负责入边。这样就有了两个集合。集合内的点不会有联系。集合之间的点有联系，但是最后只有是一一对应的关系。
也许说得不太明白。明白了，就知道这题什么意思了。发现解题只需要用模版。
建边+ 模版。
由于最佳匹配，求出来的是边的权值和最大的匹配。而这题要求的是权值和最小。有一个常用的方法，把边权改为负的，就是直接加个负号。在模版中，因为不能匹配返回-1，为了一致性，所以改为1。最后得到的值乘以-1就是我们需要的值。
第一次做此题没有理解多少，写了题解（帮助自己理解）也没讲多少。现在重新修改，感觉自己理解得深了。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 const int N=110, INF=0x3f3f3f3f; 7 int Map[N][N],mat1[N],mat2[N];//匹配上的左右集合 8 int KM(int m,int n) 9 { 10 int s[N],t[N],a[N],b[N]; 11 int i,j,k,p,q,ans=0; 12 for(i=0;i<m;i++) 13 { 14 a[i]=-INF; 15 for(j=0;j<n;j++) 16 a[i]=Map[i][j]>a[i]?Map[i][j]:a[i]; 17 if(a[i]==-INF) return 1;//cannot match 18 } 19 memset(b,0,sizeof(b)); 20 memset(mat1,-1,sizeof(mat1)); 21 memset(mat2,-1,sizeof(mat2)); 22 for(i=0;i<m;i++) 23 { 24 memset(t,-1,sizeof(t)); 25 p=q=0; 26 for(s[0]=i;p<=q&&mat1[i]<0;p++) 27 { 28 for(k=s[p],j=0;j<n&&mat1[i]<0;j++) 29 { 30 if(a[k]+b[j]==Map[k][j]&&t[j]<0) 31 { 32 s[++q]=mat2[j]; t[j]=k; 33 if(s[q]<0) 34 for(p=j;p>=0;j=p) 35 { 36 mat2[j]=k=t[j];p=mat1[k]; mat1[k]=j; 37 } 38 } 39 } 40 } 41 if(mat1[i]<0) 42 { 43 i--,p=INF; 44 for(k=0;k<=q;k++) 45 { 46 for(j=0;j<n;j++) 47 if(t[j]<0&&a[s[k]]+b[j]-Map[s[k]][j]<p) 48 p=a[s[k]]+b[j]-Map[s[k]][j]; 49 } 50 for(j=0;j<n;j++) b[j]+=t[j]<0?0:p; 51 for(k=0;k<=q;k++) a[s[k]]-=p; 52 } 53 } 54 for(i=0;i<m;i++) ans+=Map[i][mat1[i]]; 55 return ans; 56 } 57 void init() 58 { 59 for(int i=0;i<N;i++) 60 for(int j=0;j<N;j++) 61 Map[i][j]=-INF; 62 } 63 int main() 64 { 65 //freopen("test.txt","r",stdin); 66 int n,i,j,m,k; 67 while(scanf("%d%d",&n,&m)!=EOF) 68 { 69 init(); 70 while(m--) 71 { 72 scanf("%d%d%d",&i,&j,&k); 73 i--;j--;k=-k; 74 Map[i][j]=max(Map[i][j],k); 75 } 76 printf("%d ",-1*KM(n,n)); 77 } 78 return 0; 79 }