P4313 文理分科-白红宇的个人博客

P4313 文理分科

发布日期：2025-05-01 11:26:18 浏览次数：2 分类：技术文章

本文共 3091 字，大约阅读时间需要 10 分钟。

题意分析

由于要么学文科要么学理科

我们考虑用最小割解决问题

关键是怎么建图~~网络流的唯二难点~~

首先我们考虑没有集体加成的时候

由\(S\)向\((i,j)\)建边权为\(art_{i,j}\)的边

然后由\((i,j)\)向\(T\)建边权为\(science_{i,j}\)的边

这样的跑出最大流就行了

如果加上集体加成呢

关键是思考如何建使得都选上并且不会被删

那么就是对于文科

我们建立辅助节点\((i,j)'\)

然后\(S\)向\((i,j)'\)建边权为\(sameart_{i,j}\)的边

同时\((i,j)'\)向相邻的\((i,j)\)包括自己建边权为\(inf\)的边

这样就可以保证都选上不会被删

理科同理

CODE:

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 
                  #include
                  
                   #define ll long long#define inf 0x7fffffff#define N 108#define IL inline#define M 1008611#define D double#define ull unsigned long long#define R registerusing namespace std;template
                   
                    IL void read(T &_){ T __=0,___=1;char ____=getchar(); while(!isdigit(____)) {if(____=='-') ___=0;____=getchar();} while(isdigit(____)) {__=(__<<1)+(__<<3)+____-'0';____=getchar();} _=___ ? __:-__;}/*-------------OI使我快乐-------------*/int n,m,S,T,tot=1,sum,ans;int to[M],nex[M],head[M],w[M],cur[M];int dep[M],art[N][N],sci[N][N],sart[N][N],saci[N][N];int tx[6]={0,1,-1,0,0},ty[6]={0,0,0,1,-1};queue
                    
                      Q;IL int id(int x,int y){return (x-1)*m+y;}IL bool safe(int x,int y){return x>=1&&x<=n&&y>=1&&y<=m;}IL void add(int x,int y,int z){to[++tot]=y;nex[tot]=head[x];head[x]=tot;w[tot]=z;swap(x,y);to[++tot]=y;nex[tot]=head[x];head[x]=tot;w[tot]=0;}IL bool bfs(){ while(!Q.empty()) Q.pop(); for(R int i=1;i<=T;++i) dep[i]=0; Q.push(S);dep[S]=1; for(;!Q.empty();) { int u=Q.front();Q.pop(); for(R int i=head[u];i;i=nex[i]) { int v=to[i]; if(w[i]>0&&dep[v]==0) { dep[v]=dep[u]+1;Q.push(v); } } } return dep[T]!=0;}IL int dfs(int now,int res){ if(now==T||res==0) return res; for(R int &i=cur[now];i;i=nex[i]) { int v=to[i]; if(w[i]>0&&dep[v]==dep[now]+1) { int have=dfs(v,min(res,w[i])); if(have>0) { w[i]-=have;w[i^1]+=have; return have; } } } return 0;}IL void Dinic(){ while(bfs()) { for(R int i=1;i<=T;++i) cur[i]=head[i]; int d=dfs(S,inf); while(d) ans+=d,d=dfs(S,inf); }}int main(){// freopen(".in","r",stdin);// freopen(".out","w",stdout); read(n);read(m); for(R int i=1;i<=n;++i) for(R int j=1;j<=m;++j) read(art[i][j]),sum+=art[i][j]; for(R int i=1;i<=n;++i) for(R int j=1;j<=m;++j) read(sci[i][j]),sum+=sci[i][j]; for(R int i=1;i<=n;++i) for(R int j=1;j<=m;++j) read(sart[i][j]),sum+=sart[i][j]; for(R int i=1;i<=n;++i) for(R int j=1;j<=m;++j) read(saci[i][j]),sum+=saci[i][j]; S=3*n*m+1;T=3*n*m+2; for(R int i=1;i<=n;++i) for(R int j=1;j<=m;++j) add(S,id(i,j),art[i][j]); for(R int i=1;i<=n;++i) for(R int j=1;j<=m;++j) add(id(i,j),T,sci[i][j]); for(R int i=1;i<=n;++i) for(R int j=1;j<=m;++j) add(S,id(i,j)+n*m,sart[i][j]); for(R int i=1;i<=n;++i) for(R int j=1;j<=m;++j) add(id(i,j)+2*n*m,T,saci[i][j]); for(R int i=1;i<=n;++i) for(R int j=1;j<=m;++j) for(R int k=0;k<=4;++k) { int cdy=i+tx[k],wzy=j+ty[k]; if(safe(cdy,wzy)) { add(id(i,j)+n*m,id(cdy,wzy),inf); add(id(cdy,wzy),id(i,j)+2*n*m,inf); } } Dinic(); printf("%d\n",sum-ans);// fclose(stdin);// fclose(stdout); return 0;}

HEOI 2019 RP++

转载于:https://www.cnblogs.com/LovToLZX/p/10590594.html

上一篇：P4491 [HAOI2018] 染色

下一篇：P4 Tutorials Flowlet Switching

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

题意分析

CODE:

HEOI 2019 RP++

发表评论

最新留言

关于作者

推荐文章