Loading...

bzoj 1001 狼抓兔子

check评论:0 条 remove_red_eye浏览量:43 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2019-11-17

地址

用最小的代价抓住所有兔子,显然就是求图的最小割,又因为最小割等于最大流,考虑直接跑网络流

注意是无向图,正向和反向边都要将流量设置为$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 没有放弃

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名