题解 P4313 【文理分科】

· · 题解

P4313 【文理分科】

\color{green}{\text{更好的阅读体验}}

题意

每个人选文科或理科可以有满意值，几个人同时选文科或理科也可以获得满意值，求满意值的最大值。

??为什么文科是art

题解

看到这类二者选其一的模型，我们肯定能想到最小割。首先，我们先从矩阵中拿出小盆友A和TA的相邻同学B、C、D、E，怼到图上，在画上源点和汇点，分别代表文科和理科：

假设没有额外的快乐值，我们可以这么连边：

如果我们割去一条边，就代表着不选文科/理科，若图不连通，则代表每个点只与源点或汇点联通，即每个人只选文科或理科。然后我们再去考虑same值，显然，我们如果选了一条science的边，就要把same\ art删掉；同理，我们如果选了一条art的边，就要把same\ science删掉，因此，我们可以加上两个虚点，连上边：

建完了图剩下的代码就简单了

代码

#pragma optimize(2)
#include<bits/stdc++.h>
using namespace std;
namespace in{
    char buf[1<<21],*p1=buf,*p2=buf;
    inline int getc(){
        return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;
    }
    template <typename T>inline void read(T& t){
        t=0;int f=0;char ch=getc();
        while (!isdigit(ch)){
            if(ch=='-')f = 1;
            ch=getc();
        }
        while(isdigit(ch)){
            t=t*10+ch-48;
            ch = getc();
        }
        if(f)t=-t;
    }
    template <typename T,typename... Args> inline void read(T& t, Args&... args){
        read(t);read(args...);
    }
}
namespace out{
    char buffer[1<<21];
    int p1=-1;
    const int p2 = (1<<21)-1;
    inline void flush() {
        fwrite(buffer,1,p1+1,stdout),
        p1=-1;
    }
    inline void putc(const char &x) {
        if(p1==p2)flush();
        buffer[++p1]=x;
    }
    template <typename T>void write(T x) {
        static char buf[15];
        static int len=-1;
        if(x>=0){
            do{
                buf[++len]=x%10+48,x/=10;
            }while (x);
        }else{
            putc('-');
            do {
                buf[++len]=-(x%10)+48,x/=10;
            }while(x);
        }
        while (len>=0)
            putc(buf[len]),--len;
    }
}
const int maxn=4000010,maxe=100010*2;
struct Graph{
    struct node{
        int v,w,nxt;
    }e[maxe<<1];
    int head[maxn],cur[maxn],tot;
    int dis[maxn];
    int s,t;
    void init(int _s,int _t){s=_s,t=_t;tot=1;memset(head,0,sizeof head);}
    Graph(int _s=0,int _t=0){init(_s,_t);}
    void add(int u,int v,int w){
        //printf("%d %d %d\n",u,v,w);
        e[++tot]=(node){v,w,head[u]},head[u]=tot;
        e[++tot]=(node){u,0,head[v]},head[v]=tot;
    }
    #define v e[i].v
    inline bool bfs(){
        queue<int>q;
        memset(dis,0,sizeof dis);
        memcpy(cur,head,sizeof head);
        dis[s]=1;q.push(s);
        while(q.size()){
            int u=q.front();q.pop();
            for(int i=head[u];i;i=e[i].nxt)
                if(!dis[v]&&e[i].w){
                    dis[v]=dis[u]+1,q.push(v);
                    if(v==t)return true;
                }
        }
        return  false;
    }
    int dfs(int u,int flow){
        if(u==t)return flow;
        int rest=flow;
        for(int i=cur[u];i&&rest;i=e[i].nxt){
            if(dis[v]==dis[u]+1&&e[i].w){
                int tmp=dfs(v,min(rest,e[i].w));
                rest-=tmp,e[i].w-=tmp,e[i^1].w+=tmp;
            }
            cur[u]=i;
        }
        if(rest==0)dis[u]=-1;
        return flow-rest;
    }
    #undef v
    int dinic(){
        int ans=0;
        while(bfs())
            while(int sth=dfs(s,2e9))
                ans+=sth;
        return ans;
    }
}G;
int n,m,x;
int sum,tot;
bool check(int x,int y){
    return x<=n&&x>=1&&y<=m&&y>=1;
}
#define P(i,j) ((i)-1)*m+(j)
signed main(){
    //freopen("1.in","r",stdin);
    in::read(n,m);
    tot=n*m;G.init(0,++tot);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            in::read(x);sum+=x;
            G.add(G.s,P(i,j),x);
        }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            in::read(x);sum+=x;
            G.add(P(i,j),G.t,x);
        }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            in::read(x);sum+=x;
            G.add(G.s,++tot,x);
            G.add(tot,P(i,j),1e9);
            if(check(i,j-1))G.add(tot,P(i,j-1),1e9);
            if(check(i,j+1))G.add(tot,P(i,j+1),1e9);
            if(check(i-1,j))G.add(tot,P(i-1,j),1e9);
            if(check(i+1,j))G.add(tot,P(i+1,j),1e9);
        }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=m;j++){
            in::read(x);sum+=x;
            G.add(++tot,G.t,x);
            G.add(P(i,j),tot,1e9);
            if(check(i,j-1))G.add(P(i,j-1),tot,1e9);
            if(check(i,j+1))G.add(P(i,j+1),tot,1e9);
            if(check(i-1,j))G.add(P(i-1,j),tot,1e9);
            if(check(i+1,j))G.add(P(i+1,j),tot,1e9);
        }
    out::write(sum-G.dinic());
    out::flush();
}

举一反三

happiness

小M的作物