Loading...

P1646 [国家集训队]happiness

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

一道海星的网络流ww

题目让你求最大值,只能选一次的限制显然说明了是一道网络流,但是网络流最大流&最小割并不能解决求最大值,正难则反,考虑改变为割掉一些边求最小值,显然就是一个最小割的题目,为了保证同时割掉两条边是必须割掉两个点同时选是额外价值的边,我们将他们与额外价值的新点的边流量设置为$+\infty$,这样就保证了必须同时割掉

不用当前弧会$T$

#include <bits/stdc++.h>
using namespace std;
int dis[50010],head[50010],cur[50010],n,m,cnt=1,s,t,tot;
struct edge
{
    int next,to,dis;
}e[2000100];
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 bfs()
{
    memset(dis,-1,sizeof(dis));
    memcpy(cur,head,sizeof(head));
    dis[s]=0;
    queue<int> q;
    q.push(s);
    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)
    {
        int v=e[i].to;
        cur[u]=i;
        if(dis[v]!=dis[u]+1||e[i].dis<=0)
        {
            continue;
        }
        int tmp=dfs(v,min(e[i].dis,ex));
        if(!tmp)
        {
            continue;
        }
        flow+=tmp,ex-=tmp;
        e[i].dis-=tmp,e[i^1].dis+=tmp;
        if(!ex)
        {
            break;
        }
    }
    return flow;
}
int id(int x,int y)
{
    return (x-1)*m+y;
}
int main()
{
    cin>>n>>m;
    int qwq=0;
    s=0,t=5*n*m-n-m+1;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            int x;
            scanf("%d",&x);
            qwq+=x;
            add(s,id(i,j),x);
            add(id(i,j),s,0);
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            int x;
            scanf("%d",&x);
            qwq+=x;
            add(id(i,j),t,x);
            add(t,id(i,j),0);
        }
    }
    tot=n*m;
    for(int i=1;i<n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            int x;
            scanf("%d",&x);
            qwq+=x;
            ++tot;
            add(s,tot,x);
            add(tot,s,0);
            add(tot,id(i,j),0x3f3f3f3f);
            add(id(i,j),tot,0);
            add(tot,id(i+1,j),0x3f3f3f3f);
            add(id(i+1,j),tot,0);
        }
    }
    for(int i=1;i<n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            int x;
            scanf("%d",&x);
            qwq+=x;
            ++tot;
            add(tot,t,x);
            add(t,tot,0);
            add(id(i,j),tot,0x3f3f3f3f);
            add(tot,id(i,j),0);
            add(id(i+1,j),tot,0x3f3f3f3f);
            add(tot,id(i+1,j),0);
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<m;j++)
        {
            int x;
            scanf("%d",&x);
            qwq+=x;
            ++tot;
            add(s,tot,x);
            add(tot,s,0);
            add(tot,id(i,j),0x3f3f3f3f);
            add(id(i,j),tot,0);
            add(tot,id(i,j+1),0x3f3f3f3f);
            add(id(i,j+1),tot,0);
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<m;j++)
        {
            int x;
            scanf("%d",&x);
            qwq+=x;
            ++tot;
            add(tot,t,x);
            add(t,tot,0);
            add(id(i,j),tot,0x3f3f3f3f);
            add(tot,id(i,j),0);
            add(id(i,j+1),tot,0x3f3f3f3f);
            add(tot,id(i,j+1),0);
        }
    }
    while(bfs())
    {
        qwq-=dfs(s,0x3f3f3f3f);
    }
    cout<<qwq;
}

暂无评论

正在回复给  
去登陆?

   点击刷新验证码

标签云

文章留名