题意：给你一张图，有k个人和k个房子，每个房子只能住一个人，每个人到某一房子的花费为曼哈顿距离，问你让k个人怎么走，使他们都住房子且花费最小。
思路：我们把所有人和超级源点相连，流量为1花费为0，所有房子和超级汇点相连，流量为1花费为0，然后把所有人和所有房子加边，流量为1，花费为曼哈顿距离，这样这道题目就变成了求超级源点到超级汇点的MCMF。
代码：
#include#include #include #include #include #include #include #include #include #define ll long longconst int maxn = 10000+5;const int maxm = 100000+5;const int MOD = 1e7;const int INF = 1 << 25;using namespace std;struct Edge{ int to,next,cap,flow,cost;}edge[maxm];struct node{ int x,y;}house[maxn],man[maxn];int head[maxn],tot;int pre[maxn],dis[maxn];bool vis[maxn];int N,M;void init(){ N = maxn; tot = 0; memset(head,-1,sizeof(head));}void addEdge(int u,int v,int cap,int cost){ edge[tot].to = v; edge[tot].cap = cap; //容量 edge[tot].flow = 0; edge[tot].cost = cost; edge[tot].next = head[u]; head[u] = tot++; edge[tot].to = u; edge[tot].cap = 0; edge[tot].flow = 0; edge[tot].cost = -cost; edge[tot].next = head[v]; head[v] = tot++;}bool spfa(int s,int t){ queue q; for(int i = 0;i < N;i++){ dis[i] = INF; vis[i] = false; pre[i] = -1; } dis[s] = 0; vis[s] = true; q.push(s); while(!q.empty()){ int u = q.front(); q.pop(); vis[u] = false; for(int i = head[u];i != -1;i = edge[i].next){ int v = edge[i].to; if(edge[i].cap > edge[i].flow && dis[v] > dis[u] + edge[i].cost){ dis[v] = dis[u] + edge[i].cost; pre[v] = i; if(!vis[v]){ vis[v] = true; q.push(v); } } } } return pre[t] != -1;}int MCMF(int s,int t,int &cost){ int flow = 0; cost = 0; while(spfa(s,t)){ int MIN = INF; for(int i = pre[t];i != -1;i = pre[edge[i^1].to]){ if(MIN > edge[i].cap - edge[i].flow){ MIN = edge[i].cap - edge[i].flow; } } for(int i = pre[t];i != -1; i = pre[edge[i^1]. to]){ edge[i]. flow += MIN; edge[i^1]. flow -= MIN; cost += edge[i]. cost * MIN; } flow += MIN; } return flow;}char mp[maxn][maxn];int main(){ int n,m; while(scanf("%d%d",&n,&m) && n+m){ init(); int mcnt = 0,hcnt = 0; for(int i = 1;i <= n;i++){ scanf("%s",mp[i] + 1); for(int j = 1;j <= m;j++){ if(mp[i][j] == 'm'){ man[mcnt].x = i; man[mcnt++].y = j; } else if(mp[i][j] == 'H'){ house[hcnt].x = i; house[hcnt++].y = j; } } } //建图 for(int i = 1;i <= hcnt;i++){ //和超级源点连 addEdge(0,i,1,0); } for(int i = hcnt + 1;i <= 2*hcnt;i++){ //和超级汇点连 addEdge(i,2*hcnt + 1,1,0); } for(int i = 0;i < mcnt;i++){ for(int j = 0;j < mcnt;j++){ int pay = abs(house[i].x - man[j].x) + abs(house[i].y - man[j].y); addEdge(i + 1,j + mcnt + 1,1,pay); } } int cost = 0; MCMF(0,2*hcnt + 1,cost); printf("%d\n",cost); } return 0;}