poj 2195 二分图带权匹配+最小费用最大流

题意：有一个矩阵，某些格有人，某些格有房子，每个人可以上下左右移动，问给每个人进一个房子，所有人需要走的距离之和最小是多少。

貌似以前见过很多这样类似的题，都不会，现在知道是用KM算法做了

KM算法目前还没弄懂，先套模板做

Sample Input

2 2
.m
H.
5 5
HH..m
.....
.....
.....
mm..H
7 8
...H....
...H....
...H....
mmmHmmmm
...H....
...H....
...H....
0 0

Sample Output

2
10
28


  1 #include<stdio.h>
  2 #include<iostream>
  3 #include<string.h>
  4 #include<algorithm>
  5 #include<math.h>
  6 using namespace std;
  7 const int MAXN=120;
  8 const int INF=0x3fffffff;
  9 int g[MAXN][MAXN],match1[MAXN],match2[MAXN];
 10 int KM(int m,int n)
 11 {
 12     int i,j,k,p,q;
 13     int l1[MAXN],l2[MAXN];
 14     int s[MAXN],t[MAXN];
 15     int ret=0;
 16     for(i=0;i<m;i++)
 17     {
 18         l1[i]=-INF;
 19         for(j=0;j<n;j++)
 20           if(g[i][j]>l1[i])
 21              l1[i]=g[i][j];
 22         if(l1[i]==-INF) return -1;//无法匹配
 23     }
 24     for(i=0;i<n;i++)l2[i]=0;
 25 
 26     memset(match1,-1,sizeof(match1));
 27     memset(match2,-1,sizeof(match2));
 28     for(i=0;i<m;i++)
 29     {
 30         memset(t,-1,sizeof(t));
 31         for(s[p=q=0]=i;p<=q&&match1[i]<0;p++)
 32             for(k=s[p],j=0;j<n&&match1[i]<0;j++)
 33                 if(l1[k]+l2[j]==g[k][j]&&t[j]<0)
 34                 {
 35                     s[++q]=match2[j],t[j]=k;
 36                     if(s[q]<0)
 37                       for(p=j;p>=0;j=p)
 38                          match2[j]=k=t[j],p=match1[k],match1[k]=j;
 39                 }
 40 
 41         if(match1[i]<0)
 42         {
 43             for(i--,p=INF,k=0;k<=q;k++)
 44                for(j=0;j<n;j++)
 45                  if(t[j]<0&&l1[s[k]]+l2[j]-g[s[k]][j]<p)
 46                      p=l1[s[k]]+l2[j]-g[s[k]][j];
 47 
 48 
 49             for(j=0;j<n;j++)if(t[j]>=0)l2[j]+=p;
 50             for(k=0;k<=q;k++)l1[s[k]]-=p;
 51         }
 52     }
 53     for(i=0;i<m;i++)
 54     {
 55         if(match1[i]<0)return -1;//无法匹配
 56         if(g[i][match1[i]]<=-INF)return -1;
 57         ret+=g[i][match1[i]];
 58     }
 59     return ret;
 60 }
 61 struct Node
 62 {
 63     int x,y;
 64 };
 65 Node node1[MAXN],node2[MAXN];
 66 char str[MAXN];
 67 int main()
 68 {
 69     int n,m;
 70     int nx,ny;
 71     while(scanf("%d%d",&n,&m)!=EOF)
 72     {
 73         if(n==0&&m==0)break;
 74         nx=0;
 75         ny=0;
 76         for(int i=0;i<n;i++)
 77         {
 78             scanf("%s",&str);
 79             for(int j=0;j<m;j++)
 80             {
 81                 if(str[j]=='m')
 82                 {
 83                     node1[nx].x=i;
 84                     node1[nx].y=j;
 85                     nx++;
 86                 }
 87                 else if(str[j]=='H')
 88                 {
 89                     node2[ny].x=i;
 90                     node2[ny].y=j;
 91                     ny++;
 92                 }
 93             }
 94         }
 95         for(int i=0;i<nx;i++)
 96         for(int j=0;j<ny;j++)
 97         {
 98             g[i][j]=-abs(node1[i].x-node2[j].x)-abs(node1[i].y-node2[j].y);
 99         }
100         printf("%d
",-KM(nx,ny));
101     }
102     return 0;
103 }
  1 /*
  2 POJ 2195 Going Home
  3 邻接矩阵形式最小费用最大流
  4 */
  5 
  6 #include<stdio.h>
  7 #include<iostream>
  8 #include<algorithm>
  9 #include<string.h>
 10 #include<queue>
 11 using namespace std;
 12 
 13 
 14 //************************************************************
 15 //最小费用最大流算法
 16 //SPFA求最短路
 17 //邻接矩阵形式
 18 //初始化:cap:容量，没有边为0
 19 //cost:耗费，对称形式，没有边的也为0
 20 //c是最小费用
 21 //f是最大流
 22 //*******************************************************
 23 const int MAXN=500;
 24 const int INF=0x3fffffff;
 25 int cap[MAXN][MAXN];//容量，没有边为0
 26 int flow[MAXN][MAXN];
 27 //耗费矩阵是对称的，有i到j的费用，则j到i的费用为其相反数
 28 int cost[MAXN][MAXN];
 29 
 30 
 31 int n;//顶点数目0~n-1
 32 int f;//最大流
 33 int c;//最小费用
 34 int start,end;//源点和汇点
 35 
 36 bool vis[MAXN];//在队列标志
 37 int que[MAXN];
 38 int pre[MAXN];
 39 int dist[MAXN];//s-t路径最小耗费
 40 bool SPFA()
 41 {
 42     int front=0,rear=0;
 43     for(int u=0;u<=n;u++)
 44     {
 45         if(u==start)
 46         {
 47             que[rear++]=u;
 48             dist[u]=0;
 49             vis[u]=true;
 50         }
 51         else
 52         {
 53             dist[u]=INF;
 54             vis[u]=false;
 55         }
 56     }
 57     while(front!=rear)
 58     {
 59         int u=que[front++];
 60         vis[u]=false;
 61         if(front>=MAXN)front=0;
 62         for(int v=0;v<=n;v++)
 63         {
 64             if(cap[u][v]>flow[u][v]&&dist[v]>dist[u]+cost[u][v])
 65             {
 66                 dist[v]=dist[u]+cost[u][v];
 67                 pre[v]=u;
 68                 if(!vis[v])
 69                 {
 70                     vis[v]=true;
 71                     que[rear++]=v;
 72                     if(rear>=MAXN)rear=0;
 73                 }
 74             }
 75         }
 76     }
 77     if(dist[end]>=INF)return false;
 78     return true;
 79 }
 80 
 81 void minCostMaxflow()
 82 {
 83     memset(flow,0,sizeof(flow));
 84     c=f=0;
 85     while(SPFA())
 86     {
 87         int Min=INF;
 88         for(int u=end;u!=start;u=pre[u])
 89            Min=min(Min,cap[pre[u]][u]-flow[pre[u]][u]);
 90         for(int u=end;u!=start;u=pre[u])
 91         {
 92             flow[pre[u]][u]+=Min;
 93             flow[u][pre[u]]-=Min;
 94         }
 95         c+=dist[end]*Min;
 96         f+=Min;
 97     }
 98 }
 99 //************************************************************
100 
101 struct Node
102 {
103     int x,y;
104 };
105 Node node1[MAXN],node2[MAXN];
106 char str[MAXN][MAXN];
107 int main()
108 {
109     //freopen("in.txt","r",stdin);
110     //freopen("out.txt","w",stdout);
111     int N,M;
112     while(scanf("%d%d",&N,&M))
113     {
114         if(N==0&&M==0)break;
115         int tol1=0,tol2=0;
116         for(int i=0;i<N;i++)
117         {
118             scanf("%s",&str[i]);
119             for(int j=0;j<M;j++)
120             {
121                 if(str[i][j]=='m')
122                 {
123                     tol1++;
124                     node1[tol1].x=i;
125                     node1[tol1].y=j;
126                 }
127                 else if(str[i][j]=='H')
128                 {
129                     tol2++;
130                     node2[tol2].x=i;
131                     node2[tol2].y=j;
132                 }
133             }
134         }
135         start=0;
136         n=tol1+tol2+1;
137         end=tol1+tol2+1;
138         memset(cap,0,sizeof(cap));
139         memset(cost,0,sizeof(cost));
140         for(int i=1;i<=tol1;i++)
141         {
142             cost[0][i]=cost[i][0]=0;
143             cap[0][i]=1;
144         }
145         for(int i=1;i<=tol2;i++)
146         {
147             cost[tol1+i][end]=0;
148             cap[tol1+i][end]=1;
149         }
150         for(int i=1;i<=tol1;i++)
151           for(int j=1;j<=tol2;j++)
152           {
153               cost[i][tol1+j]=abs(node1[i].x-node2[j].x)+abs(node1[i].y-node2[j].y);
154               cost[tol1+j][i]=-cost[i][tol1+j];
155               cap[i][tol1+j]=1;
156           }
157         minCostMaxflow();
158         printf("%d
",c);
159     }
160     return 0;
161 }
  1 /*
  2 POJ 2195 Going Home
  3 邻接表形式最小费用最大流
  4 */
  5 
  6 #include<stdio.h>
  7 #include<iostream>
  8 #include<algorithm>
  9 #include<string.h>
 10 #include<queue>
 11 using namespace std;
 12 
 13 const int MAXN=1000;
 14 const int MAXE=100000;
 15 const int INF=0x3f3f3f3f;
 16 struct Edge
 17 {
 18     int from;
 19     int to;
 20     int next;
 21     int re;//记录逆边的下标
 22     int cap;//容量
 23     int cost;//费用
 24 }edge[MAXE];
 25 int pre[MAXN];
 26 int head[MAXN];
 27 bool vis[MAXN];
 28 int que[MAXN];
 29 int dist[MAXN];
 30 int tol;//边的总数
 31 void add(int u,int v,int ca,int co)
 32 {
 33     edge[tol].from=u;
 34     edge[tol].to=v;
 35     edge[tol].cap=ca;
 36     edge[tol].cost=co;
 37     edge[tol].re=tol+1;
 38     edge[tol].next=head[u];
 39     head[u]=tol++;
 40 
 41     edge[tol].from=v;//加逆边
 42     edge[tol].to=u;
 43     edge[tol].cap=0;
 44     edge[tol].cost=-co;
 45     edge[tol].re=tol-1;
 46     edge[tol].next=head[v];
 47     head[v]=tol++;
 48 }
 49 int n;
 50 int start;
 51 int end;
 52 bool SPFA()
 53 {
 54     int front=0,rear=0;
 55     for(int v=0;v<=n;v++)
 56     {
 57         if(v==start)
 58         {
 59             que[rear++]=v;
 60             vis[v]=true;
 61             dist[v]=0;
 62         }
 63         else
 64         {
 65             dist[v]=INF;
 66             vis[v]=false;
 67         }
 68     }
 69     while(front!=rear)
 70     {
 71         int u=que[front++];
 72         vis[u]=false;
 73         if(front>=MAXN)front=0;
 74         for(int i=head[u];i!=-1;i=edge[i].next)
 75         {
 76             int v=edge[i].to;
 77             if(edge[i].cap&&dist[v]>dist[u]+edge[i].cost)
 78             {
 79                 dist[v]=dist[u]+edge[i].cost;
 80                 pre[v]=i;
 81                 if(!vis[v])
 82                 {
 83                     que[rear++]=v;
 84                     vis[v]=true;
 85                     if(rear>=MAXN)rear=0;
 86                 }
 87             }
 88         }
 89     }
 90     if(dist[end]==INF)return false;
 91     return true;
 92 }
 93 int c;//费用
 94 int f;//最大流
 95 
 96 void minCostMaxflow()
 97 {
 98     c=f=0;
 99     int u,p;
100     while(SPFA())
101     {
102         int Min=INF;
103         for(u=end;u!=start;u=edge[p].from)
104         {
105             p=pre[u];
106             Min=min(Min,edge[p].cap);
107         }
108         for(u=end;u!=start;u=edge[p].from)
109         {
110             p=pre[u];
111             edge[p].cap-=Min;
112             edge[edge[p].re].cap+=Min;
113 
114         }
115         c+=dist[end]*Min;
116         f+=Min;
117     }
118 }
119 
120 
121 struct Node
122 {
123     int x,y;
124 };
125 Node node1[MAXN],node2[MAXN];
126 char str[MAXN][MAXN];
127 int main()
128 {
129    // freopen("in.txt","r",stdin);
130     //freopen("out.txt","w",stdout);
131     int N,M;
132     while(scanf("%d%d",&N,&M))
133     {
134         if(N==0&&M==0)break;
135         int tol1=0,tol2=0;
136         for(int i=0;i<N;i++)
137         {
138             scanf("%s",&str[i]);
139             for(int j=0;j<M;j++)
140             {
141                 if(str[i][j]=='m')
142                 {
143                     tol1++;
144                     node1[tol1].x=i;
145                     node1[tol1].y=j;
146                 }
147                 else if(str[i][j]=='H')
148                 {
149                     tol2++;
150                     node2[tol2].x=i;
151                     node2[tol2].y=j;
152                 }
153             }
154         }
155         start=0;
156         n=tol1+tol2+1;
157         end=tol1+tol2+1;
158 
159         //加边之前一定要初始化
160         tol=0;//边数
161         memset(head,-1,sizeof(head));//一定要初始化为-1
162 
163 
164         for(int i=1;i<=tol1;i++)
165         {
166             add(0,i,1,0);
167         }
168         for(int i=1;i<=tol2;i++)
169         {
170             add(tol1+i,end,1,0);
171         }
172         for(int i=1;i<=tol1;i++)
173           for(int j=1;j<=tol2;j++)
174           {
175               int temp=abs(node1[i].x-node2[j].x)+abs(node1[i].y-node2[j].y);
176               add(i,tol1+j,1,temp);
177           }
178         minCostMaxflow();
179         printf("%d
",c);
180     }
181     return 0;
182 }
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/cnblogs321114287/p/4314645.html