P4313 文理分科

猿柒

6个月前更新

120

P4313 文理分科

题目描述

文理分科是一件很纠结的事情！（虽然看到这个题目的人肯定都没有纠结过）

小 P 所在的班级要进行文理分科。他的班级可以用一个 $n\times m$ 的矩阵进行描述，每个格子代表一个同学的座位。每位同学必须从文科和理科中选择一科。同学们在选择科目的时候会获得一个满意值。满意值按如下的方式得到：

如果第 $i$ 行第 $j$ 列的同学选择了文科，则他将获得 $art_{i,j}$ 的满意值，如果选择理科，将得到 $science_{i,j}$ 的满意值。
如果第 $i$ 行第 $j$ 列的同学选择了文科，并且他相邻（两个格子相邻当且仅当它们拥有一条相同的边）的同学全部选择了文科，则他会更开心，所以会增加 $same\text{\underline{ }}art_{i,j}$ 的满意值。
如果第 $i$ 行第 $j$ 列的同学选择了理科，并且他相邻的同学全部选择了理科，则增加 $same\text{\underline{ }}science_{i,j}$ 的满意值。

小 P 想知道，大家应该如何选择，才能使所有人的满意值之和最大。请告诉他这个最大值。

数据范围

$n,m\leq 100$，读入数据均 $\leq 500$。

Solution:

说句闲话：

又是一道我拖了半年才写的题目，同时也是我的600AC。

言归正传：

我们考虑重新刻画一下第二类贡献：

对于一个同学 $x$ 如果他选了文科，并且所有与他相邻的同学都没选理科，才会产生 $same\text{\underline{ }}art_{i,j}$ 的贡献。

于是我们不难将这个问题用最小割来刻画。

对于一个节点 $x$：

连一条 $S$ 到 $x$ 流量为 $art_x$ 的边。
连一条 $x$ 到 $T$ 流量为 $science_x$ 的边。

这样我们就刻画出了一个点要么选理科，要么选文科。

对于第二类贡献：

我们新建一个节点 $x’$，以 $S$ 为起点 $x’$ 为终点，流量为 $same\text{\underline{ }}art_{i,j}$ 连边
以 $ x’$ 为起点, $x$ 和所有 $x$ 的相邻节点为终点分别连流量为 $inf$ 的边
我们新建一个节点 $x”$，以 $x”$ 为起点 $T$ 为终点，流量为 $same\text{\underline{ }}science_{i,j}$ 连边
以 $x$ 和所有 $x$ 的相邻节点 为起点, $x”$为终点分别连流量为 $inf$ 的边

这样我们保证了对于所有 $x’$，要么放弃 $same\text{\underline{ }}art_{i,j}$ ，要么就将他连的五条边全部断掉(即那五个点都不选理)。

$x”$也是类似的，不过多赘述。

Code:

#include<bits/stdc++.h>
const int N=1e5+5;
const int inf=1e9;
using namespace std;
struct Edge{
    int to,fl,nxt;
}e[N<<2];
int head[N],cnt=1;
void add(int x,int y,int fl)
{
    e[++cnt]={y,fl,head[x]};head[x]=cnt;
    e[++cnt]={x,0,head[y]};head[y]=cnt;
}
int n,m,S,T,tot;
long long ans;
inline int id(int i,int j){return (i-1)*m+j;}
int dx[5]={0,1,0,-1,0},dy[5]={1,0,-1,0,0};
int dis[N];
queue<int> Q;
void init()
{
    for(int u=S;u<=T;u++)dis[u]=0;
}
bool spfa(int s,int t)
{
    init();dis[s]=1;Q.push(s);
    while(!Q.empty())
    {
        int u=Q.front();Q.pop();
        for(int i=head[u],v,fl;i;i=e[i].nxt)
        {
            v=e[i].to,fl=e[i].fl;
            if(!dis[v]&&fl){dis[v]=dis[u]+1;Q.push(v);}
        }
    }
    return dis[t];
}
int dfs(int u,int flow)
{
    if(!flow||u==T)return flow;
    int res=0;
    for(int i=head[u],v,fl;i&&flow;i=e[i].nxt)
    {
        v=e[i].to,fl=e[i].fl;
        if(fl&&dis[v]==dis[u]+1)
        {
            int ff=dfs(v,min(fl,flow));
            e[i].fl-=ff;e[i^1].fl+=ff;
            res+=ff,flow-=ff;
        }
    }
    return res;
}
void dinic()
{
    while(spfa(S,T))
    {
        ans-=dfs(S,inf);
    }
}
void work()
{
    cin>>n>>m;S=0,T=3*n*m+1;tot=n*m;
    for(int i=1,x;i<=n;i++)for(int j=1;j<=m;j++)
    {
        scanf("%d",&x);ans+=x;
        add(S,id(i,j),x);
    }
    for(int i=1,x;i<=n;i++)for(int j=1;j<=m;j++)
    {
        scanf("%d",&x);ans+=x;
        add(id(i,j),T,x);
    }
    for(int i=1,x;i<=n;i++)for(int j=1;j<=m;j++)
    {
        scanf("%d",&x);ans+=x;
        add(S,++tot,x);
        for(int ii=0;ii<=4;ii++)if(1<=i+dx[ii]&&i+dx[ii]<=n&&1<=j+dy[ii]&&j+dy[ii]<=m)
        add(tot,id(i+dx[ii],j+dy[ii]),inf);
    }
    for(int i=1,x;i<=n;i++)for(int j=1;j<=m;j++)
    {
        scanf("%d",&x);ans+=x;
        add(++tot,T,x);
        for(int ii=0;ii<=4;ii++)if(1<=i+dx[ii]&&i+dx[ii]<=n&&1<=j+dy[ii]&&j+dy[ii]<=m)
        add(id(i+dx[ii],j+dy[ii]),tot,inf);
    }
    dinic();
    cout<<ans;
}
int main()
{
    //freopen("P4313.in","r",stdin);freopen("P4313.out","w",stdout);
    work();
    return 0;
}

来源链接：https://www.cnblogs.com/LG017/p/18724009

评分

欢迎为Ta评分