模板题 超级源点-》men->house->超级汇点 坐标差值为两点的cost值 cap为1

1 #include 
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 #include
           
             7 #define INF 0xfffffff 8 using namespace std; 9 struct node 10 { 11 int u,v,next,cost,cap; 12 }edge[210000]; 13 int men[1100][2],house[1100][2],head[1100],t,dist[1100],vis[1100],pp[1100]; 14 void init() 15 { 16 t = 0; 17 memset(head,-1,sizeof(head)); 18 } 19 void add(int u,int v,int c,int p) 20 { 21 edge[t].u = u; 22 edge[t].v = v; 23 edge[t].cap = c; 24 edge[t].cost = p; 25 edge[t].next = head[u]; 26 head[u] = t++; 27 edge[t].v = u; 28 edge[t].u = v; 29 edge[t].cap = 0; 30 edge[t].cost = -p; 31 edge[t].next = head[v]; 32 head[v] = t++; 33 } 34 int spfa(int s,int en,int n) 35 { 36 int u,v,i; 37 queue
            
             q; 38 memset(vis,0,sizeof(vis)); 39 memset(pp,-1,sizeof(pp)); 40 for(i = 0 ; i <= n ; i++) 41 dist[i] = INF; 42 dist[s] = 0; 43 vis[s] = 1; 44 q.push(s); 45 while(!q.empty()) 46 { 47 u = q.front(); 48 q.pop(); 49 vis[u] = 0; 50 for(i = head[u] ; i != -1 ; i = edge[i].next) 51 { 52 v = edge[i].v; 53 if(edge[i].cap&&dist[v]>dist[u]+edge[i].cost) 54 { 55 dist[v] = dist[u]+edge[i].cost; 56 pp[v] = i; 57 if(!vis[v]) 58 { 59 vis[v] = 1; 60 q.push(v); 61 } 62 } 63 } 64 } 65 if(dist[en]==INF) 66 return 0; 67 return 1; 68 } 69 int mcmf(int s,int en,int n) 70 { 71 int i,mc=0,minf; 72 while(spfa(s,en,n)) 73 { 74 minf = INF+1; 75 for(i = pp[en] ; i != -1 ; i = pp[edge[i].u]) 76 if(minf>edge[i].cap) 77 minf = edge[i].cap; 78 for(i = pp[en]; i!=-1 ;i = pp[edge[i].u]) 79 { 80 edge[i].cap-=minf; 81 edge[i^1].cap+=minf; 82 } 83 mc+=minf*dist[en]; 84 } 85 return mc; 86 } 87 int main() 88 { 89 int i,j,k,n,m,g,o; 90 char c; 91 while(cin>>n>>m) 92 { 93 if(n==0&&m==0) 94 break; 95 o=0;g=0; 96 init(); 97 for(i = 1; i <= n ; i++) 98 { 99 getchar();100 for(j = 1; j <= m ; j++)101 {102 scanf("%c",&c);103 if(c=='m')104 {105 g++;106 men[g][0] = i;107 men[g][1] = j;108 }109 if(c=='H')110 {111 o++;112 house[o][0] = i;113 house[o][1] = j;114 }115 }116 }117 int s = 0 ,en = g+o+1;118 for( i = 1 ; i <= g ; i++)119 add(s,i,1,0);120 for(i = 1 ; i <= o ;i++)121 add(i+g,en,1,0);122 for(i = 1 ; i <= g ; i++)123 for(j = 1; j <= o ; j++)124 {125 int x = abs(men[i][0]-house[j][0])+abs(men[i][1]-house[j][1]);126 add(i,g+j,1,x);127 }128 cout<
             
              <