题目概述

ACL Contest 1C

解题报告

这题还是挺可做的，首先考虑棋子之间拦路的问题，在一颗棋子穿过了另一颗棋子时，我们可以认为两颗棋子互换位置，显然移动次数不变。

既然没有棋子之间互相拦路，不难发现这就是个二分图带权匹配的问题。

可以用KM算法（我早忘完了）或者费用流解决。

示例程序

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=50,maxt=2600,maxe=252600<<1;

int n,m,cnt;char pic[maxn+5][maxn+5];
int E,lnk[maxt+5],son[maxe+5],nxt[maxe+5],e[maxe+5],w[maxe+5];
int que[maxt+5],ti,vis[maxt+5],dis[maxt+5],MIN[maxt+5];

#define ID(x,y) (((x)-1)*m+(y))
inline void Add(int x,int y,int z,int c){
    son[E]=y;nxt[E]=lnk[x];lnk[x]=E;e[E]=z;w[E]=c;E++;
    son[E]=x;nxt[E]=lnk[y];lnk[y]=E;e[E]=0;w[E]=-c;E++;
}
void BFS(int X,int Y){
    int Head=0,Tail=0;que[++Tail]=ID(X,Y);vis[ID(X,Y)]=++ti;
    while (Head!=Tail){
        int now=que[++Head],x=(now-1)/m+1,y=(now-1)%m+1;
        if (y<m && vis[ID(x,y+1)]<ti && pic[x][y+1]!='#') que[++Tail]=ID(x,y+1),vis[ID(x,y+1)]=ti;
        if (x<n && vis[ID(x+1,y)]<ti && pic[x+1][y]!='#') que[++Tail]=ID(x+1,y),vis[ID(x+1,y)]=ti;
    }
    Add(cnt,ID(X,Y)+100,1,0);
    for (int i=1,now,x,y;i<=Tail;i++){
        now=que[i];x=(now-1)/m+1;y=(now-1)%m+1;
        if (pic[x][y]!='o') Add(cnt,ID(x,y)+100,1,x-X+y-Y);
    }
}
bool Spfa(int s,int t,int &MC){
    static int fa[maxt+5],ID[maxt+5];
    for (int i=s;i<=t;i++) dis[i]=-2e9;
    int Head=0,Tail=0;que[++Tail]=s;vis[s]=++ti;dis[s]=0;MIN[s]=2e9;
    while (Head!=Tail){
        int x=que[Head=(Head+1)%maxt];vis[x]=0;
        for (int j=lnk[x],u;~j;j=nxt[j])
            if (e[j] && dis[x]+w[j]>dis[u=son[j]]){
                dis[u]=dis[x]+w[j];MIN[u]=min(MIN[x],e[j]);fa[u]=x;ID[u]=j;
                if (vis[u]<ti) que[Tail=(Tail+1)%maxt]=u,vis[u]=ti;
            }
    }
    if (dis[t]<0) return false;MC+=dis[t]*MIN[t];
    for (int x=t,j;x!=s;x=fa[x]) j=ID[x],e[j]-=MIN[t],e[j^1]+=MIN[t];
    return true;
}
int MCMF(int s,int t) {int MC=0;while (Spfa(s,t,MC));return MC;}
int main(){
    freopen("C.in","r",stdin);freopen("C.out","w",stdout);
    scanf("%d%d",&n,&m);memset(lnk,255,sizeof(lnk));
    for (int i=1;i<=n;i++) scanf("%s",pic[i]+1);
    for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) if (pic[i][j]=='o') cnt++,BFS(i,j);
    for (int i=1;i<=cnt;i++) Add(0,i,1,0);for (int i=101;i<=n*m+100;i++) Add(i,n*m+101,1,0);
    printf("%d\n",MCMF(0,n*m+101));return 0;
}