P7198 [CTSC2002] 玩具兵 题解

· · 题解

题面

题面过长，见 P7198，此处不再赘述。

分析

容易得知：

所以我们不妨直接将天兵移到终点，然后观察其他玩具兵如何行走。

先考虑一次都不能发动超能力判定能否全部到达终点，对于每个骑兵和步兵需要有一条单调递增或者递减的序列从起点走到终点（非严格），由于终点没有确定，我们自然想到了二分图匹配：对于每个骑兵或者步兵，找到所有能到的终点连边，跑一遍匈牙利算法即可。

然后考虑要发动超能力，那么设我们找到了每个点与之匹配的终点，我们可以对于每个点在 O(n^2 \log n) 的时间复杂度用广义最短路知道它到终点至少变动多少次（即：从骑兵变为步兵或者从步兵变为骑兵），这个问题很简单，这里就不再过多说明。

那么我们发现，发动超能力的次数对于这种选终点的方法就是所有点到终点至少变动次数的最大值。

此处简化一下问题：假如没有天兵，那么最少发动多少次超能力。

这个问题可以二分解决，先预处理每个起点到终点最少变动多少次，二分超能力的次数，然后删去从某个起点到终点的大于这个次数的边，看匹配是否等于起点的个数就可以了。（此处的起点不包括天兵的起点，即 2k 个，终点有 2k+1 个）

最后考虑有天兵的情况，天兵在一次超能力的过程中可以送一个骑兵或者步兵到达某一个终点，并且天兵移动不受限制，故天兵可以不用超能力到达一个终点。

结合上个问题，天兵可以免费帮你把一条边边权设为 0，设一共去掉了 x 条边，那么二分图匹配的花费就需要与 x 取 \max。

这个问题就很简单了，二分可以解决，但是我写的是暴力枚举边权，都可以在规定时间内通过。

代码

#include<bits/stdc++.h>
#define N 205
#define ll long long
using namespace std;
struct node{
    ll x,y,z,t;
    bool operator<(const node& a)const{
        return a.t<t;
    }
}tmp;
ll n,m,k,t,x[N],y[N],z[N],a[N],b[N],aa,bb,cc,tot,i,j,maps[N][N],dp[N][N][2],sum,ans=1e18,cnt,vis[N],link[N];
ll edge[N][N],px[4]={0,0,1,-1},py[4]={1,-1,0,0};
priority_queue<node> q;
void solve(){
    while(q.size()){
        tmp = q.top(),q.pop();
        if(dp[tmp.x][tmp.y][tmp.z]!=tmp.t) continue;
        for(ll i=0;i<4;i++){
            ll tx = tmp.x+px[i],ty = tmp.y+py[i];
            if(tx<1||tx>n||ty<1||ty>m) continue;
            if(tmp.z==0){
                if(maps[tmp.x][tmp.y]<=maps[tx][ty]){
                    if(dp[tx][ty][0]>tmp.t){
                        dp[tx][ty][0] = tmp.t;
                        q.push((node){tx,ty,0,tmp.t});
                    }
                }
                else{
                    if(dp[tx][ty][1]>tmp.t+1){
                        dp[tx][ty][1] = tmp.t+1;
                        q.push((node){tx,ty,1,tmp.t+1});
                    }
                }
            }
            else{
                if(maps[tmp.x][tmp.y]>=maps[tx][ty]){
                    if(dp[tx][ty][1]>tmp.t){
                        dp[tx][ty][1] = tmp.t;
                        q.push((node){tx,ty,1,tmp.t});
                    }
                }
                else{
                    if(dp[tx][ty][0]>tmp.t+1){
                        dp[tx][ty][0] = tmp.t+1;
                        q.push((node){tx,ty,0,tmp.t+1});
                    }
                }
            }
        }
    }
}
bool dfs(ll x,ll r,ll p){
    for(ll i=1;i<=2*k+1;i++){
        if(edge[x][i]>p) continue;
        if(vis[i]==r) continue;
        vis[i] = r;
        if(!link[i]||dfs(link[i],r,p)){
            link[i] = x;
            return 1;
        }
    }
    return 0;
}
ll solve(ll x){
    ll cnt = 0;
    for(ll i=1;i<=2*k+1;i++) vis[i]=0,link[i]=0;
    for(ll i=1;i<=2*k;i++) cnt+=dfs(i,i,x);
    return cnt;
}
int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m>>k>>t;
    for(i=1;i<=2*k+1;i++){
        cin>>x[i]>>y[i];
        if(i<=k) z[i]=0;
        else if(i<=2*k) z[i]=1;
        else z[i]=2;
    }
    for(i=1;i<=t;i++){
        cin>>aa>>bb>>cc;
        while(cc){
            tot++;
            a[tot] = aa,b[tot] = bb;
            cc--;
        }
    }
    for(i=1;i<=n;i++) for(j=1;j<=m;j++) cin>>maps[i][j];
    for(i=1;i<=2*k;i++){
        memset(dp,0x3f,sizeof(dp));
        dp[x[i]][y[i]][z[i]] = 0;
        q.push((node){x[i],y[i],z[i],0});
        solve();
        for(j=1;j<=2*k+1;j++) edge[i][j]=min(dp[a[j]][b[j]][0],dp[a[j]][b[j]][1]);
    }
    for(i=0;i<=2*n;i++){
        cnt = solve(i);
        if(i>=2*k-cnt) ans=min(ans,i);
    }
    cout<<ans<<endl;
    return 0;
}