POJ 2195(2점도 대권 일치)
문제풀이 사고방식: 이 문제는 권한 일치나 비용 흐름 문제로 바뀔 수 있다.먼저 입력 구도에 따라 문제를 권한 일치 문제로 전환한 후 KM 알고리즘을 적용하면 된다.KM 알고리즘의 입문은 아주 좋은 문제입니다.
코드:
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define INF 0x3f3f3f3f
#define MAXN 105
using namespace std;
int n,a[MAXN][MAXN],vx[MAXN],vy[MAXN],lx[MAXN],ly[MAXN],pre[MAXN],slack[MAXN];
int N,M,cnth,cntm;
struct point{
int x,y;
}tmph[MAXN],tmpm[MAXN];
char st[MAXN][MAXN];
bool dfs(int index)
{
vx[index]=1;
for(int i=1;i<=n;i++)
{
if(!vy[i]&&lx[index]+ly[i]==a[index][i])
{
vy[i]=1;
if(!pre[i]||dfs(pre[i]))
{
pre[i]=index;
return 1;
}
}
else if(!vy[i]&&lx[index]+ly[i]>a[index][i])
slack[i]=min(slack[i], lx[index]+ly[i]-a[index][i]);
}
return 0;
}
int KM()
{
memset(ly,0,sizeof(ly));
for(int i=1;i<=n;i++)
{
lx[i]=-INF;
for(int j=1;j<=n;j++)
lx[i]=max(lx[i],a[i][j]);
}
int ans=0,d;
memset(pre,0,sizeof(pre));
for(int i=1;i<=n;i++)
{
memset(slack,INF,sizeof(slack));
while(1)
{
memset(vx,0,sizeof(vx));
memset(vy,0,sizeof(vy));
if(dfs(i))
break;
d=INF;
for(int i=1;i<=n;i++)
if(!vy[i])
d=min(d,slack[i]);
if(d==INF) return -1; //no matching
for(int j=1;j<=n;j++)
if(vx[j]) lx[j]-=d;
for(int j=1;j<=n;j++)
if(vy[j]) ly[j]+=d;
}
}
for(int i=1;i<=n;i++)
ans+=a[pre[i]][i];
return ans;
}
int main()
{
while(~scanf("%d %d", &N, &M))
{
if(!N&&!M)
break;
cnth=cntm=0;
getchar();
for(int i=1;i<=N;i++)
{
for(int j=1;j<=M;j++)
{
scanf("%c",&st[i][j]);
if(st[i][j]=='m')
cntm++,tmpm[cntm].x=i, tmpm[cntm].y=j;
if(st[i][j]=='H')
cnth++,tmph[cnth].x=i, tmph[cnth].y=j;
}
getchar();
}
n=cntm;
for(int i=1;i<=cntm;i++)
for(int j=1;j<=cnth;j++)
a[i][j]=-(abs(tmpm[i].x-tmph[j].x)+abs(tmpm[i].y-tmph[j].y));
printf("%d
",-KM());
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.