http://acm.hdu.edu.cn/showproblem.php?pid=4862

选t<=k次，t条路要经过全部的点一次而且只一次。

建图是问题：

我自己最初就把n*m 个点分别放入X集合以及Y集合，再求最优匹配，然后连例子都过不了，并且事实上当时解释不了什么情况下不能得到结果。由于k此这个条件相当于没用上。。。

建图方法：

1、X集合和Y集合都放入n*m+k个点，X中前n*m个点和Y中前n*m个点之间。假设格子里的值相等。权就是（收益-耗费），不等就是（-耗费），由于要的是最大收益，所以初始时。全部点之间权值为-1；

  原因：例如以下图，1->2  2->3  3->1   二分图的边本身不和其它边相连，可是这种建图方式，使得能够找到连同路径1->2->3

由此学到的一种思维方式：二分图又称作二部图。是图论中的一种特殊模型。 设G=(V,E)是一个无向图。假设顶点V可切割为两个互不相交的子集(A,B)，而且图中的每条边（i。j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)。则称图G为一个二分图。可是假设两个子集是一样的。那么就能通过二分图的算法找路径或者连通分量

  

这样建图须要避免的是1->1，这样的自环的情况。导致有些点不能被覆盖，避免的方法就是初始化的时候，由于要的是最大收益。所以把自环的边初始化为最小值。

2、X中后k个点到Y中前n*m个点，权值为0。Y中后k个点到X中前n*m个点，权值也为0。增加的k个点是作为起点和终点，起点到第一个格子不须要耗费

3、X中k个点和Y中k个点一一相应的权值为0  由于同意少于k次把图遍历完毕。k个点中，有自环，说明这次不须要用

建图说的应该够清了，以后复习也好用

帖代码：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;#define rep(i,s,e) for(int i=s;i
          
           =0?x:-x;}bool path(int u){ sx[u]=true; rep(v,0,n) if(!sy[v] && lx[u]+ly[v]==mat[u][v]) { sy[v]=1; if(match[v]==-1 || path(match[v])) { match[v]=u; return true; } } return false;}int KM(){ rep(i,0,n) { lx[i]=-INF; ly[i]=0; rep(j,0,n) { lx[i]=max(lx[i],mat[i][j]); } } memset(match, 0xff, sizeof(match)); rep(u,0,n) { while(1) { memset(sx,0,sizeof(sx)); memset(sy,0,sizeof(sy)); if(path(u))break; int dmin=INF; rep(i,0,n) if(sx[i]) rep(j,0,n) if(!sy[j]) dmin=min(lx[i]+ly[j]-mat[i][j],dmin); rep(i,0,n) { if(sx[i]) lx[i]-=dmin; if(sy[i]) ly[i]+=dmin; } } } int sum=0; rep(j,0,n) { if(mat[match[j]][j] == -INF)return -INF; sum+=mat[match[j]][j]; } return sum;}void init(int nn, int mm,int kk){ for(int i=0;i
          
         
        
       
      
     

} else { mat[i*mm+j][ii*mm+j]=-ABS(i-ii)+1; } } } } int main() { //freopen("hdu4862.txt","r",stdin); //freopen("out.txt","w",stdout); int ncase; int nn,kk,mm; scanf("%d",&ncase); for(int icase=1;icase<=ncase;icase++) { scanf("%d%d%d",&nn,&mm,&kk); n=nn*mm+kk; rep(i,0,nn) { scanf("%s",line); rep(j,0,mm) { matv[i][j]=line[j]-'0'; } } init(nn,mm,kk); int ans=KM(); if(ans<=-INF)printf("Case %d : -1\n",icase); else printf("Case %d : %d\n", icase, ans); } return 0; }