[Bzoj3894]文理分科（最小割）

Description

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

小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想知道，大家应该如何选择，才能使所有人的满意值之和最大。请告诉他这个最大值。

Solution

这是一道最小割的题目，关键在建图

Code

#include <cstdio>

#include <algorithm>

#define N 1000010

#define Inf 0x7fffffff

using namespace std;

const int dx[]={0,0,0,1,-1};

const int dy[]={0,1,-1,0,0};

struct info{int to,nex,f;}e[N];

int n,m,T,S,tot,nodes,head[N],Ans,cnt[N],dis[N],sum;

inline void Link(int u,int v,int f){

    e[++tot].to=v;e[tot].nex=head[u];head[u]=tot;e[tot].f=f;

    e[++tot].to=u;e[tot].nex=head[v];head[v]=tot;e[tot].f=0;

}

inline int read(){

    int x=0,f=1;char ch=getchar();

    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

    return x*f;

}

inline void Init(){

    n=read(),m=read();

    S=0,tot=1,nodes=(T=n*m*3+1)+1;

    for(int i=1;i<=n*m;++i){int t=read();sum+=t;Link(S,i,t);}

	for(int i=1;i<=n*m;++i){int t=read();sum+=t;Link(i,T,t);}

	for(int i=1;i<=n;++i)

		for(int j=1;j<=m;++j){

			int t=read(),cur=(i-1)*m+j;

			sum+=t;

			Link(S,cur+m*n,t);

			for(int k=0;k<5;++k){

				int x=i+dx[k],y=j+dy[k];

				if(x<=0||y<=0||x>n||y>m) continue;

				Link(cur+m*n,(x-1)*m+y,Inf);

			}

		}

	for(int i=1;i<=n;++i)

		for(int j=1;j<=m;++j){

			int t=read(),cur=(i-1)*m+j;

			sum+=t;

			Link(cur+2*m*n,T,t);

			for(int k=0;k<5;++k){

				int x=i+dx[k],y=j+dy[k];

				if(x<=0||y<=0||x>n||y>m) continue;

				Link((x-1)*m+y,cur+2*m*n,Inf);

			}

		}

}

int sap(int u,int d){

    if(u==T) return d;

    int sum=0,mins=nodes;

    for(int i=head[u];i;i=e[i].nex){

        int v=e[i].to;

        if(e[i].f>0&&dis[u]==dis[v]+1){

            int save=sap(v,min(d-sum,e[i].f));

            sum+=save;

            e[i].f-=save;

            e[i^1].f+=save;

            if(dis[S]>=nodes||sum==d) return sum;

        }

        if(e[i].f>0) mins=min(mins,dis[v]);

    }

    if(!sum){

        if(!(--cnt[dis[u]])) dis[S]=nodes;

        else ++cnt[dis[u]=mins+1];

    }

    return sum;

}

void SAP(){cnt[0]=nodes;while(dis[S]<nodes) Ans+=sap(S,Inf);}

int main(){

    Init();

    SAP();

    printf("%d\n",sum-Ans);

    return 0;

}

巴特西

[Bzoj3894]文理分科（最小割）

Description

Solution

Code

最新文章

热门文章