Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
代码有点长,但是感觉思路还行,1A,贴下留念~~~#include<iostream> #include<queue> using namespace std; #define MAX 101 #define INF (1 << 31 - 1) struct TM { int x; int y; }; struct TH { int x; int y; }; struct TNode { int x; int y; int step; }; TM tms[MAX]; TH ths[MAX]; int map[MAX][MAX]; int rows, cols; int cntM, cntH; int xx[4] = {0, 1, 0, -1}; int yy[4] = {-1, 0, 1, 0}; bool vis[MAX][MAX]; queue<TNode> qq; void vInput() { int i, j; char ch; cntM = 0, cntH = 0; for(i = 1; i <= rows; i++) { getchar(); for(j = 1; j <= cols; j++) { scanf("%c", &ch); if(ch == 'm') { tms[++cntM].x = i; tms[cntM].y = j; } else if(ch == 'H') { ths[++cntH].x = i; ths[cntH].y = j; } } } } bool inmap(int x, int y) { if(x > 0 && x <= rows && y > 0 && y <= cols) return true; return false; } int bfs(int start, int end) { int i, nx, ny; TNode cur, temp; cur.x = tms[start].x; cur.y = tms[start].y; cur.step = 0; memset(vis, false, sizeof(vis)); while(!qq.empty()) qq.pop(); qq.push(cur); vis[cur.x][cur.y] = true; while(!qq.empty()) { cur = qq.front(); qq.pop(); if(cur.x == ths[end].x && cur.y == ths[end].y) return cur.step; for(i = 0; i < 4; i++) { nx = cur.x + xx[i]; ny = cur.y + yy[i]; if(!vis[nx][ny] && inmap(nx, ny)) { temp.x = nx; temp.y = ny; temp.step = cur.step + 1; qq.push(temp); vis[nx][ny] = true; } } } return -1; } void vBuiltMap() { int i, j; for(i = 1; i <= cntM; i++) for(j = 1; j <= cntH; j++) { map[i][j] = bfs(i, j); } } int lx[MAX], ly[MAX]; bool markx[MAX], marky[MAX]; int link[MAX]; bool bHungarian(int u) { int v; markx[u] = true; for(v = 1; v <= cntH; v++) { if(!marky[v] && lx[u] + ly[v] == map[u][v]) { marky[v] = true; if(link[v] == 0 || bHungarian(link[v])) { link[v] = u; return true; } } } return false; } int nKM(bool isMAX) { int i, j, k, dd, sum; memset(link, 0, sizeof(link)); memset(ly, 0, sizeof(ly));//初始化为0 if(!isMAX) { for(i = 1; i <= cntM; i++) for(j = 1; j <= cntH; j++) map[i][j] *= -1; } for(i = 1; i <= cntM; i++) { lx[i] = -INF; for(j = 1; j <= cntH; j++) { if(lx[i] < map[i][j]) lx[i] = map[i][j]; } } for(i = 1; i <= cntM; i++) { while(1) { memset(markx, false, sizeof(markx)); memset(marky, false, sizeof(marky)); if(bHungarian(i)) break; dd = INF; for(j = 1; j <= cntM; j++) { if(markx[j]) { for(k = 1; k <= cntH; k++) { if(!marky[k]) if(dd > (lx[j] + ly[k] - map[j][k])) dd = lx[j] + ly[k] - map[j][k]; } } } for(j = 1; j <= cntM; j++) { if(markx[j]) lx[j] -= dd; if(marky[j]) ly[j] += dd; } } } sum = 0; for(i = 1; i <= cntH; i++) { sum += map[link[i]][i]; } return -sum; } void vOut(int nOut) { printf("%d\n", nOut); } int main() { int nAns; while(2 == scanf("%d%d", &rows, &cols)) { if(rows == 0 && cols == 0) break; vInput(); vBuiltMap(); nAns = nKM(false); vOut(nAns); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator