网络流
程序员文章站
2022-07-09 13:14:05
title: 网络流 date: 2018 07 31 22:01:22 tags: acm 算法 网络流 概述 这篇博客主要是关于网络流的一些基本的知识点以及相应的模板，， 算了，，，还是先贴大佬的博客，，，暑假在补一下。。。。QAQ
title: 网络流
date: 2018-07-31 22:01:22
tags:
- acm
- 算法
网络流
概述
这篇博客主要是关于网络流的一些基本的知识点以及相应的模板，，
算了，，，还是先贴大佬的博客，，，暑假在补一下。。。。QAQ
网络流
tan90，，，，，，，
习题
Problem A: 养猪
Time Limit: 1 Sec Memory Limit: 128 MB
Description
AveryBoy喜欢玩LOL，但是他技术太菜，总是被别人喷“这么菜玩什么游戏，回家养猪去吧”。终于有一天，他被喷的受不了了，于是回家养猪。不过他家的养猪场在下雨天的时候总是被淹，所以他用读书学来的知识设计了一套排水系统。他还设计了一套装置，可以控制排水管道的水流流量。现在有n个排水管道，m个排水节点，问你从1到m的最大排水流量。
Input
有多组测试数据，对于每组测试数据，第一行是两个整数n，m（0 <= n <= 200，2 <= m <= 200），分别表示排水管道数和排水节点数。之后n行每行包含3个整数，u，v，w（1<=u,v<=m，0<=w<=1e7，u!=v），表示从u到v的排水管道的水流流量是w。
Output
对于每种情况输出一个整数，表示从1到m的最大排水流量。
Sample Input
5 4
1 2 40
1 4 20
2 4 20
2 3 30
3 4 10
Sample Output
50
模板题，，，直接套就行
#include <iostream>
#include <bits/stdc++.h>
#define ms(a , b) memset(a , b , sizeof(a))
using namespace std;
//前向星
typedef long long ll;
const int maxn = 1e4;
const int inf = 0x3f3f3f3f;
int n , m;
struct Edge
{
int to;
int next;
int w;
}edge[maxn << 1];
int head[maxn];
bool vis[maxn];
int cnt;
void init()
{
ms(head , -1);
cnt = 0;
}
void add(int u , int v , int w)
{
edge[cnt].to = v;
edge[cnt].w = w;
edge[cnt].next = head[u];
head[u] = cnt++;
edge[cnt].to = u; //添加反向边，，流量为零
edge[cnt].w = 0;
edge[cnt].next = head[v];
head[v] = cnt++;
}
int step[maxn];
bool bfs(int s , int t)
{
ms(step , -1);
step[s] = 0;
queue<int> q;
q.push(s);
while (!q.empty())
{
int u = q.front();q.pop();
for (int i = head[u]; i != -1; i = edge[i].next)
{
if (step[edge[i].to] == -1 && edge[i].w > 0)
{
step[edge[i].to] = step[u] + 1;
q.push(edge[i].to);
if (edge[i].to == t) return true;
}
}
}
return step[t] != -1;
}
int dfs(int s , int t , int f)
{
if (s == t || !f) return f;
int flow = 0;
for (int i = head[s]; i != -1; i = edge[i].next)
{
if (step[s] + 1 == step[edge[i].to] && edge[i].w > 0)
{
int d = dfs(edge[i].to , t , min(edge[i].w , f));
if (d > 0)
{
edge[i].w -= d;
edge[i ^ 1].w += d;
flow += d; //累加当前节点的某条路径的合适流量
f -= d; //当前节点的容量减去某条路径的合适流量
if (f == 0) break; //如果当前节点的容量用完,说明无法再通过任何流量
}
}
}
if (flow == 0) step[s] = inf; //如果当前节点无任何流量通过,取消标记
return flow;
}
int Dinic(int s , int t)
{
int flow = 0;
while (bfs(s , t))
{
flow += dfs(s , t , inf);
}
return flow;
}
int main()
{
//ios_base::sync_with_stdio(0);
while (~scanf("%d%d", &n , &m))
{
int u , v , w;
init();
for (int i = 1; i <= n; i++)
{
//cin >> u >> v >> w;
scanf("%d%d%d" , &u , &v , &w);
add(u , v , w);
}
printf("%d\n" , Dinic(1 , m));
//cout << "Case " << k++ << ": " << ans << endl;
}
return 0;
}
学长用的邻接表存的，，，
学长的代码:
// hdu 1532
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PB push_back
const int INF = 0x3f3f3f3f;
const int maxn = 205;
int n,m;
struct Edge{
int to,cap,idx;
Edge(){}
Edge(int to,int cap,int idx):to(to),cap(cap),idx(idx){}
};
vector<Edge> V[maxn];
bool vis[maxn];
void add_edge(int u,int v,int w)
{
V[u].PB(Edge(v,w,V[v].size()));
V[v].PB(Edge(u,0,V[u].size()-1));
}
int dfs(int s,int t,int f)
{
if(s==t) return f;
vis[s]=true;
for(int i=0;i<V[s].size();i++)
{
Edge &cur = V[s][i];
if(!vis[cur.to] && cur.cap>0)
{
int tmp = dfs(cur.to,t,min(f,cur.cap));
if(tmp>0)
{
cur.cap -= tmp;
V[cur.to][cur.idx].cap += tmp;
return tmp;
}
}
}
return 0;
}
int Ford_Fulkerson(int s,int t)
{
int res = 0;
while(true)
{
memset(vis,false,sizeof(vis));
int flow = dfs(s,t,INF);
if(flow==0) return res;
res += flow;
}
}
int main()
{
while(~scanf("%d%d",&n,&m))
{
for(int i=1;i<=m;i++) V[i].clear();
int u,v,w;
for(int i=1;i<=n;i++)
{
scanf("%d%d%d",&u,&v,&w);
add_edge(u,v,w);
}
printf("%d\n",Ford_Fulkerson(1,m));
}
return 0;
}
Problem B: 最大流
Time Limit: 1 Sec Memory Limit: 128 MB
Description
如题，给你一个容量网络，请你找出最大流。
Input
第一行输入包含一个整数T，表示测试用例的数量。
对于每个测试用例，第一行包含两个整数N和M，表示图中顶点和边的数量。（2 <= N <= 15,0 <= M <= 1000）
接下来的M行，每行包含三个整数X，Y和C，表示从X到Y有一个边，它的容量是C.（1 <= X，Y <= N，1 <= C <= 1000）
Output
对于每个测试用例，您应该输出从源点1到汇点N的最大流量。
Sample Input
2
3 2
1 2 1
2 3 1
3 3
1 2 1
2 3 1
1 3 1
Sample Output
Case 1: 1
Case 2: 2
同样是模板题，，，不过刚开始我套fk的模板一直tle就换了dinic算法
#include <iostream>
#include <bits/stdc++.h>
#define ms(a , b) memset(a , b , sizeof(a))
using namespace std;
//前向星
const int maxn = 1e4;
const int inf = 0x3f3f3f3f;
int n , m;
struct Edge
{
int to;
int next;
int w;
}edge[maxn << 1];
int head[maxn];
bool vis[maxn];
int cnt;
void init()
{
ms(head , -1);
cnt = 0;
}
void add(int u , int v , int w)
{
edge[cnt].to = v;
edge[cnt].w = w;
edge[cnt].next = head[u];
head[u] = cnt++;
edge[cnt].to = u; //添加反向边，，流量为零
edge[cnt].w = 0;
edge[cnt].next = head[v];
head[v] = cnt++;
}
int step[maxn];
bool bfs(int s , int t)
{
ms(step , -1);
step[s] = 0;
queue<int> q;
q.push(s);
while (!q.empty())
{
int u = q.front();q.pop();
for (int i = head[u]; i != -1; i = edge[i].next)
{
if (step[edge[i].to] == -1 && edge[i].w > 0)
{
step[edge[i].to] = step[u] + 1;
q.push(edge[i].to);
if (edge[i].to == t) return true;
}
}
}
return step[t] != -1;
}
int dfs(int s , int t , int f)
{
if (s == t || !f) return f;
int flow = 0;
for (int i = head[s]; i != -1; i = edge[i].next)
{
if (step[s] + 1 == step[edge[i].to] && edge[i].w > 0)
{
int d = dfs(edge[i].to , t , min(edge[i].w , f));
if (d > 0)
{
edge[i].w -= d;
edge[i ^ 1].w += d;
flow += d; //累加当前节点的某条路径的合适流量
f -= d; //当前节点的容量减去某条路径的合适流量
if (f == 0) break; //如果当前节点的容量用完,说明无法再通过任何流量
}
}
}
if (flow == 0) step[s] = inf; //如果当前节点无任何流量通过,取消标记
return flow;
}
int Dinic(int s , int t)
{
int flow = 0;
while (bfs(s , t))
{
flow += dfs(s , t , inf);
}
return flow;
}
int main()
{
//ios_base::sync_with_stdio(0);
int t;scanf("%d" , &t);
//cin >> t;
int k = 1;
while (t--)
{
//cin >> n >> m;
scanf("%d%d", &n , &m);
int u , v , w;
init();
for (int i = 1; i <= m; i++)
{
//cin >> u >> v >> w;
scanf("%d%d%d" , &u , &v , &w);
add(u , v , w);
}
printf("Case %d: %d\n" , k++ , Dinic(1 , n));
//cout << "Case " << k++ << ": " << ans << endl;
}
return 0;
}
学长的代码：
// hdu 3549
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define PB push_back
const int INF = 0x3f3f3f3f;
const int maxn = 20;
int c[maxn][maxn],f[maxn][maxn],p[maxn],a[maxn];
int m,n;
int bfs()
{
queue<int> q;
memset(p,-1,sizeof(p));
memset(a,0,sizeof(a));
a[1] = INF;
q.push(1);
while(!q.empty())
{
int u = q.front();q.pop();
for(int i=1;i<=n;i++)
{
if(!a[i] && c[u][i]>f[u][i])
{
p[i] = u;
q.push(i);
a[i] = min(a[u],c[u][i]-f[u][i]);
}
}
if(a[n]) break;
}
if(!a[n]) return 0;
for(int u=n;u!=1;u=p[u])
{
f[p[u]][u] += a[n];
f[u][p[u]] -= a[n];
}
return a[n];
}
int Edmonds_Karp()
{
int res = 0;
while(true)
{
int tmp = bfs();
if(tmp==0) return res;
res += tmp;
}
}
int main()
{
int t;
scanf("%d",&t);
for(int ca=1;ca<=t;ca++)
{
scanf("%d%d",&n,&m);
memset(c,0,sizeof(c));
memset(f,0,sizeof(f));
int u,v,w;
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&u,&v,&w);
c[u][v] += w;
}
int max_flow=Edmonds_Karp();
printf("Case %d: %d\n",ca,max_flow);
}
return 0;
}
Problem C: 房子和车
Time Limit: 1 Sec Memory Limit: 128 MB
Description
华中农业大学总共有n个老师，f种房子和d种车（1 <= n，f，d <= 200）。每个老师都有自己喜欢的一些房子和车的类型，现在要你把这些房子和车分配给这n个老师，每个老师只分配一套房子和一辆车。问你最多能使多少个老师满意对应的分配。
Input
有多组测试数据，每组测试数据第一行是3个正整数，n，f，d，表示老师个数，房子种数，车子种数。
第二行包含f个整数，其中第i个数表示第i种房子的个数。
第三行包含d个整数，其中第i个数表示第i种车子的个数。
之后n行，每行包含长度为f的字符串，其中第i行第j个字符表示第i个老师是否喜欢第j种房子，‘Y’表示喜欢，‘N’表示不喜欢。
之后n行，每行包含长度为d的字符串，其中第i行第j个字符表示第i个老师是否喜欢第j种车子，‘Y’表示喜欢，‘N’表示不喜欢。
Output
对于每组测试数据，输出一个整数，表示最大的老师满意的个数。
Sample Input
4 3 3
1 1 1
1 1 1
YYN
NYY
YNY
YNY
YNY
YYN
YYN
NNY
Sample Output
3
这道题主要是将题目所给的信息用图描述出来，，，老师的处理是一分为二即可，，，
我的代码:
#include <iostream>
#include <bits/stdc++.h>
#define ms(a , b) memset(a , b , sizeof(a))
using namespace std;
//前向星
typedef long long ll;
const int maxn = 1e5;
const int maxm = 1e3 + 10;
const int inf = 0x3f3f3f3f;
int n , f , d;
int home[maxm];
int car[maxm];
struct Edge
{
int to;
int next;
int w;
}edge[maxn << 1];
int head[maxn];
bool vis[maxn];
int cnt;
void init()
{
ms(head , -1);
cnt = 0;
}
void add(int u , int v , int w)
{
edge[cnt].to = v;
edge[cnt].w = w;
edge[cnt].next = head[u];
head[u] = cnt++;
edge[cnt].to = u; //添加反向边，，流量为零
edge[cnt].w = 0;
edge[cnt].next = head[v];
head[v] = cnt++;
}
int step[maxn];
bool bfs(int s , int t)
{
ms(step , -1);
step[s] = 0;
queue<int> q;
q.push(s);
while (!q.empty())
{
int u = q.front();q.pop();
for (int i = head[u]; i != -1; i = edge[i].next)
{
if (step[edge[i].to] == -1 && edge[i].w > 0)
{
step[edge[i].to] = step[u] + 1;
q.push(edge[i].to);
if (edge[i].to == t) return true;
}
}
}
return step[t] != -1;
}
int dfs(int s , int t , int f)
{
if (s == t || !f) return f;
int flow = 0;
for (int i = head[s]; i != -1; i = edge[i].next)
{
if (step[s] + 1 == step[edge[i].to] && edge[i].w > 0)
{
int d = dfs(edge[i].to , t , min(edge[i].w , f));
if (d > 0)
{
edge[i].w -= d;
edge[i ^ 1].w += d;
flow += d; //累加当前节点的某条路径的合适流量
f -= d; //当前节点的容量减去某条路径的合适流量
if (f == 0) break; //如果当前节点的容量用完,说明无法再通过任何流量
}
}
}
if (flow == 0) step[s] = inf; //如果当前节点无任何流量通过,取消标记
return flow;
}
int Dinic(int s , int t)
{
int flow = 0;
while (bfs(s , t))
{
flow += dfs(s , t , inf);
}
return flow;
}
int main()
{
//ios_base::sync_with_stdio(0);
while (~scanf("%d%d%d", &n , &f , &d))
{
init();
for (int i = 1; i <= f; i++)
scanf("%d" , &home[i]);
for (int i = 1; i <= d; i++)
scanf("%d" , &car[i]);
int s = 0; //超级原点
int t = f + n + n + d + 1; //汇点
for (int i = 1; i <= f; i++)
add(0 , i , home[i]); //原点到每个房子的点建边
char str[maxm];
for (int i = 1; i <= n; i++)
{
scanf("%s" , str);
for (int j = 1; j <= f; j++)
{
if (str[j - 1] == 'Y')
add(j , i + f, 1); //老师满意的和对应的房子连接，，，流量为1
}
add(i + f , f + n + i , 1); //分离出两个老师的点，，，同一个老师之间流量为1
}
for (int i = 1; i <= n; i++)
{
scanf("%s" , str);
for (int j = 1; j <= d; j++)
if (str[j - 1] == 'Y')
add(f + n + i , f + n + n + j , 1);//第二个老师的点和车子建边，，，流量为1
}
for (int i = 1; i <= d; i++)
add(f + n + n + i , t , car[i]); //汇点和车子之间建边，
printf("%d\n" , Dinic(s , t));
}
return 0;
}
add(f + n + n + i , t , 1);
//----------
//这个在处理点之间的关系和我的不同，，，一个是老师分开另一个是分开的老师相邻就是下面这个
int s = 0;
int t = f + n + n + d + 1;
for (int i = 1; i <= f; i++)
add(0 , i , home[i]);
char str[maxm];
for (int i = 1; i <= n; i++)
{
scanf("%s" , str);
for (int j = 1; j <= f; j++)
{
if (str[j - 1] == 'Y')
add(j , f + 2 * i - 1 , 1);
}
add(f + 2 * i - 1 , f + 2 * i , 1);
}
for (int i = 1; i <= n; i++)
{
scanf("%s" , str);
for (int j = 1; j <= d; j++)
if (str[j - 1] == 'Y')
add(f + 2 * i , f + n + n + j , 1);
}
for (int i = 1; i <= d; i++)
add(f + n + n + i , t , car[i]);
printf("%d\n" , Dinic(s , t));
学长的代码:
// hdu 4292
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<queue>
#define INF 0x3f3f3f3f
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;
const int N=1000+50;
const int M=1e6+50;
struct node
{
node() {};
node(int tv,int tw,int tnext)
{
v=tv,w=tw,next=tnext;
};
int v,w,next;
} e[M];
int first[N],vis[N],dis[N],tot;
void add_edge(int u,int v,int w)
{
e[tot]=node(v,w,first[u]);
first[u]=tot++;
e[tot]=node(u,0,first[v]);
first[v]=tot++;
}
int bfs(int s,int t)
{
mem(vis,0);
mem(dis,0);
queue<int>q;
q.push(s);
vis[s]=1;
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=first[u]; ~i; i=e[i].next)
{
if(!vis[e[i].v]&&e[i].w>0)
{
vis[e[i].v]=1;
dis[e[i].v]=dis[u]+1;
q.push(e[i].v);
}
}
}
return dis[t];
}
int dfs(int u,int t,int flow)
{
if(u==t)return flow;
for(int i=first[u]; ~i; i=e[i].next)
{
if(dis[e[i].v]==dis[u]+1&&e[i].w>0)
{
int dd=dfs(e[i].v,t,min(e[i].w,flow));
if(dd)
{
e[i].w-=dd;
e[i^1].w+=dd;
return dd;
}
}
}
dis[u]=0;
return 0;
}
int Dinic(int s,int t)
{
int ans=0,flow;
while(bfs(s,t))
{
while(flow=dfs(s,t,INF))
ans+=flow;
}
return ans;
}
void init()
{
mem(first,-1);
tot=0;
}
int a[N],b[N];
char s[N];
int main()
{
int n,f,d;
while(~scanf("%d%d%d",&n,&f,&d))
{
init();
for(int i=1; i<=f; i++) scanf("%d",&a[i]);
for(int i=1; i<=d; i++) scanf("%d",&b[i]);
for(int i=1; i<=n; i++)
{
add_edge(f+2*i-1,f+2*i,1);
scanf("%s",s+1);
for(int j=1; j<=f; j++)
if(s[j]=='Y')
add_edge(j,f+2*i-1,1);
}
for(int i=1; i<=n; i++)
{
scanf("%s",s+1);
for(int j=1; j<=d; j++)
if(s[j]=='Y')
add_edge(f+2*i,f+2*n+j,1);
}
for(int i=1; i<=f; i++) add_edge(0,i,a[i]);
for(int i=1; i<=d; i++) add_edge(2*n+f+i,2*n+f+d+1,b[i]);
printf("%d\n",Dinic(0,2*n+f+d+1));
}
return 0;
}
Problem D: 回家
Time Limit: 5 Sec Memory Limit: 128 MB
Description
在网格地图上有n个人和n个房子。在每个单位时间内，每个人都可以水平或垂直移动到相邻点。对于每个人，你需要为他移动的每一步支付1美元的旅行费，直到他进入房子。每个房子只能容纳一个人。现在问你所有人都回到房子所需要的最少费用是多少？输入是一个网格图，‘.’表示空地，‘H’表示房子，‘m’表示人。
Input
有多组测试数据，对于每组测试数据第一行是两个正整数n，m表示地图的行和列（2<=n，m<=100）。地图上有相同数量的房子和人，房子最多不超过100。输入以n=0，m=0结束。
Output
对于每组测试数据输出一个整数，表示所有人都回到房子所需的最小费用。
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
这道题自己做的时候被网上的模板坑了一手，，，一直tle，，，换模板就行了，，，
主要思路是，先将人房找到，，，计算出每一个人和所有房子直接的距离，，这个距离也叫曼哈顿距离，，，然后人房直接建边，，再弄一个超级原点和汇点求原点和会顶啊直接的最小费用的最大流就可以了，，，，
#include <iostream>
#include <bits/stdc++.h>
#define ms(a , b) memset(a , b , sizeof(a))
using namespace std;
//前向星
typedef long long ll;
const int maxn = 1e3 + 5;
const int maxm = 1e3 + 5;
const int inf = 0x3f3f3f3f;
int n , m;
char mp[maxm][maxm];
struct Man
{
int x , y;
}man[maxn];
int cnt_man;
struct Home
{
int x , y;
}home[maxn];
int cnt_home;
struct Edge
{
int v;
int u;
int next;
int cap;
int cost;
Edge(){}
Edge(int u , int v, int cap , int cost , int next):u(u) , v(v) , cap(cap) , cost(cost) , next(next){}
}edge[maxn << 7];
int head[maxn];
int cnt;
void init()
{
ms(head , -1);
cnt = 0;
cnt_home = 1;
cnt_man = 1;
}
void add(int from , int to , int cap , int cost)
{
edge[cnt] = Edge(from , to , cap , cost , head[from]);
head[from] = cnt++;
edge[cnt] = Edge(to , from , 0 , -cost , head[to]);
head[to] = cnt++;
}
int dis[maxn << 1];
int pe[maxn << 1];
bool vis[maxn << 1];
bool spfa(int s , int t)
{
ms(dis , inf);
ms(vis , false);
ms(pe , -1);
dis[0] = 0;
vis[s] = true;
queue<int> q;
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].v;
int cost = edge[i].cost;
if (edge[i].cap > 0 && dis[v] > dis[u] + cost)
{
dis[v] = dis[u] + cost;
pe[v] = i;
if (!vis[v])
{
vis[v] = true;
q.push(v);
}
}
}
}
if (dis[t] == inf) return false;
return true;
}
int min_cost_flow(int s , int t , int f)
{
int res = 0;
while (spfa(s , t))
{
int flow = inf;
for (int i = pe[t]; i != -1; i = pe[edge[i].u])
{
flow = min(flow , edge[i].cap);
}
f -= flow;
if (f < 0) break;
for (int i = pe[t]; i != -1; i = pe[edge[i].u])
{
edge[i].cap -= flow;
edge[i ^ 1].cap += flow;
}
res += flow * dis[t];
}
return res;
}
int main()
{
//ios_base::sync_with_stdio(0);
while (~scanf("%d%d", &n , &m) && n && m)
{
init();
char str[maxm];
for (int i = 1; i <= n; i++) //存图
{
scanf("%s" , str);
for (int j = 1; j <= m; j++)
mp[i][j] = str[j - 1];
}
for (int i = 1; i <= n; i++) //人房分离，，记录坐标
{
for (int j = 1; j <= m; j++)
{
if (mp[i][j] == 'H')
{
home[cnt_home].x = i;
home[cnt_home++].y = j;
}
else if (mp[i][j] == 'm')
{
man[cnt_man].x = i;
man[cnt_man++].y = j;
}
}
}
for (int i = 1; i <= cnt_man - 1; i++)
{
for (int j = 1; j <= cnt_home - 1; j++)
{ //算出每一个人对于所有房子的距离，，（曼哈顿距离），，，
int w = (int)fabs(man[i].x - home[j].x) + (int)fabs(man[i].y - home[j].y);
add(i , j + cnt_man - 1 , 1 , w); //人房之间连边，，，流量为刚刚的值
}
}
int t = cnt_home; //汇点
t *= 2;
t--;
for (int i = 1; i <= cnt_man - 1; i++) //超级原点和每个人建边，，流量为0
add(0 , i , 1 , 0);
for (int i = cnt_man; i <= t - 1; i++) //房子和汇点建边
add(i , t , 1 , 0);
printf("%d\n" , min_cost_flow(0 , t , t + 1));
}
return 0;
}
学长的代码：
// hdu 1533
#include <cstdio>
#include <queue>
#include <cstring>
#include <cstdlib>
using namespace std;
typedef long long ll;
#define PB push_back
const int INF = 0x3f3f3f3f;
const int maxn = 1005;
typedef pair<int,int> P;
char mp[105][105];
int dist[maxn<<1],pe[maxn<<1],head[maxn<<1];
bool vis[maxn<<1];
int n,m,tot;
struct Edge{
int u,v,cap,cost,next;
Edge(){}
Edge(int u,int v,int cap,int cost,int next):u(u),v(v),cap(cap),cost(cost),next(next){}
}edge[maxn<<7];
void add_edge(int from,int to,int cap,int cost)
{
edge[tot] = Edge(from,to,cap,cost,head[from]);
head[from] = tot++;
edge[tot] = Edge(to,from,0,-cost,head[to]);
head[to] = tot++;
}
bool SPFA(int s,int t)
{
memset(dist,INF,sizeof(dist));
memset(vis,false,sizeof(vis));
memset(pe,-1,sizeof(pe));
dist[s]=0;
vis[s]=true;
queue<int> q;
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].v;
int cost = edge[i].cost;
if(edge[i].cap>0 && dist[v]>dist[u]+cost)
{
dist[v] = dist[u]+cost;
pe[v] = i;
if(!vis[v])
{
vis[v]=true;
q.push(v);
}
}
}
}
if(dist[t]==INF) return false;
else return true;
}
int min_cost_flow(int s,int t,int f)
{
int res = 0;
while(SPFA(s,t))
{
int flow = INF;
for(int i=pe[t];i!=-1;i=pe[edge[i].u])
{
flow = min(flow,edge[i].cap);
}
f -= flow;
if(f<0) break;
for(int i=pe[t];i!=-1;i=pe[edge[i].u])
{
edge[i].cap -= flow;
edge[i^1].cap += flow;
}
res += flow*dist[t];
}
return res;
}
int dis(P a,P b)
{
return abs(a.first-b.first)+abs(a.second-b.second);
}
int main()
{
while(~scanf("%d%d",&n,&m) && (n!=0 && m!=0))
{
int num1=0,num2=0;
P man[maxn],hos[maxn];
for(int i=1;i<=n;i++)
{
scanf("%s",mp[i]);
for(int j=0;j<m;j++)
{
if(mp[i][j]=='m')
man[++num1] = P(i,j+1);
if(mp[i][j]=='H')
hos[++num2] = P(i,j+1);
}
}
int s=0,t=num1+num2+1;
memset(head,-1,sizeof(head));
tot=0;
for(int i=1;i<=num1;i++)
add_edge(0,i,1,0);
for(int i=1;i<=num2;i++)
add_edge(num1+i,t,1,0);
for(int i=1;i<=num1;i++)
{
for(int j=1;j<=num2;j++)
{
add_edge(i,num1+j,1,dis(man[i],hos[j]));
}
}
printf("%d\n",min_cost_flow(s,t,num1));
}
return 0;
}
鸽~~~~~~~~~~~~~~
下一篇： STL源码笔记（16）—单链表slist