bzoj 4823 & 洛谷 P3756 老C的方块 —— 最小割

题目：https://www.lydsy.com/JudgeOnline/problem.php?id=4823

https://www.luogu.org/problemnew/show/P3756

巧妙建图；

其实“俄罗斯方块”就是选择一条特殊边两边的方格，左右两边周围的六个中再各选两个；

于是可以把图“四分”，特殊边两边的格子算两种，而且奇数行和偶数行恰好相反，然后两边围着的格子也算两种；

然后不能有上面四种可选方格同时存在的情况，建出图来跑最小割即可。

代码如下：

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<map>

#include<queue>

using namespace std;

int const xn=2e5+,xm=2e6+,inf=1e9;

int C,R,n,hd[xn],ct=,to[xm],nxt[xm],c[xm],dis[xn],cur[xn],S,T;

map<int,int>mp[xn];

struct N{int x,y;}p[xn];

queue<int>q;

int rd()

{

  int ret=,f=; char ch=getchar();

  while(ch<''||ch>''){if(ch=='-')f=; ch=getchar();}

  while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();

  return f?ret:-ret;

}

void ade(int x,int y,int z){to[++ct]=y; nxt[ct]=hd[x]; hd[x]=ct; c[ct]=z;}

void add(int x,int y,int z){ade(x,y,z); ade(y,x,);}

int tp(int x,int y)

{

  int d=y%;

  if(x&){if(d==)return ; if(d==)return ; if(d==)return ; if(!d)return ;}

  else {if(d==)return ; if(d==)return ; if(d==)return ; if(!d)return ;}

}

void addedge(int a,int b,int x,int y)

{

  if(a==&&b==)add(n+x,y,inf);

  else if(a==&&b==)add(n+x,y,inf);

  else if(a==&&b==)add(n+x,y,inf);

}

bool bfs()

{

  for(int i=S;i<=T;i++)dis[i]=;

  dis[S]=; q.push(S);

  while(q.size())

    {

      int x=q.front(); q.pop();

      for(int i=hd[x],u;i;i=nxt[i])

    if(!dis[u=to[i]]&&c[i])dis[u]=dis[x]+,q.push(u);

    }

  return dis[T];

}

int dfs(int x,int fl)

{

  //printf("x=%d fl=%d\n",x,fl);

  if(x==T)return fl;

  int ret=;

  for(int &i=cur[x],u;i;i=nxt[i])

    {

      if(dis[u=to[i]]!=dis[x]+||!c[i])continue;

      int tmp=dfs(u,min(fl-ret,c[i]));

      if(!tmp)dis[u]=;

      c[i]-=tmp; c[i^]+=tmp;

      ret+=tmp; if(ret==fl)break;

    }

  return ret;

}

int main()

{

  C=rd(); R=rd(); n=rd(); S=; T=*n+;

  for(int i=,x,y,w;i<=n;i++)

    {

      y=p[i].y=rd(); x=p[i].x=rd(); w=rd();

      mp[x][y]=i; add(i,n+i,w);

      int t=tp(p[i].x,p[i].y);

      if(t==)add(S,i,inf);

      if(t==)add(n+i,T,inf);

    }

  for(int i=;i<=n;i++)

    {

      int x=p[i].x,y=p[i].y,t=tp(x,y);

      if(x>&&mp[x-][y]){int tt=tp(x-,y); addedge(t,tt,i,mp[x-][y]);}

      if(y>&&mp[x][y-]){int tt=tp(x,y-); addedge(t,tt,i,mp[x][y-]);}

      if(x<R&&mp[x+][y]){int tt=tp(x+,y); addedge(t,tt,i,mp[x+][y]);}

      if(y<C&&mp[x][y+]){int tt=tp(x,y+); addedge(t,tt,i,mp[x][y+]);}

    }

  int ans=;

  while(bfs())

    {

      memcpy(cur,hd,sizeof hd);

      ans+=dfs(S,inf);

    }

  printf("%d\n",ans);

  return ;

}