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

一个不合法方案其实就是蓝线的两边格子一定选、剩下两部分四相邻格子里各选一个。

所以这个图是一个四分图。记蓝线左边格子是1,右边是2,与 1 四相邻的是3,与 2 四相邻的是4;这个部分右边就是蓝线左边是2、右边是1,这样。

有一些“4个格子不能同时选”的限制,考虑怎么在图中表示。

需要做到的是4个格子里割掉一个就能让这条路径废掉,那么应该是把有联系的4个点连成一条链。因为是4分图,所以能做到。

一个格子可能在很多路径里,如果在路径的边上放权值,不能表示割掉这个格子可以使很多路径都废掉。所以把格子拆成两个点,自己向自己连的边上放权值即可。

map 是一个有序结构,所以结构体的话要定义小于号。如果只定义了 x<b.x ,那么在 x==b.x 的时候 map 会认为这是同一个点!即使它们的 y 不同。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std;
const int N=2e5+,M=2e6+,INF=1e9+;
int n,r,c,t,x[N],y[N],w[N];
int hd[N],xnt=,cur[N],to[M],nxt[M],cap[M];
int dfn[N],q[N],he,tl;
struct Node{
int x,y;
Node(int a=,int b=):x(a),y(b) {}
bool operator< (const Node &b)const
{return x==b.x?y<b.y:x<b.x;}//////x<b.x will rec x==b.x as the same point
};
map<Node,int> mp;
int Mn(int a,int b){return a<b?a:b;}
int rdn()
{
int ret=;bool fx=;char ch=getchar();
while(ch>''||ch<''){if(ch=='-')fx=;ch=getchar();}
while(ch>=''&&ch<='')ret=ret*+ch-'',ch=getchar();
return fx?ret:-ret;
}
void add(int x,int y,int z)
{
to[++xnt]=y;nxt[xnt]=hd[x];hd[x]=xnt;cap[xnt]=z;
to[++xnt]=x;nxt[xnt]=hd[y];hd[y]=xnt;cap[xnt]=;
}
bool bfs()
{
memset(dfn,,sizeof dfn);dfn[]=;
q[he=tl=]=;
while(he<=tl)
{
int k=q[he++];
for(int i=hd[k],v;i;i=nxt[i])
if(cap[i]&&!dfn[v=to[i]])
dfn[v]=dfn[k]+,q[++tl]=v;
}
return dfn[t];
}
int dinic(int cr,int flow)
{
if(cr==t)return flow;
int use=;
for(int& i=cur[cr],v;i;i=nxt[i])
if(cap[i]&&dfn[v=to[i]]==dfn[cr]+)
{
int tmp=dinic(v,Mn(flow-use,cap[i]));
if(!tmp)dfn[v]=;
use+=tmp;cap[i]-=tmp;cap[i^]+=tmp;
if(use==flow)return use;
}
return use;
}
int main()
{
c=rdn();r=rdn();n=rdn();
for(int i=;i<=n;i++)
{
y[i]=rdn();x[i]=rdn();w[i]=rdn();//y[] then x[]
mp[Node(x[i],y[i])]=i;
}
t=(n<<)+; Node o;
for(int i=;i<=n;i++)
{
add(i,i+n,w[i]);
int u=(x[i]&),v=(y[i]&);
if((u&&!v)||(!u&&v==))add(,i,INF);//
else if((u&&v==)||(!u&&v==))add(i+n,t,INF);//
else if((u&&v==)||(!u&&!v))//
{
if(mp.count(o=Node(x[i]-,y[i])))//3->1
add(mp[o]+n,i,INF);
if(mp.count(o=Node(x[i]+,y[i])))
add(mp[o]+n,i,INF);
if(mp.count(o=Node(x[i],y[i]+)))//1>2 or 3>1
u?add(i+n,mp[o],INF):add(mp[o]+n,i,INF);
if(mp.count(o=Node(x[i],y[i]-)))
u?add(mp[o]+n,i,INF):add(i+n,mp[o],INF);
}
else//
{
if(mp.count(o=Node(x[i]-,y[i])))
add(i+n,mp[o],INF);
if(mp.count(o=Node(x[i]+,y[i])))
add(i+n,mp[o],INF);
if(mp.count(o=Node(x[i],u?y[i]+:y[i]-)))
add(i+n,mp[o],INF);
}
}
int ans=;
while(bfs())memcpy(cur,hd,sizeof hd),ans+=dinic(,INF);
printf("%d\n",ans);
return ;
}
05-11 22:21
查看更多