(网络流匹配 KM) Going Home --poj -- 2195-白红宇

(网络流匹配 KM) Going Home --poj -- 2195

阅读量：6587 次

发布时间：2019-06-24

本文共 2177 字，大约阅读时间需要 7 分钟。

链接：

有n个人有n栋房子，每栋房子里能进一个人，但每走一格的价值是1，所以要尽可能的少走，这一看很显然是匹配用KM算法，

但这是网络流专题的，不是太懂怎么用网络流来写

代码：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;#define N 110#define INF 0x3fffffffstruct node{
   int x, y, step;};char G[N][N];int n, m1, dir[4][2]={
   {-1,0},{
   1,0},{
   0,-1},{
   0,1}};int STEP[N][N], m[N][N], H[N][N], vis[N][N];int  num1, num2, lx[N], ly[N];int  used[N], visx[N], visy[N], s[N];void BFS(node p){    node q, t;    queue
          
           Q; Q.push(p); memset(vis, 0, sizeof(vis)); vis[p.x][p.y] = 1; while(Q.size()) { q = Q.front(); Q.pop(); if(G[q.x][q.y]=='H') STEP[m[p.x][p.y]][H[q.x][q.y]] = -q.step; for(int i=0; i<4; i++) { t.x = q.x + dir[i][0]; t.y = q.y + dir[i][1]; t.step = q.step + 1; if(t.x>=0 && t.x
           
            =0 && t.y

粘个别人的代码：

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;const int MAXN = 407;const int oo = 1e9+7;struct point{ int x, y;}man[MAXN], house[MAXN];struct Graph{ int flow, cost;}G[MAXN][MAXN];int NX, NY, start, End;///男人和房子的数目,源点和汇点bool spfa(int pre[]){ stack
           
             sta; int instack[MAXN]={ 0}, dist[MAXN]; for(int i=1; i<=End; i++) dist[i] = oo; dist[start] = 0; sta.push(start); while(sta.size()) { int u = sta.top();sta.pop(); instack[u] = false; for(int i=1; i<=End; i++) { if(G[u][i].flow && dist[i] > dist[u]+G[u][i].cost) { dist[i] = dist[u] + G[u][i].cost; pre[i] = u; if(instack[i] == false) { sta.push(i); instack[i] = true; } } } } return dist[End] != oo;}int MinCost(){ int i, pre[MAXN], cost=0; while(spfa(pre) == true) { ///如果有增广路 int MinFlow = oo; for(i=End; i != start; i=pre[i]) MinFlow = min(MinFlow, G[pre[i]][i].flow); for(i=End; i != start; i=pre[i]) { ///逆向访问这条增广路上的每条边 int k = pre[i]; G[k][i].flow -= MinFlow; G[i][k].flow += MinFlow; cost += G[k][i].cost; } } return cost;}int main(){ int M, N; while(scanf("%d%d", &M, &N), M+N) { int i, j;char s[MAXN][MAXN]; memset(G, 0, sizeof(G)); NX = NY = 0; for(i=0; i