bzoj 3894 文理分科【最小割+dinic】

谁说这道和2127是双倍经验的来着完全不一样啊？

数组开小会TLE！数组开小会TLE！数组开小会TLE！

首先sum统计所有收益

对于当前点\( (i,j) \)考虑，设\( x=(i-1)*m+j \) 首先单个人选择文科或者理科是很好建图的，我们设与s点相连选文，与t点相连选理，连接\( [s,x]=art[i][j] \) \( [x,t]=science[i][j] \)，即不选哪一科就割掉哪一科的收益即可

然后考虑前后左右中5个人同时选同一科的情况。把x拆成x,x0,x1,连接\( [s,x0]=same_{art}[i][j] \)，x0与5个相邻点，\( [x1,t]=same_{science}[i][j] \)，5个相邻点与t。也就是五个人只要有一个选了和其他人不同的科目，经应该把同时选该科目的收益割掉。

\( ans=sum-最小割 \)

#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

using namespace std;

const int N=1005,E=1000005,inf=1e9,P=5000005,dx[6]={0,0,0,1,-1},dy[6]={0,1,-1,0,0};

int n,m,a[N][N],b[N][N],c[N][N],d[N][N],s,t,sum,cnt=1,h[P],le[N*N];

struct qwe

{

	int ne,to,va;

}e[E];

int read()

{

	int r=0,f=1;

	char p=getchar();

	while(p<'0'||p>'9')

	{

		if(p=='-')

			f=-1;

		p=getchar();

	}

	while(p>='0'&&p<='9')

	{

		r=r*10+p-48;

		p=getchar();

	}

	return r*f;

}

void add(int u,int v,int w)

{

	cnt++;

	e[cnt].ne=h[u];

	e[cnt].to=v;

	e[cnt].va=w;

	h[u]=cnt;

}

void ins(int u,int v,int w)

{

	add(u,v,w);

	add(v,u,0);

}

bool bfs()

{

	queue<int>q;

    memset(le,0,sizeof(le));

	le[s]=1;

	q.push(s);

    while(!q.empty())

    {

        int u=q.front();

		q.pop();

        for(int i=h[u];i;i=e[i].ne)

            if(e[i].va>0&&!le[e[i].to])

            {

                le[e[i].to]=le[u]+1;

                q.push(e[i].to);

            }

    }

    return le[t];

 }

int dfs(int u,int f)

{//cout<<u<<" "<<f<<endl;

    if(u==t||f==0)

		return f;

    int used=0;

    for(int i=h[u];i;i=e[i].ne)

        if(e[i].va>0&&le[e[i].to]==le[u]+1)

        {//cout<<"OK"<<endl;

            int w=dfs(e[i].to,min(f-used,e[i].va));

            e[i].va-=w;

            e[i^1].va+=w;

            used+=w;

            if(used==f)

				return f;

        }

    if(!used)

		le[u]=-1;

    return used;

}

int dinic()

{

	int ans=0;

	while(bfs())

		ans+=dfs(s,inf);//,cout<<ans<<endl;

	return ans;

}

int id(int x,int y)

{

	return (x-1)*m+y;

}

int main()

{

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

	s=0,t=3*n*m+1;

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

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

			a[i][j]=read(),sum+=a[i][j];

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

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

			b[i][j]=read(),sum+=b[i][j];

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

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

			c[i][j]=read(),sum+=c[i][j];

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

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

			d[i][j]=read(),sum+=d[i][j];

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

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

		{

			int x=(i-1)*m+j,x0=x+n*m,x1=x+2*n*m;

			ins(s,x,a[i][j]);

			ins(x,t,b[i][j]);

			ins(s,x0,c[i][j]);

			ins(x1,t,d[i][j]);

			for(int k=0;k<=4;k++)

				if(i+dx[k]>=1&&i+dx[k]<=n&&j+dy[k]>=1&&j+dy[k]<=m)

				{

					int y=(i+dx[k]-1)*m+j+dy[k];

					ins(x0,y,inf);

					ins(y,x1,inf);

				}

		}

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

	return 0;

}