网络流学习笔记II

xtx1092515503 · 2021-01-28 17:31:25 · 个人记录

这里是网络流学习笔记II。上一篇笔记写够一百题了，故开个新坑。

本文中各种约定同上一篇笔记中一致。

现在开始！

CI.[国家集训队]部落战争

第一题，挑道比较板子的题罢。

首先很明显可以抽象出一张从一个位置走到另一个的有向无环图出来（因为只能从上往下打）

然后就是最小路径覆盖问题的板子。很遗憾的是，我忘记了最小路径覆盖问题的解法，于是使用了XLIII.[SDOI2010]星际竞速中的拆点+最小费用最大流的做法，一样能过，就是被卡掉一个点，不得不吸氧。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,a,b;
char s[60][60];
namespace MCMF{
    const int N=5010,M=200000;
    int head[N],cnt,dis[N],fr[N],id[N],S,T,cost;
    struct node{
        int to,next,val,cost;
    }edge[M];
    void ae(int u,int v,int w,int c){
    //  printf("%d %d %d %d\n",u,v,w,c);
        edge[cnt].cost=c,edge[cnt].next=head[u],edge[cnt].to=v,edge[cnt].val=w,head[u]=cnt++;
        edge[cnt].cost=-c,edge[cnt].next=head[v],edge[cnt].to=u,edge[cnt].val=0,head[v]=cnt++;
    }
    queue<int>q;
    bool in[N];
    bool SPFA(){
        memset(dis,0x3f,sizeof(dis)),dis[S]=0,q.push(S),in[S]=true;
        while(!q.empty()){
            int x=q.front();q.pop(),in[x]=false;
    //      printf("%d\n",x);
            for(int i=head[x];i!=-1;i=edge[i].next){
                if(!edge[i].val)continue;
                if(dis[edge[i].to]>dis[x]+edge[i].cost){
                    dis[edge[i].to]=dis[x]+edge[i].cost,fr[edge[i].to]=x,id[edge[i].to]=i;
                    if(!in[edge[i].to])in[edge[i].to]=true,q.push(edge[i].to);
                }
            }
        }
        if(dis[T]==dis[T+1])return false;
        int x=T,mn=0x3f3f3f3f;
        while(x!=S)mn=min(mn,edge[id[x]].val),x=fr[x];
        cost+=dis[T]*mn,x=T;
        while(x!=S)edge[id[x]].val-=mn,edge[id[x]^1].val+=mn,x=fr[x];
        return true;
    }
}
using namespace MCMF;
int main(){
    scanf("%d%d%d%d",&n,&m,&a,&b),S=2*n*m,T=S+1,memset(head,-1,sizeof(head));
    int dx[4]={a,b,b,a},dy[4]={-b,-a,a,b};
    for(int i=0;i<n;i++)scanf("%s",s[i]);
    for(int i=0;i<n;i++)for(int j=0;j<m;j++){
        if(s[i][j]=='x')continue;
        ae(S,i*m+j,1,0);
        ae(i*m+j,T,1,1);
        ae(n*m+i*m+j,T,1,0);
        for(int k=0;k<4;k++){
            int ii=i+dx[k],jj=j+dy[k];
            if(ii<0||ii>=n||jj<0||jj>=m||s[ii][jj]=='x')continue;
    //      printf("(%d,%d):(%d,%d)\n",i,j,ii,jj);
            ae(i*m+j,n*m+ii*m+jj,1,0);
        }
    }
    while(SPFA());
//  for(int i=0;i<cnt;i++)if(edge[i^1].val&&edge[i^1].to<n*m)printf("%d->%d\n",edge[i^1].to,edge[i].to);
    printf("%d\n",cost);
    return 0;
} 

CII.[NOI2015]小园丁与老司机

首先，老司机部分考虑DP：明显 y 值不同的状态间转移是有阶段性的，但是 y 值相同时则不然；于是为了凸显阶段性，我们设 f_x 表示从位置 x 进入某个 y 值的最大收益，g_x 表示从位置 x 离开某个 y 值的最大收益。