| ||||||||||
| 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