[CQOI2017]老C的方块-白红宇

[CQOI2017]老C的方块

阅读量：5057 次

发布时间：2019-06-12

本文共 2749 字，大约阅读时间需要 9 分钟。

题目描述

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

题解

观察那四种条件

有没有什么特点？

我们可以把蓝线两边的部分看做两个区域，这样的话任何一个不合法的匹配都是在蓝线两边都必须有格子，而且那两个格子的临近位置也需要有一个格子。

如果我们把蓝线两边的格子看做一个点，那不就是我们所熟悉的三元匹配模型了吗？

如果我们建出了图，求一下最小割就好了。

关键是这个图怎么建。

除了蓝线两边的以外的点黑白染色，匹配顺序为白->紫->紫->黑，就可以建出图来了。

代码

#include
     
      #include
      
       #include
       #include
        
         #include
         
          #define N 100002#define inf 2e9using namespace std;queue
          
           q;int tot=1,head[N],deep[N],cur[N],C,R,n;map
           
            mp[N];map
            
             ::iterator it;long long ans;inline int rd(){ int x=0;char c=getchar();bool f=0; while(!isdigit(c)){ if(c=='-')f=1;c=getchar();} while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();} return f?-x:x;}struct edge{ int n,to,l;}e[N*6];inline void add(int u,int v,int l){ e[++tot].n=head[u];e[tot].to=v;head[u]=tot;e[tot].l=l; e[++tot].n=head[v];e[tot].to=u;head[v]=tot;e[tot].l=0;}inline bool bfs(int s,int t){ memset(deep,0,sizeof(deep)); memcpy(cur,head,sizeof(head)); deep[s]=1;q.push(s); while(!q.empty()){ int u=q.front();q.pop(); for(int i=head[u];i;i=e[i].n){ int v=e[i].to; if(!deep[v]&&e[i].l){ deep[v]=deep[u]+1;q.push(v); } } } return deep[t];}int dfs(int u,int t,int l){ if(u==t||!l)return l; int f,flow=0; for(int &i=cur[u];i;i=e[i].n){ int v=e[i].to; if(deep[v]==deep[u]+1&&(f=dfs(v,t,min(l,e[i].l)))){ e[i].l-=f;e[i^1].l+=f;flow+=f;l-=f; if(!l)break; } } return flow;}struct block{ int u,v,w;}a[N];int main(){ C=rd();R=rd();n=rd(); for(int i=1;i<=n;++i){ a[i].u=rd();a[i].v=rd();a[i].w=rd(); swap(a[i].u,a[i].v); mp[a[i].u][a[i].v]=i; } for(int i=1;i<=n;++i){ if(a[i].u&1){ if(a[i].v%4==1){ it=mp[a[i].u].find(a[i].v+1); if(it!=mp[a[i].u].end()){ int x=it->second; add(i,x,min(a[i].w,a[x].w)); } } else if(a[i].v%4==2||a[i].v%4==0){ if(a[i].v%4==0)add(0,i,a[i].w); it=mp[a[i].u].find(a[i].v+1); if(it!=mp[a[i].u].end()){ int x=it->second; add(i,x,inf); } it=mp[a[i].u+1].find(a[i].v); if(it!=mp[a[i].u+1].end()){ int x=it->second; add(i,x,inf); } it=mp[a[i].u-1].find(a[i].v); if(it!=mp[a[i].u-1].end()){ int x=it->second; add(i,x,inf); } } else if(a[i].v%4==3){ add(i,n+1,a[i].w); } } else{ if(a[i].v%4==1||a[i].v%4==3){ if(a[i].v%4==1)add(0,i,a[i].w); it=mp[a[i].u].find(a[i].v-1); if(it!=mp[a[i].u].end()){ int x=it->second; add(i,x,inf); } it=mp[a[i].u+1].find(a[i].v); if(it!=mp[a[i].u+1].end()){ int x=it->second; add(i,x,inf); } it=mp[a[i].u-1].find(a[i].v); if(it!=mp[a[i].u-1].end()){ int x=it->second; add(i,x,inf); } } else if(a[i].v%4==0){ it=mp[a[i].u].find(a[i].v-1); if(it!=mp[a[i].u].end()){ int x=it->second; add(i,x,min(a[i].w,a[x].w)); } } else add(i,n+1,a[i].w); } } while(bfs(0,n+1))ans+=dfs(0,n+1,2e9); cout<