poj acm的AC解题报告

/*最小费用最大流 Sample Input 输入地图 2 2 行数列数 .m .表空格 m表人 H. H表房子 5 5 人每走一步1美元 HH..m 一间房子装一人 ..... 问所有人进房子最小代价 ..... ..... mm..H 7 8 ...H.... ...H.... ...H.... mmmHmmmm ...H.... ...H.... ...H.... 0 0 Sample Output 2 10 28 */ #include <iostream> #include <algorithm> #include <queue> #include <cmath> using namespace std; #define MAXN 1000 #define NIL INT_MAX struct point { int u, have; bool operator <(const point it)const {return have > it.have; } }; int flow[MAXN][MAXN];//流，初始化为0 int fees[MAXN][MAXN];//费用，初始化为无穷大 int have[MAXN]; int father[MAXN]; int mk[MAXN]; int min(int a, int b){ if(a > b)return b; else return a; } int flow_dijk (int n, int u, int s) { priority_queue<point> h; int i, k=0; point pond; for(i=0; i<=n; i++) { mk[i] = 0; have[i] = NIL; father[i] = -1; } pond.u = u; pond.have = 0; h.push( pond ); have[u]=0; while(k<=n && !h.empty()) { pond = h.top(); h.pop(); u = pond.u; if(mk[u])continue; k++; if(u == s)return have[s]; mk[u] = 1; for(i=0; i<=n; i++) { if(!mk[i] && fees[u][i] != NIL && have[i]>fees[u][i]+have[u] && flow[u][i]!=0 ) { have[i] = fees[u][i] + have[u]; pond.u = i; pond.have = have[i]; h.push(pond); father[i] = u; } } } return 0; } int max_flow_min_fee (int n, int u, int s) { int maxflow = 0, ans, k, fee, minfee = 0; while ( fee = flow_dijk(n, u, s) ) { ans = NIL; k = s; while (father[k] != -1) { if(flow[father[k]][k] < ans) ans = flow[father[k]][k]; k = father[k]; } maxflow += ans; minfee += (ans * fee); k = s; while (father[k] != -1) { flow[father[k]][k] -= ans; flow[k][father[k]] += ans; k = father[k]; } } return minfee; } int main() { struct pi { int i, j; }; int mm, n, i, j, mi, hi; char c; pi m[MAXN], h[MAXN]; while(scanf( "%d %d", &n, &mm)!=EOF && (n!=0 && mm!=0)) { mi = 1; hi = 1; for(i=1; i<=n; i++) { getchar(); for(j=1; j<=mm; j++) { scanf("%c", &c); if(c == 'm') { m[mi].i = i; m[mi].j = j; mi++; } else if(c == 'H') { h[hi].i = i; h[hi].j = j; hi++; } } } hi--; mi--; n = hi + mi; for(i=1; i<=n; i++) for(j=1 ;j<=n; j++) { fees[i][j] = NIL; flow[i][j] = 0; } for(i=1; i<=mi; i++) { flow[0][i] = 1; fees[0][i] = 0; } for(i=1; i<=hi; i++) { flow[mi+i][n+1] = 1; fees[mi+i][n+1] = 0; } for(i=1; i<=mi; i++) for(j=1; j<=hi; j++) { flow[i][mi+j] = 1; fees[i][mi+j] = abs ( m[i].i - h[j].i ) + abs ( m[i].j - h[j].j ); fees[mi+j][i] = -fees[i][mi+j]; } printf("%d\n", max_flow_min_fee (n+1, 0, n+1)); } return 0; }