刚读的时候以为是Optimal Milking那道题，但实际上不是的；但借此我也想清了一些东西。

optimal milking里面问的是走的最远的那头奶牛最少走多少，对应到这道题里就是走的最远的people最少走多少；若是这样的话就得二分找可行流了，不然的话没有办法建图。（几乎一样的题稍微问了个不一样的东西，就从原本用最大流解变成用费用流解，让我觉得很奇妙）

这里面问的一共最少走多少，那就是费用流了。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #define INF 2e9using namespace std;int T,ans;struct edge{    int v,cap,reverse,cost;};vector
          
            edges[1005];//邻接表 vector
           
             bian;//所有的边都存在里面vector< pair
            
              > people,house;char maze[105][105];void addedge(int u,int v,int cost,int cap){ //u到v一条边，再加一条反向边 edge e; e.cap=cap; e.v=v; e.cost=cost; e.reverse=bian.size()+1;//这条边的反边将建在这条边之后（这条边建完后在bian.size()的位置） bian.push_back(e); edges[u].push_back(bian.size()-1); e.cap=0; e.v=u; e.cost=-cost; e.reverse=bian.size()-1; bian.push_back(e); edges[v].push_back(bian.size()-1);}int dist[1005],pre[1005];//pre[i]代表走的哪条边到的i点 bool spfa(){ for(int i=0;i<=T;i++) dist[i]=INF; for(int i=0;i<=T;i++) pre[i]=-1; deque
             
               q; dist[0]=0; pre[0]=-1; q.push_back(0); while( !q.empty() ){ int u = q.front(); q.pop_front(); for(int i=0;i
              
               0 && dist[u]+e.cost
               
                >n>>m; if(n==0 && m==0) break; bian.clear(); people.clear(); house.clear(); for(int i=0;i<=T;i++) edges[i].clear(); ans=0; //people:1-n house: n+1 - 2*n for(int i=1;i<=n;i++) for(int j=1;j<=m;j++){ cin>>maze[i][j]; if( maze[i][j]=='H' ) house.push_back( make_pair(i,j) ); else if( maze[i][j]=='m' ) people.push_back( make_pair(i,j) ); } //people向house建边 费用流 for(int i=0;i