题面 https://www.luogu.org/problemnew/show/P4313
解析
首先, 分析题目,
因为每个人要么选文科, 要么选理科.
所以这道题可以用最小割来解决.
先设文科为 S, 理科为 T(反过来也没区别),
再将每个人与文科, 理科都连起来,
流量就为满意值,
那么, 肯定得割掉一条边,
然后, 就要处理相同科目满意值了,
其实, 只要把相邻的四个人和中间的一个人连到一个点上,
再把那个点连到理科就行了 (文科也一样但要另外建一个点).
最后求最小割就可以了!
上 AC 代码:
- #include<bits/stdc++.h>
- using namespace std;
- inline int read(){
- int sum=0,f=1;char ch=getchar();
- while(ch>'9' || ch<'0'){if(ch=='-')f=-1;ch=getchar();}
- while(ch>='0' && ch<='9'){sum=sum*10+ch-'0';ch=getchar();}
- return f*sum;
- }
- const int INF=0x3f3f3f3f;
- struct hh{
- int to,next,v;
- }e[1000001];
- int n,m,si,ti,sum;
- int a[101][101],s[101][101],sa[101][101],ss[101][101];
- int id[101][101];
- int head[100001],cnt=1;
- int d[100001];
- int dx[4]={0,0,1,-1};
- int dy[4]={-1,1,0,0};
- void ppre(){
- int kk=0;
- for(int i=1;i<=n;i++)
- for(int j=1;j<=m;j++) id[i][j]=++kk;
- }
- void add(int x,int y,int v){
- e[++cnt].to=head[x];
- e[cnt].next=y;
- e[cnt].v=v;
- head[x]=cnt;
- }
- bool bfs(){
- memset(d,0,sizeof(d));
- queue <int> que;
- que.push(si);
- d[si]=1;
- while(!que.empty()){
- int x=que.front();
- que.pop();
- for(int i=head[x];i;i=e[i].to){
- int k=e[i].next;
- if(!e[i].v||d[k]) continue;
- d[k]=d[x]+1;
- que.push(k);
- }
- }
- return d[ti];
- }
- int dfs(int x,int mi){
- if(x==ti||!mi) return mi;
- int flow=0;
- for(int i=head[x];i;i=e[i].to){
- int k=e[i].next;
- if(!e[i].v||d[k]!=d[x]+1) continue;
- int ret=dfs(k,min(mi,e[i].v));
- e[i].v-=ret;e[i^1].v+=ret;
- flow+=ret;mi-=ret;
- if(!mi) break;
- }
- if(mi) d[x]=-1;
- return flow;
- }
- void DINIC(){
- int ans=sum;
- while(bfs()){
- int ret=dfs(si,INF);
- sum-=ret;
- }
- printf("%d\n",sum);
- }
- int main(){
- // freopen("divide.in","r",stdin);
- // freopen("divide.out","w",stdout);
- n=read();m=read();
- ppre();
- si=n*m*3+10;ti=n*m*3+20;
- 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++)
- s[i][j]=read(),sum+=s[i][j];
- for(int i=1;i<=n;i++)
- for(int j=1;j<=m;j++)
- sa[i][j]=read(),sum+=sa[i][j];
- for(int i=1;i<=n;i++)
- for(int j=1;j<=m;j++)
- ss[i][j]=read(),sum+=ss[i][j];
- for(int i=1;i<=n;i++){
- for(int j=1;j<=m;j++){
- add(si,id[i][j],s[i][j]);
- add(id[i][j],si,0);
- add(id[i][j],ti,a[i][j]);
- add(ti,id[i][j],0);
- }
- }
- for(int i=1;i<=n;i++){
- for(int j=1;j<=m;j++){
- int l=id[i][j]+n*m;
- add(l,ti,sa[i][j]);add(ti,l,0);
- add(id[i][j],l,INF);add(l,id[i][j],0);
- for(int k=0;k<4;k++){
- int x=i+dx[k],y=j+dy[k];
- if(x<=0||y<=0||x>n||y>m) continue;
- add(id[x][y],l,INF);add(l,id[x][y],0);
- }
- }
- }
- for(int i=1;i<=n;i++){
- for(int j=1;j<=m;j++){
- int l=id[i][j]+n*m*2;
- add(si,l,ss[i][j]);add(l,si,0);
- add(l,id[i][j],INF);add(id[i][j],l,0);
- // add(id[i][j],l,INF);add(l,id[i][j],0);
- for(int k=0;k<4;k++){
- int x=i+dx[k],y=j+dy[k];
- if(x<=0||y<=0||x>n||y>m) continue;
- add(l,id[x][y],INF);add(id[x][y],l,0);
- }
- }
- }
- DINIC();
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2986746.html