D – 文理分科 (最小割)

  • 2019-02-03
  • 0
  • 0

题目链接:https://cn.vjudge.net/contest/281959#problem/D

题意:给定一个m*n的矩阵,每个格子的人可以学文或者学理,学文和学理各有一个满意度,如果以某人为中心的十字内所有人都学文或者学理还会得到一个额外满意度,求最大满意度之和

最小割建图:http://www.cnblogs.com/chenyushuo/p/5146626.html?tdsourcetag=s_pctim_aiomsg
该题建图:https://blog.csdn.net/frods/article/details/54910596
参考代码:https://blog.csdn.net/PoPoQQQ/article/details/43968017

#include <bits/stdc++.h>

using namespace std;
#define ll long long
const int inf=0x3f3f3f3f;
struct node
{
    int to,w,next;
}e[1000005];
int n,m,id[5500][5500],s,t,sum=0,num=0;
int dx[5]={0,0,0,1,-1};
int dy[5]={0,1,-1,0,0};
int head[100005],cnt,cur[1000005],deep[1000005];
int maxflow;

void init()
{
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            id[i][j]=++num;
        }
    }
    s=0;
    t=3*num+1;
    memset(head,-1,sizeof(head));
    cnt=0;
}

void add(int u,int v,int w)
{
    e[cnt]=node{v,w,head[u]};
    head[u]=cnt++;
}

bool bfs()
{
    for(int i=s;i<=t;i++)
    {
        cur[i]=head[i];
    }
    memset(deep,inf,sizeof(deep));
    queue<int>q;
    deep[s]=0;
    q.push(s);
    while(!q.empty())
    {
        int x=q.front();
        q.pop();
        for(int i=head[x];i!=-1;i=e[i].next)
        {
            int to=e[i].to;
            int w=e[i].w;
            if(deep[to]>=inf&&w>0)
            {
                deep[to]=deep[x]+1;
                q.push(to);
            }
        }
    }
    if(deep[t]<inf)return true;
    else return false;
}

int dfs(int x,int limit)
{
    if(x==t||!limit)return limit;
    int flow=0;
    for(int i=cur[x];i!=-1;i=e[i].next)
    {
        cur[x]=i;
        int to=e[i].to;
        int w=e[i].w;
        if(deep[to]==deep[x]+1)
        {
            int a=dfs(to,min(limit,w));
            flow+=a;
            limit-=a;
            e[i].w-=a;
            e[i^1].w+=a;
        }
        if(!limit)break;
    }
    return flow;
}

void dinic()
{
    while(bfs())
    {
        maxflow+=dfs(s,inf);
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>m;
    init();
    int x;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>x;
            sum+=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++)
        {
            cin>>x;
            sum+=x;
            add(id[i][j],t,x);
            add(t,id[i][j],0);
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>x;
            sum+=x;
            add(s,id[i][j]+m*n,x);
            add(id[i][j]+m*n,s,0);
            for(int k=0;k<5;k++)
            {
                int xx=i+dx[k];
                int yy=j+dy[k];
                if(xx<1||xx>n||yy<1||yy>m)continue;
                add(id[i][j]+m*n,id[xx][yy],inf);
                add(id[xx][yy],id[i][j]+m*n,0);
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            cin>>x;
            sum+=x;
            add(id[i][j]+2*m*n,t,x);
            add(t,id[i][j]+2*m*n,0);
            for(int k=0;k<5;k++)
            {
                int xx=i+dx[k];
                int yy=j+dy[k];
                if(xx<1||xx>n||yy<1||yy>m)continue;
                add(id[xx][yy],id[i][j]+2*m*n,inf);
                add(id[i][j]+2*m*n,id[xx][yy],0);
            }
        }
    }
    maxflow=0;
    dinic();
    cout<<sum-maxflow<<endl;
}

评论

还没有任何评论,你来说两句吧