BZOJ3894:文理分科

引:

今天听学长讲了这道题目,然后现在写个博客…

题面:

传送门

文理分科是一件很纠结的事情!(虽然看到这个题目的人肯定都没有纠
结过)
小P所在的班级要进行文理分科。他的班级可以用一个n*m的矩阵进行
描述,每个格子代表一个同学的座位。每位同学必须从文科和理科中选择
一科。同学们在选择科目的时候会获得一个满意值。满意值按如下的方式
得到:
1. 如果第i行第秒J的同学选择了文科,则他将获得art[i][j]的满意值,如
果选择理科,将得到science[i][j]的满意值。
2. 如果第i行第J列的同学选择了文科,并且他相邻(两个格子相邻当且
仅当它们拥有一条相同的边)的同学全部选择了文科,则他会更开
心,所以会增加same_art[i][j]的满意值。
3. 如果第i行第j列的同学选择了理科,并且他相邻的同学全部选择了理
科,则增加same_science[i][j]的满意值。

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

分析:

看到这个题大概就知道这是最小割解决的问题…
当我们碰到有代价的选择某些点,同时它只有两种状态时,就可以用最小割,建立一个S(源点),T(汇点).
对于这道题目,我们假设和S相连的人都是选文的,和T相连的都是选理的,因为所有人要么选文要么选理,网络流可以解决一定条件下最小代价的分离…
对于题目的情况1,我们从源点向所有人连一条边,流量是art[i][j],同时建反向边,流量是0.
对于情况2,我们从所有人向汇点连一条边,流量是science[i][j],同时建反向边,流量是0.
对于情况3,我们先解决十字都是文的情况,我们另外开一个虚点,然后从源点向其连流量是same_art[i][j]的边,然后从这个虚点向十字里的所有点连边,流量是inf。
对于情况4,建边的方法与三相同。。
最后在建好的图上跑一边最小割就好了,答案就是输入的所有边的代价减去最小割…

证明:

上面说了,我们建好图以后,所有人只会和S,T连…然后,表明所有人都只选一门课.我们通过最小的代价,断掉的那些边都表明这段代价我们不要了..
然后因为是最小割,我们舍去的代价最小,那么最后剩余的代价就最大…

代码:

#pragma GCC diagnostic error "-std=c++11"
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const LL N=1e6+10;
const LL mod=1e9+7;
const LL inf=0x3f3f3f;
template<typename tp> inline void read(tp &x)
{
    x=0; char c=getchar(); bool f=0;
    for(;c<'0'||c>'9';f|=(c=='-'),c = getchar());
    for(;c>='0'&&c<='9';x=(x<<3)+(x<<1)+c-'0',c = getchar());
    if(f) x=-x;
}
int n,m,s,t,_new,sum;
struct Edge{int next,to,flow;}edge[N*2];
int head[N],cnt=1,dep[N],cur[N];
queue<int> q;
void add(int from,int to,int flow){edge[++cnt]={head[from],to,flow};head[from]=cnt;}
void insert(int from,int to,int flow){add(from,to,flow),add(to,from,0);}
bool BFS()
{
    memset(dep,-1,sizeof(dep));
    q.push(s);dep[s]=0;
    while(!q.empty())
    {
        int now=q.front();q.pop();
        for(int i=head[now];i;i=edge[i].next)
        {
            int to=edge[i].to;
            if(!edge[i].flow) continue;
            if(dep[to]==-1) dep[to]=dep[now]+1,q.push(to);
        }
    }
    return dep[t]!=-1;
}
int DFS(int now,int flow)
{
    if(now==t||!flow) return flow;
    int used=0;
    for(int &i=cur[now];i;i=edge[i].next)
    {
        int to=edge[i].to;
        if(dep[to]==dep[now]+1&&edge[i].flow)
        {
            int flag=DFS(to,min(flow-used,edge[i].flow));
            if(flag>0)
            {
                edge[i].flow-=flag;
                edge[i^1].flow+=flag;
                used+=flag;
            }
        }
    }
    return used;
}
int dinic(int ret=0) 
{ 
    while(BFS()) 
    {
        memcpy(cur,head,sizeof(int)*(n*m*4+2));
        ret+=DFS(s,inf); 
    }
    return ret;
}
int main()
{
    read(n),read(m);
    s=0,t=n*m*4+1;_new=n*m;
    for(int i=0,w;i<n;i++)
        for(int j=1;j<=m;j++)
            read(w),insert(s,i*m+j,w),sum+=w;
    for(int i=0,w;i<n;i++)
        for(int j=1;j<=m;j++)
            read(w),insert(i*m+j,t,w),sum+=w;
    for(int i=0,w;i<n;i++)
        for(int j=1;j<=m;j++)
        {
            read(w);++_new;
            insert(_new,i*m+j,inf);
            if(i>0) insert(_new,(i-1)*m+j,inf);
            if(i+1<n) insert(_new,(i+1)*m+j,inf);
            if(j>1) insert(_new,i*m+j-1,inf);
            if(j<m) insert(_new,i*m+j+1,inf);
            insert(s,_new,w);sum+=w;
        }
    for(int i=0,w;i<n;i++)
        for(int j=1;j<=m;j++)
        {
            read(w);++_new;
            insert(i*m+j,_new,inf);
            if(i>0) insert((i-1)*m+j,_new,inf);
            if(i+1<n) insert((i+1)*m+j,_new,inf);
            if(j>1) insert(i*m+j-1,_new,inf);
            if(j<m) insert(i*m+j+1,_new,inf);
            insert(_new,t,w);sum+=w;
        }
    printf("%d\n",sum-dinic());
    return 0;
}

关于“BZOJ3894:文理分科”我的1个想法

发表评论

电子邮件地址不会被公开。 必填项已用*标注