文理分科 bzoj-3894
题目大意:题目链接。
注释:略。
想法:
这种题也是一种套路。
我们新建一个点表示收益点。
然后把所有的收益都加一起,求最小割表示代价即可。
Code:
#include <bits/stdc++.h>
#define inf 0x3f3f3f3f
#define N 1000100
using namespace std;
int to[N<<1],nxt[N<<1],head[N],val[N<<1],tot=1,dis[N],S,T;
queue<int>q;
int d1[]={1,-1,0,0,0};
int d2[]={0,0,1,-1,0};
char *p1,*p2,buf[100000];
#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
int rd() {int x=0,f=1; char c=nc(); while(c<48) {if(c=='-') f=-1; c=nc();} while(c>47) x=(((x<<2)+x)<<1)+(c^48),c=nc(); return x*f;}
inline void add(int x,int y,int z)
{
// printf("%d %d %d\n",x,y,z);
to[++tot]=y; val[tot]=z; nxt[tot]=head[x]; head[x]=tot;
to[++tot]=x; val[tot]=0; nxt[tot]=head[y]; head[y]=tot;
}
bool bfs()
{
memset(dis,-1,sizeof dis); while(!q.empty()) q.pop();
dis[S]=0; q.push(S); while(!q.empty())
{
int x=q.front(); q.pop(); for(int i=head[x];i;i=nxt[i]) if(dis[to[i]]==-1&&val[i]>0)
{
dis[to[i]]=dis[x]+1; q.push(to[i]);
if(to[i]==T) return true;
}
}
return false;
}
int dinic(int x,int fl)
{
int tmp=fl; if(x==T) return fl; for(int i=head[x];i;i=nxt[i]) if(dis[to[i]]==dis[x]+1&&val[i]>0)
{
int mdl=dinic(to[i],min(val[i],tmp));
if(!mdl) dis[to[i]]=-1;
val[i]-=mdl; val[i^1]+=mdl; tmp-=mdl;
if(!tmp) break;
}
return fl-tmp;
}
int main()
{
int ans=0;
int n=rd(),m=rd(); S=0; T=3*n*m+1;
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)
{
int x=rd(); add((i-1)*m+j,T,x); ans+=x;
}
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)
{
int x=rd(); add(S,(i-1)*m+j,x); ans+=x;
}
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)
{
int tt=n*m+(i-1)*m+j;
int v=rd(); add(tt,T,v); ans+=v;
for(int k=0;k<5;k++)
{
int x=i+d1[k],y=j+d2[k];
if(x>=1&&x<=n&&y>=1&&y<=m) add((x-1)*m+y,tt,inf);
}
}
for(int i=1;i<=n;i++) for(int j=1;j<=m;j++)
{
int tt=n*m*2+(i-1)*m+j;
int v=rd(); add(S,tt,v); ans+=v;
for(int k=0;k<5;k++)
{
int x=i+d1[k],y=j+d2[k];
if(x>=1&&x<=n&&y>=1&&y<=m) add(tt,(x-1)*m+y,inf);
}
}
while(bfs()) ans-=dinic(S,1<<30);
cout << ans << endl ;
return 0;
}
小结:这种模型要多积累。

京公网安备 11010502036488号