The 2022 ICPC Asia Xian Regional Contest

https://codeforces.com/gym/104077

B. Cells Coloring

题解

当我们选定一个 $k$ 后，所有每行每列选择不超过 $k$ 个的方案数都是合法的。所以我们可以建立网络流模型：源点向每行连容量为 $k$ 的边，若第 $i$ 行第 $j$ 列为空，第 $i$ 行向第 $j$ 列连容量为 $1$ 的边，每列向汇点连容量为 $k$ 的边。

我们从小到大增加 $k$，每次在残量网络上跑dinic就可以了。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=505;
const int inf=0x3f3f3f3f;
struct edge
{
    int to,nxt;
    int c;
}e[2*305*305];
int cnt=1,head[N];
int s,t;
int d[N],cur[N];
void add(int u,int v,int c)
{
    e[++cnt]={v,head[u],c};head[u]=cnt;
    e[++cnt]={u,head[v],0};head[v]=cnt;
}
bool bfs()
{
    memset(d,0,sizeof(d));
    queue<int> q;
    d[s]=1;q.push(s);
    while(!q.empty())
    {
        int u=q.front();q.pop();
        for(int i=head[u];i;i=e[i].nxt)
        {
            int v=e[i].to;
            if(d[v]==0&&e[i].c)
            {
                d[v]=d[u]+1;q.push(v);
                if(v==t) return true;
            }
        }
    }
    return false;
}
int dfs(int u,int mf)
{
    if(u==t) return mf;
    int sum=0;
    for(int i=cur[u];i;i=e[i].nxt)
    {
        cur[u]=i;
        int v=e[i].to;
        if(d[v]==d[u]+1&&e[i].c)
        {
            int res=dfs(v,min(mf,e[i].c));
            e[i].c-=res;
            e[i^1].c+=res;
            sum+=res;
            mf-=res;
            if(mf==0) break;
        }
    }
    if(sum==0) d[u]=0;
    return sum;
}
int dinic()
{
    int flow=0;
    while(bfs())
    {
        memcpy(cur,head,sizeof(cur));
        flow+=dfs(s,inf);
    }
    return flow;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n,m,c,d;cin>>n>>m>>c>>d;
    s=0,t=n+m+1;
    for(int i=1;i<=n;i++) add(s,i,0);
    for(int i=1;i<=m;i++) add(i+n,t,0);
    int z=0;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++)
        {
            char ch;cin>>ch;
            if(ch=='.') 
            {
                z++;
                add(i,j+n,1);
            }
        }
    ll ans=1ll*d*z;
    for(int k=1;k<=max(n,m);k++)
    {
        for(int i=2;i<=2*n;i+=2) e[i].c++;
        for(int i=2*n+2;i<=2*(n+m);i+=2) e[i].c++;
        z-=dinic();
        ans=min(ans,1ll*c*k+1ll*d*z);
    }
    cout<<ans<<'\n';
    return 0;
}

D. Contests

题解

每次从 $b_i$ 到 $b_{i+1}$ 的目的必然是走到另一个 $b_{i+1}$ 在 $b_i$ 前面的排列，为下一步创造空间。所以，每次移动的时候，我们关心的只是在每个排列中所能到达的最靠前的位置。令 $f_{i,j,k}$ 表示从 $i$ 出发，至多走 $2^k$ 步到排列 $j$ 的最靠前的位置，利用倍增进行维护。查询时，先判断是否能一步到达，若不能，就求出需要多少步能走能到一步到达的前一个位置，然后答案就是所需步数 +2（因为还要到该位置还需要再走两步）。