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 |
KM算法#include <cstdio> #include <iostream> using namespace std; const int MAXN=105; const int MAXM=5005; const int INF=0x3f3f3f3f; int n,m,now,cnt1,cnt2; char s[MAXN][MAXN]; int map[MAXN][MAXN]; int match[MAXM],slack[MAXM]; int vis_boy[MAXM],vis_girl[MAXM]; int ex_boy[MAXM],ex_girl[MAXM],rela[MAXM][MAXM]; inline int abs(int x) { if (x<0) return -x; return x; } inline int get_cost(int x,int y,int x0,int y0) { return abs(x-x0)+abs(y-y0); } inline bool dfs(int x) { int cp; vis_girl[x]=now; for (int y=1;y<=cnt1;y++) { if (vis_boy[y]==now) continue; cp=ex_girl[x]+ex_boy[y]-rela[x][y]; if (cp==0) { vis_boy[y]=now; if ((match[y]==0)||dfs(match[y])) { match[y]=x;return true; } } else if (cp<slack[y]) slack[y]=cp; } return false; } inline long long KM() { for (int i=1;i<=cnt1;i++) { match[i]=ex_boy[i]=ex_girl[i]=0; for (int j=1;j<=cnt1;j++) if (rela[i][j]>ex_girl[i]) ex_girl[i]=rela[i][j]; } for (int i=1;i<=cnt1;i++) { now=0; for (int j=1;j<=cnt1;j++) { slack[j]=INF; vis_boy[j]=vis_girl[j]=0; } while (true) { now++; if (dfs(i)) break; int d=INF; for (int j=1;j<=cnt1;j++) if (vis_boy[j]!=now&&slack[j]<d) d=slack[j]; for (int j=1;j<=cnt1;j++) { if (vis_girl[j]==now) ex_girl[j]-=d; if (vis_boy[j]==now) ex_boy[j]+=d; else slack[j]-=d; } } } long long ans=0; for (int i=1;i<=cnt1;i++) ans+=rela[match[i]][i]; return ans; } int main() { while (~scanf("%d%d",&n,&m)) { if (n==0&&m==0) break; cnt1=0;cnt2=0; for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) { cin>>s[i][j]; if (s[i][j]=='m') map[i][j]=++cnt1; if (s[i][j]=='H') map[i][j]=++cnt2; } for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) if (s[i][j]=='m') for (int x=1;x<=n;x++) for (int y=1;y<=m;y++) if (s[x][y]=='H') rela[map[i][j]][map[x][y]]=-get_cost(i,j,x,y); printf("%lld\n",-KM()); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator