题意：
给定n*m的矩阵 （最大100*100）
.为空地 H为房子 m为人 （题目保证 H的个数<=100 && H = m）
一个房子只能住一个人
问：让每个人回到任意一个房子使得所有人需要步数最少，问最少需要多少步。
思路：
费用流，虚拟源点与人建边 费用为0， 一个人与所有房子建边，费用为步数， 房子与汇点建边费用为0
所有边流限为1
#include#include #include #include #include #include #include #include #define N 10001 #define M 101000 #define inf 107374182 #define ll int using namespace std; //双向边，注意RE 注意这个模版是 相同起末点的边 合并而不是去重 //注意 起点<终点&&终点必须为最大点标 && 点标不要太分散 struct Edge{ int from, to, flow, cap, nex, cost; }edge[M*2]; int head[N], edgenum; void addedge(int u,int v,int cap,int cost){//网络流要加反向弧 Edge E={u, v, 0, cap, head[u], cost}; edge[edgenum]=E; head[u]=edgenum++; Edge E2={v, u, 0, 0, head[v], -cost}; //这里的cap若是单向边要为0 edge[edgenum]=E2; head[v]=edgenum++; } int D[N], P[N], A[N]; bool inq[N]; bool BellmanFord(int s, int t, int &flow, int &cost){ for(int i=0;i<=t;i++) D[i]= inf; memset(inq, 0, sizeof(inq)); D[s]=0; inq[s]=1; P[s]=0; A[s]=inf; queue Q; Q.push( s ); while( !Q.empty()){ int u = Q.front(); Q.pop(); inq[u]=0; for(int i=head[u]; i!=-1; i=edge[i].nex){ Edge &E = edge[i]; if(E.cap > E.flow && D[E.to] > D[u] +E.cost){ D[E.to] = D[u] + E.cost ; P[E.to] = i; A[E.to] = min(A[u], E.cap - E.flow); if(!inq[E.to]) Q.push(E.to) , inq[E.to] = 1; } } } if(D[t] == inf) return false; flow += A[t]; cost += D[t] * A[t]; int u = t; while(u != s){ edge[P[u]].flow += A[t]; edge[P[u]^1].flow -= A[t]; u = edge[P[u]].from; } return true; } int Mincost(int s,int t){ int flow = 0, cost = 0; while(BellmanFord(s, t, flow, cost)); return cost; } int n, m; int idx(int x, int y){ return x*m+y; } char s[105][105]; struct node{ int x, y; node(int a=0,int b=0):x(a),y(b){} int idx(){return x*m+y;} }Home[105], Man[105]; int dis(node a,node b){return abs(a.x-b.x)+abs(a.y-b.y);} int main(){ int i, j; while( scanf("%d %d",&n, &m), n+m){ memset(head,-1,sizeof(head)); edgenum=0; for(i = 1; i <= n; i++)scanf("%s", s[i]+1); int Start = 0, End = idx(n,m)+1; int topH = 0, topM = 0; for(i = 1; i <= n; i++) { for(j = 1; j <= m; j++) if(s[i][j] == 'H') { Home[topH++] = node(i,j); addedge(Start, idx(i,j), 1, 0);} else if(s[i][j] == 'm') { Man[topM++] = node(i,j); addedge(idx(i,j), End, 1, 0);} } for(i = 0; i < topH; i++) { for(j = 0; j < topM; j++) { node home = Home[i], man = Man[j]; addedge(home.idx(), man.idx(), 1, dis(home, man)); } } printf("%d\n",Mincost(Start, End) ); } return 0; } /* 2 2 .m H. 5 5 HH..m ..... ..... ..... mm..H 7 8 ...H.... ...H.... ...H.... mmmHmmmm ...H.... ...H.... ...H.... */