用最小的代价抓住所有兔子,显然就是求图的最小割,又因为最小割等于最大流,考虑直接跑网络流
注意是无向图,正向和反向边都要将流量设置为$x$
此题直接$dinic$会$gg$,要用当前弧优化
/* Never Island */
/*deco loves Chino*/
/* Summer Pockets */
#include <bits/stdc++.h>
using namespace std;
int head[1000010],cur[1000010],n,m;
int dis[1000010],cnt=1,s,t;
struct edge
{
int next,to,dis;
}e[8000010];
void add(int u,int v,int d)
{
e[++cnt].to=v;
e[cnt].next=head[u];
e[cnt].dis=d;
head[u]=cnt;
}
int id(int x,int y)
{
return (x-1)*m+y;
}
queue<int> q;
int bfs()
{
memset(dis,-1,sizeof(dis));
memcpy(cur,head,sizeof(head));
q.push(s),dis[s]=0;
while(!q.empty())
{
int u=q.front();
q.pop();
for(int i=head[u];i;i=e[i].next)
{
int v=e[i].to;
if(dis[v]==-1&&e[i].dis>0)
{
dis[v]=dis[u]+1;
q.push(v);
}
}
}
return dis[t]!=-1;
}
int dfs(int u,int ex)
{
if(u==t||!ex)
{
return ex;
}
int flow=0;
for(int i=cur[u];i;i=e[i].next)
{
cur[u]=i;
int v=e[i].to;
if(dis[v]!=dis[u]+1||e[i].dis<=0)
{
continue;
}
int tmp=dfs(v,min(e[i].dis,ex));
if(!tmp)
{
continue;
}
ex-=tmp,flow+=tmp;
e[i].dis-=tmp,e[i^1].dis+=tmp;
if(!ex)
{
break;
}
}
return flow;
}
int read()
{
int x=0;
char ch=getchar();
while(!isdigit(ch))
{
ch=getchar();
}
while(isdigit(ch))
{
x=x*10+(ch-'0');
ch=getchar();
}
return x;
}
int main()
{
cin>>n>>m;
s=0,t=n*m+1;
for(int i=1;i<=n;i++)
{
for(int j=1;j<m;j++)
{
int x=read();
add(id(i,j),id(i,j+1),x);
add(id(i,j+1),id(i,j),x);
}
}
for(int i=1;i<n;i++)
{
for(int j=1;j<=m;j++)
{
int x=read();
add(id(i,j),id(i+1,j),x);
add(id(i+1,j),id(i,j),x);
}
}
for(int i=1;i<n;i++)
{
for(int j=1;j<m;j++)
{
int x=read();
add(id(i,j),id(i+1,j+1),x);
add(id(i+1,j+1),id(i,j),x);
}
}
add(s,id(1,1),0x3f3f3f3f);
add(id(1,1),s,0);
add(id(n,m),t,0x3f3f3f3f);
add(t,id(n,m),0);
int ans=0;
while(bfs())
{
ans+=dfs(s,0x3f3f3f3f);
}
cout<<ans;
}
deco 没有放弃