首页 > 代码库 > Bzoj3894文理分科

Bzoj3894文理分科

2024-08-29 17:20:23   219人阅读

注意到所有学生分为文理两科实际是把所有学生分为两个集合，如果相邻点全为同一集合有额外贡献

与最小割模型类似，考虑用最小割来解这道题

所有割到s的集合的点如果相邻点有割到t集合的就要去掉共有贡献，但是不论他周围有多少与他不同的人，这个贡献只会被扣一次，所以考虑拆点

可以观察到如果一个点没有选择文科，那么也必然不会有文科共同贡献，理科亦然，所以考虑把选每科贡献与每科共同贡献统一起来

然后就可以构图了

设a[x]为x选文科满意度，s[x]为选理科满意度

Sa[x],Ss[x]分别为选两科的共同贡献

把每个点拆成三个点ux,x,dx，源向x连容量为a[x]+Sa[x]的边，x向汇连容量为s[x]+Ss[x]的边

x向ux连容量为Sa[x]的边，dx向x连容量为Ss[x]的边

ux向所有与x相邻的点连容量为INF的边，所有与x相邻的点向dx连容量为INF的边

跑最小割即可

代码:

#include<bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std;

inline int _min(int a,int b) {return a<b?a:b;}

#define MAXN 30005

const int S=MAXN-3,T=MAXN-2;
int n,m,fix,fix2,ans;
struct Edge{
    int from,to,next,v;
}e[MAXN*10];
int cnt=1,head[MAXN];
inline void insert(int a,int b,int f) {
    e[++cnt].next=head[a];head[a]=cnt;e[cnt].v=f;e[cnt].to=b;e[cnt].from=a;
    e[++cnt].next=head[b];head[b]=cnt;e[cnt].v=0;e[cnt].to=a;e[cnt].from=b;
}

int mk[105][105],sz,a[105][105],s[105][105],Sa[105][105],Ss[105][105];
int to[4][2]={1,0,0,1,-1,0,0,-1};

int dis[MAXN],bk[MAXN];queue<int> q;
bool Bfs() {
    memset(dis,0,sizeof(dis));
    dis[T]=1;q.push(T);
    while(!q.empty()) {
        int now=q.front();q.pop();
        for(int i=head[now];i;i=e[i].next) 
            if(!dis[e[i].to]&&e[i^1].v>0) {
                dis[e[i].to]=dis[now]+1;
                q.push(e[i].to);
            }
    }
    return dis[S];
}
int Dfs(int v,int a) {
    if(v==T) return a;
    int flow=0,k;
    for(int i=head[v];i;i=e[i].next) {
        if(e[i].v>0&&dis[e[i].to]==dis[v]-1) {
            k=Dfs(e[i].to,_min(a,e[i].v));
            a-=k;flow+=k;e[i].v-=k;e[i^1].v+=k;
            if(a==0) return flow;
        }
    }
    return flow;
}
int MaxFlow() {
    int flow=0,h;
    while(Bfs()) {
        while(h=Dfs(S,INF)) 
            flow+=h;
    }
    return flow;
}

int main() {
    scanf("%d%d",&n,&m);fix=n*m;fix2=n*m*2;
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) {
        mk[i][j]=++sz;
        scanf("%d",&a[i][j]);
    }
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&s[i][j]);
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&Sa[i][j]);
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) scanf("%d",&Ss[i][j]);
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) {
        ans+=a[i][j]+s[i][j]+Sa[i][j]+Ss[i][j];
        insert(S,mk[i][j],a[i][j]+Sa[i][j]);
        insert(mk[i][j],T,s[i][j]+Ss[i][j]);
    }
    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) {
        insert(mk[i][j],mk[i][j]+fix,Sa[i][j]);
        insert(mk[i][j]+fix2,mk[i][j],Ss[i][j]);
        for(int k=0;k<4;k++) {
            if(!mk[i+to[k][0]][j+to[k][1]]) continue;
            insert(mk[i][j]+fix,mk[i+to[k][0]][j+to[k][1]],INF);
            insert(mk[i+to[k][0]][j+to[k][1]],mk[i][j]+fix2,INF);
        }
    }
    printf("%d\n",ans-MaxFlow());
    return 0;
}

 

Bzoj3894文理分科


联系
我们