部落战争（建图+最小路径覆盖）

传送门

题目求最少要多少支军队可以把所有城镇覆盖完（DAG的最小不相交路径覆盖）

军队只能向下走，所以建图时就往四个方向连边，最后跑一下最小路径覆盖即可（=点数 - 二分图最大匹配）

#include<bits/stdc++.h>
#define N 53
using namespace std;
int read()
{
    int x=0,f=1;char s=getchar();
    while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
    while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
    return x*f;
}
int ud[5],lr[5],ord[N][N],head[N*N],vis[N*N],match[N*N];
int ndnum=0,tot=0,n,m,timer=0;
char s[N],mp[N][N];
struct EDGE{
    int to,nextt;
}w[N*N*N*N];
void add(int a,int b)
{
    tot++;
    w[tot].nextt=head[a];
    w[tot].to=b;
    head[a]=tot;
}
void build_tu()
{
    for(int i=1;i<=m;++i)
      for(int j=1;j<=n;++j)
        for(int k=0;k<4;++k)
        {
            if(mp[i][j]!='.')continue;
            int xx=i+ud[k],yy=j+lr[k];
            if(mp[xx][yy]=='.'&&xx>=1&&xx<=m&&yy>=1&&yy<=n)
              add(ord[i][j],ord[xx][yy]);
        }
}
int dfs(int x)//匈牙利求最大匹配 
{
    if(vis[x]==timer)return 0;
    vis[x]=timer;
    for(int i=head[x];i;i=w[i].nextt)
    {
        int v=w[i].to;
        if(!match[v]||dfs(match[v]))
        {
            match[v]=x;
            return 1;
        }
    } 
    return 0;
}
void work()//求最小路径覆盖
{
    int sum=0,ans=0;
    for(int i=1;i<=m;++i)
      for(int j=1;j<=n;++j)
      {
          if(mp[i][j]=='.')
          {
              sum++;
              timer++;
              if(dfs(ord[i][j]))ans++;
        }
      }
    printf("%d
",sum-ans);
} 
int main()
{
    m=read(),n=read();int r=read(),c=read();
    ud[0]=r;ud[1]=r;ud[2]=c;ud[3]=c;
    lr[0]=c;lr[1]=-c;lr[2]=r;lr[3]=-r;
    for(int i=1;i<=m;++i)
    {
        scanf("%s",s+1);
        for(int j=1;j<=n;++j)
        {
            mp[i][j]=s[j];
            ++ndnum;
            ord[i][j]=ndnum;
        }
    }
    build_tu();
    work();
}