深圳网站优化推广方案,网页设计师岗位,室内装饰设计师证书含金量,综合电商平台正题
题目链接:https://www.luogu.com.cn/problem/P4313 题目大意
有n∗mn*mn∗m个人#xff0c;第(i,j)(i,j)(i,j)选择文科就可以获得arti,jart_{i,j}arti,j的价值#xff0c;选择理科就可以获得scii,jsci_{i,j}scii,j的价值。如果一个选择文科的人周围都选择了文科第(i,j)(i,j)(i,j)选择文科就可以获得arti,jart_{i,j}arti,j的价值选择理科就可以获得scii,jsci_{i,j}scii,j的价值。如果一个选择文科的人周围都选择了文科那么就可以多获得same_arti,jsame\_art_{i,j}same_arti,j的价值。如果一个选择了理科的人周围都选择了理科那么就可以多获得same_scii,jsame\_sci_{i,j}same_scii,j的价值。
求最大价值和。 解题思路
显然不考虑samesamesame的话如何将其模型转移到网络流上考虑最小割。我们对于每个同学(i,j)(i,j)(i,j)建立一个节点pi,j,0p_{i,j,0}pi,j,0然后S−pi,j,0S-p_{i,j,0}S−pi,j,0流量为arti,jart_{i,j}arti,jpi,j,0−Tp_{i,j,0}-Tpi,j,0−T流量为scii,jsci_{i,j}scii,j。
考虑如何加入samesamesame入这个模型中先考虑文科的对于一个点我们发现如果它周围的都割掉了理科的边就不需要割same_artsame\_artsame_art也就是我们需要新建一个节点连接这些周围的节点这样这些被连接的节点就必须要割掉连向TTT的边 。显然我们还需要建立S−pi,j,1S-p_{i,j,1}S−pi,j,1流量为same_arti,jsame\_art_{i,j}same_arti,j
same_scii,jsame\_ sci_{i,j}same_scii,j同理。 codecodecode
#includecstdio
#includecstring
#includealgorithm
#includequeue
#define p(x,y,z) ((((x)-1)*m(y))(z)*S)
using namespace std;
const int N3e410,inf2147483647/3;
struct node{int to,next,w;
}a[N*20];
const int dx[5]{1,-1,0,0,0},dy[5]{0,0,1,-1,0};
int n,m,s,t,S,tot1;
int dep[N],ls[N],ans;
queueint q;
void adde(int x,int y,int w){a[tot].toy;a[tot].nextls[x];ls[x]tot;a[tot].ww;a[tot].tox;a[tot].nextls[y];ls[y]tot;a[tot].w0;return;
}
bool bfs(){while(!q.empty())q.pop();memset(dep,0,sizeof(dep));dep[s]1;q.push(s);while(!q.empty()){int xq.front();q.pop();for(int ils[x];i;ia[i].next){int ya[i].to;if(!a[i].w||dep[y])continue;dep[y]dep[x]1;if(yt)return 1;q.push(y);}}return 0;
}
int dinic(int x,int flow){int rest0,k;if(xt)return flow;for(int ils[x];i;ia[i].next){int ya[i].to;if(!a[i].w||dep[y]!dep[x]1)continue;rest(kdinic(y,min(flow-rest,a[i].w)));a[i].w-k;a[i^1].wk;if(restflow)return flow;}if(!rest)dep[x]0;return rest;
}
int main()
{scanf(%d%d,n,m);Sn*m;sp(n,m,2)1;ts1;for(int i1;in;i)for(int j1;jm;j){int x;scanf(%d,x);adde(s,p(i,j,0),x);ansx;}for(int i1;in;i)for(int j1;jm;j){int x;scanf(%d,x);adde(p(i,j,0),t,x);ansx;}for(int i1;in;i)for(int j1;jm;j){int x;scanf(%d,x);adde(s,p(i,j,1),x);ansx;for(int k0;k5;k){int zxidx[k],zyjdy[k];if(zx1||zy1||zxn||zym)continue;adde(p(i,j,1),p(zx,zy,0),inf);}}for(int i1;in;i)for(int j1;jm;j){int x;scanf(%d,x);adde(p(i,j,2),t,x);ansx;for(int k0;k5;k){int zxidx[k],zyjdy[k];if(zx1||zy1||zxn||zym)continue;adde(p(zx,zy,0),p(i,j,2),inf);}}while(bfs())ans-dinic(s,inf);printf(%d,ans);
}
