MYF

POJ 2195 Going Home

Posted on | In | | Visitors

题目链接

POJ 2195

方法：最小费用最大流模版题

题目分析

题目大意

有若干个人和若干个房子，每个人走到一个房子，希望总距离最小，问最小距离

解析

实际上是一个带权的二分图匹配问题，这里使用最小费用最大流的方法来做。设置一个超级源点和一个超级汇点，然后将对应的边加上。每条边的容量为1，表示可以走或者不走，费用为距离，这样就很easy了，板子加上就过了。注意数据范围，100个人，所以至少开202个点

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
#include <set>
#include <map>
#include <stack>
#include <cmath>
#include <queue>
#include <cstdio>
#include <string>
#include <vector>
#include <iomanip>
#include <bitset>
#include <cstring>
#include <iostream> 
#include <iosfwd>
#include <deque>
#include <algorithm>
#define Memset(a,val) memset(a,val,sizeof(a))
#define PI acos(-1.0)
#define PB push_back
#define MP make_pair
#define rt(n)       (i == n ? '\n' : ' ')
#define hi         printf("Hi----------\n")
#define IN freopen("input.txt","r",stdin);
#define OUT freopen("output.txt","w",stdout);
#define debug(x) cout<<"Debug : ---"<<x<<"---"<<endl;
#define debug2(x,y) cout<<"Debug : ---"<<x<<" , "<<y<<"---"<<endl;
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
typedef pair<int,int> PII;
typedef long long ll;

const int mod=1000000007;
const int INF=0x3f3f3f3f;
const double eps=1e-8;

/**模版部分**/
const int maxn=200+5;
struct Edge{
    int from,to,cap,flow,cost;
    Edge(int u,int v,int c,int f,int w):from(u),to(v),cap(c),flow(f),cost(w){}
};
struct MCMF{
    int n,m;
    vector<Edge>edges;
    vector<int>G[maxn];
    int inq[maxn];  //是否在队列中
    int d[maxn];    //Bellman-Ford
    int p[maxn];    //上一条弧
    int a[maxn];    //可改进量
    
    void init(int n){
        this->n=n;
        for(int i=0;i<n;i++) G[i].clear();
        edges.clear();
    }
    
    void adde(int from,int to,int cap,int cost){
        edges.push_back(Edge(from, to, cap, 0, cost));
        edges.push_back(Edge(to, from, 0, 0, -cost));
        m=edges.size();
        G[from].push_back(m-2);
        G[to].push_back(m-1);
    }
    
    bool SPFA(int s,int t,int& flow,long long& cost){
        for(int i=0;i<n;i++) d[i]=INF;
        memset(inq, 0, sizeof(inq));
        d[s]=0;
        inq[s]=1;
        p[s]=0;
        a[s]=INF;
        
        queue<int>q;
        q.push(s);
        while(!q.empty()){
            int u=q.front();
            q.pop();
            inq[u]=0;
            for(int i=0;i<G[u].size();i++){
                Edge& e=edges[G[u][i]];
                if(e.cap>e.flow&&d[e.to]>d[u]+e.cost){
                    d[e.to]=d[u]+e.cost; //松弛操作
                    p[e.to]=G[u][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; //s-t 不联通，失败退出
        flow+=a[t];
        cost+=(long long)d[t]*(long long)a[t];
        for(int u=t;u!=s;u=edges[p[u]].from){
            edges[p[u]].flow+=a[t];
            edges[p[u]^1].flow-=a[t];
        }
        return true;
    }
    
    int MincostMaxflow(int s,int t,long long& cost){
        int flow=0;
        cost=0;
        while(SPFA(s, t, flow, cost));
        return flow;
    }
};
/**模版部分**/
struct node{
    int x,y;
    node(){}
    node(int _x,int _y){
        x = _x;
        y = _y;
    }
    int operator - (const node &a){
        return abs(a.x-x)+abs(a.y-y);
    }
}man[maxn],house[maxn];
char mp[maxn][maxn];
int main(){;
    int N,M;
    while (scanf("%d%d",&N,&M),N&&M) {
        
        MCMF p;
        for (int i=0; i<N; i++) {
            scanf("%s",mp[i]);
        }
        int mcnt = 0;
        int hcnt = 0;
        for (int i=0; i<N; i++) {
            for (int j=0; j<M; j++) {
                if (mp[i][j]=='H') {
                    house[hcnt++] = node(i,j);
                }
                else if(mp[i][j]=='m'){
                    man[mcnt++] = node (i,j);
                }
            }
        }
        
        int st = 0,ed =hcnt+mcnt+1;    //超级源点和超级汇点
        int cnt = hcnt + mcnt + 2;

        p.init(cnt);
        
        for (int i=1; i<=mcnt; i++) {
            p.adde(0, i, 1, 0);
        }
        for (int i=1; i<=hcnt; i++) {
            p.adde(mcnt+i, ed, 1, 0);
        }
        
        for (int i=0; i<mcnt; i++) {
            for (int j=0; j<hcnt; j++) {
                p.adde(i+1, mcnt+j+1, 1, man[i]-house[j]);
            }
        }
        
        ll mc,mf;
        mf = p.MincostMaxflow(st, ed, mc);
        cout<<mc<<endl;
    }
}