首页 > 代码库 > POJ2195 最小费用流
POJ2195 最小费用流
题目:http://poj.org/problem?id=2195
处理出每个人到每个门的曼哈顿距离,分别建立容量为1费用为曼哈顿距离的边,在源点和每个人人之间建立容量为1费用为0的边,在门和汇点之间建立容量为1费用为0的边,然后跑最小费用流即可。
1 #include<cstdio> 2 #include<cstring> 3 #include<vector> 4 #include<queue> 5 #include<iostream> 6 #include<stdlib.h> 7 using namespace std; 8 typedef pair<int,int> P; 9 const int maxv = 222; 10 const int inf = 0x3f3f3f3f; 11 struct edge{ 12 int to,cap,cost,rev; 13 }; 14 int V; 15 vector<edge> g[maxv]; 16 int h[maxv]; 17 int dist[maxv]; 18 int prevv[maxv],preve[maxv]; 19 void addedge(int from,int to,int cap,int cost){ 20 edge t; 21 t.to = to;t.cap = cap;t.cost = cost;t.rev = g[to].size(); 22 g[from].push_back(t); 23 t.to = from;t.cap = 0;t.cost = -cost;t.rev = g[from].size()-1; 24 g[to].push_back(t); 25 } 26 int solve(int s,int t,int f){ 27 int res = 0; 28 memset(h,0,sizeof(h)); 29 while(f > 0){ 30 priority_queue<P,vector<P>,greater<P> > que; 31 memset(dist,inf,sizeof(dist)); 32 dist[s] = 0; 33 que.push(P(0,s)); 34 while(!que.empty()){ 35 P p = que.top(); 36 que.pop(); 37 int v = p.second; 38 if(dist[v] < p.first) 39 continue; 40 for(int i = 0;i<g[v].size();i++){ 41 edge &e = g[v][i]; 42 if(e.cap>0 && dist[e.to]>dist[v]+e.cost+h[v]-h[e.to]){ 43 dist[e.to] = dist[v]+e.cost+h[v]-h[e.to]; 44 prevv[e.to] = v; 45 preve[e.to] = i; 46 que.push(P(dist[e.to],e.to)); 47 } 48 } 49 } 50 if(dist[t] == inf){ 51 return -1; 52 } 53 for(int i = 0;i<=t;i++) 54 h[i] += dist[i]; 55 int d = f; 56 for(int i = t;i!=s;i = prevv[i]){ 57 d = min(d,g[prevv[i]][preve[i]].cap); 58 } 59 f -= d; 60 res += d*h[t]; 61 for(int i = t;i!=s;i = prevv[i]){ 62 edge &e = g[prevv[i]][preve[i]]; 63 e.cap -= d; 64 g[i][e.rev].cap += d; 65 } 66 } 67 return res; 68 } 69 int main(){ 70 int n,m; 71 while(scanf("%d%d",&n,&m) && n && m){ 72 vector<P> mm,hh; 73 char ch; 74 for(int i = 1;i<=n;i++){ 75 for(int j = 1;j<=m;j++){ 76 scanf(" %c",&ch); 77 if(ch == ‘m‘) 78 mm.push_back(P(i,j)); 79 if(ch == ‘H‘) 80 hh.push_back(P(i,j)); 81 } 82 } 83 for(int i = 0;i<=2*mm.size()+1;i++) 84 g[i].clear(); 85 for(int i = 0;i<mm.size();i++){ 86 for(int j = 0;j<hh.size();j++){ 87 addedge(i+1,mm.size()+j+1,1,abs(mm[i].first-hh[j].first)+abs(mm[i].second-hh[j].second)); 88 } 89 } 90 int s = 0,t = 2*mm.size()+1; 91 for(int i = 0;i<mm.size();i++) 92 addedge(s,i+1,1,0); 93 for(int i = 0;i<hh.size();i++) 94 addedge(mm.size()+i+1,t,1,0); 95 cout << solve(s,t,mm.size()) << endl; 96 } 97 }
POJ2195 最小费用流
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。