题解 P5796 【[CQOI2006]移动棋子】

· · 题解

题目传送门

这种匹配的问题一看就知道是网络流了吧qwq

因为n非常小。。。所以我们可以暴力枚举所有目标状态

然后从源点S向每一个初始节点连边权为1，费用为0的边

从每个目标节点向汇点T连一条边权为1，费用为0的边

对于每对(i,j)（i为第i个初始节点，j为第j个目标节点）

连一条边权为1，费用为最短路长度的边

最后跑最小费用最大流就可以了qwq

附上代码:

#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <queue>
#define INF 1000000000
#define M 10005
#define N 55
using namespace std;
int nxt[M],head[M],to[M],adj[M],cost[M],X[M],Y[M],XX[M],YY[M],nowX[M],nowY[M],dist[M],cur[M],F[N][N][N];
int mincost,tot,n,m,S,T,Ans=INF;
bool inq[M],vis[M],G[N][N];
int dx[10]={0,1,-1,0,0};
int dy[10]={0,0,0,1,-1};
int read(){//没什么用的快速读入
    int ans=0;char c=getchar();
    while (c<'0'||c>'9') c=getchar();
    while (c>='0'&&c<='9') ans=ans*10+c-'0',c=getchar();
    return ans;
}
void Write(int x){//没什么用的快速输出
    if (x<0) putchar('-'),x=-x;
    if (x<10) putchar(x^48);
    else Write(x/10),putchar((x%10)^48);
    return;
}
void add(int u,int v,int w,int Cost){
    nxt[tot]=head[u];head[u]=tot;to[tot]=v;adj[tot]=w;cost[tot]=Cost;tot++;
    nxt[tot]=head[v];head[v]=tot;to[tot]=u;adj[tot]=0;cost[tot]=-Cost;tot++;
    return;
}
bool SPFA(){
    for (register int i=S;i<=T;i++) dist[i]=INF,inq[i]=0;
    queue <int> Q;Q.push(T);inq[T]=1;dist[T]=0;
    while (!Q.empty()){
        int now=Q.front();Q.pop();inq[now]=0;
        for (register int i=head[now];~i;i=nxt[i])
            if (adj[i^1]>0&&dist[to[i]]>dist[now]-cost[i]){
                dist[to[i]]=dist[now]-cost[i];
                if (!inq[to[i]]) inq[to[i]]=1,Q.push(to[i]);
            }
    }
    return dist[S]<INF;
}
int dfs(int x,int low){
    vis[x]=1;if (x==T) return low;int used=0,a;
    for (register int &i=cur[x];~i;i=nxt[i])
        if (!vis[to[i]]&&adj[i]>0&&dist[to[i]]==dist[x]-cost[i]){
            a=dfs(to[i],min(low-used,adj[i]));
            if (a) adj[i]-=a,adj[i^1]+=a,mincost+=a*cost[i],used+=a;
            if (used==low) break;
        }
    return used;
}
int costflow(){
    int ans=0,a;
    while (SPFA()){
        vis[T]=1;
        while (vis[T]){
            for (register int i=S;i<=T;i++) cur[i]=head[i],vis[i]=0;
            while (a=dfs(S,INF)) ans+=a;
        }
    }
    return mincost;
}
int work(){
    memset(head,-1,sizeof(head));mincost=tot=0;//记得初始化
    for (register int i=1;i<=n;i++)
        if (G[nowX[i]][nowY[i]]) return INF;//判断目标状态是否合法
    for (register int i=1;i<=n;i++){
        add(S,i+1,1,0),add(i+n+1,T,1,0);
        for (register int j=1;j<=n;j++) add(i+1,j+n+1,1,F[i][nowX[j]][nowY[j]]);
    }
    return costflow();
}
void BFS(int x){//BFS找最短路
    queue <pair<int,int> > Q;
    for (register int i=1;i<=n;i++)
        for (register int j=1;j<=n;j++) F[x][i][j]=INF;
    F[x][X[x]][Y[x]]=0;Q.push(make_pair(X[x],Y[x]));
    while (!Q.empty()){
        pair <int,int> now=Q.front();Q.pop();
        for (register int i=1;i<=4;i++){
            int xx=now.first+dx[i],yy=now.second+dy[i];
            if (xx<1||xx>n||yy<1||yy>n||F[x][xx][yy]<INF||G[xx][yy]) continue;
            F[x][xx][yy]=F[x][now.first][now.second]+1;
            Q.push(make_pair(xx,yy));
        }
    }
    return;
}
int main(){
    n=read(),m=read();S=1,T=n+n+2;
    for (register int i=1;i<=n;i++) X[i]=read(),Y[i]=read();
    for (register int i=1,x,y;i<=m;i++) x=read(),y=read(),G[x][y]=1;
    for (register int i=1;i<=n;i++) BFS(i);
    for (register int i=1;i<=n;i++){
        for (register int j=1;j<=n;j++) nowX[j]=i,nowY[j]=j;
        Ans=min(Ans,work());
        for (register int j=1;j<=n;j++) nowX[j]=j,nowY[j]=i;
        Ans=min(Ans,work());
    }
    for (register int i=1;i<=n;i++) nowX[i]=nowY[i]=i;
    Ans=min(Ans,work());
    for (register int i=1;i<=n;i++) nowX[i]=i,nowY[i]=n+1-i;
    Ans=min(Ans,work());
    Write(Ans==INF?-1:Ans);//不要忘了输出-1
    return 0;
}

虽然代码长但不难写qwq

记得点赞啊