bzoj2127:happiness bzoj3894:文理分科(最小割)

Author Avatar
Sakits 3月 28, 2018

题解

  想了一会就知道是网络流了…一直建不出图,看了题解感觉很妙
  这题的正确思路应该运用最小割,用总贡献减去最小的代价
  首先说bzoj21272127…整个图割完应该有一些点与SS相连,一些点与TT相连,分别对应文理科。
  那么如果割掉与SS的边而与TT相连,那么会失去文科的贡献。设选文科的喜悦度为xx,与相邻位置同选文科的喜悦度为yy,那么SS与点应连权值为x+y2x+\frac{y}{2}的边,这样连边的话如果相邻位置同选了理科,那么损失的就是两个人选文科的喜悦度和同选文科的喜悦度。与TT的连边同理。
  还有一种情况是相邻位置选的科目不同,那么可以在相邻的两个点(u,v)(u,v)上连边来做文章,因为如果选的科目不同这条边必定会被割掉。如果相邻位置选科不同,那么会失去同时选文科的喜悦度aa和同时选理科的喜悦度bbuuvv互相连权值为a+b2\frac{a+b}{2}的边即可。

bzoj21272127代码

#include<iostream> 
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath> 
#include<algorithm> 
using namespace std;
const int maxn=500010, inf=1e9;
struct poi{int too, cf, pre;}e[maxn<<1];
int n, m, s, t, x, y, z, tot, ans, sum;
int v[maxn], dist[maxn], last[maxn], cur[maxn], h[maxn];
int a[10][110][110];
inline void read(int &k)
{
    int f=1; k=0; char c=getchar();
    while(c<'0' || c>'9') c=='-'&&(f=-1), c=getchar();
    while(c<='9' && c>='0') k=k*10+c-'0', c=getchar();
    k*=f;
}
inline void add(int x, int y, int z){e[++tot]=(poi){y, z, last[x]}; last[x]=tot;}
inline bool bfs(int s, int t)
{
    for(int i=1;i<=n;i++) v[i]=0, dist[i]=-1;
    dist[s]=0; int front=0, rear=1; h[1]=s; v[s]=1;
    while(front!=rear)
    {
        int now=h[++front];
        if(front==maxn-1) front=-1;
        for(int i=last[now], too;i;i=e[i].pre)
        if(!v[too=e[i].too] && e[i].cf)
        {
            dist[too]=dist[now]+1;
            v[too]=1; h[++rear]=too;
            if(rear==maxn-1) rear=-1;
            if(too==t) return 1;
        }
    } 
    return 0;
}
int dfs(int x, int flow)
{
    if(x==t || !flow) return flow; 
    int f=0, tmp;
    for(int &i=cur[x], too;i;i=e[i].pre)
    if(dist[too=e[i].too]==dist[x]+1 && e[i].cf)
    {
        tmp=dfs(too, min(flow-f, e[i].cf));
        e[i].cf-=tmp; e[i^1].cf+=tmp; f+=tmp;
        if(f==flow) break;
    } 
    return f;
}
inline void dinic(int s, int t)
{
    while(bfs(s, t))
    {
        memcpy(cur, last, sizeof(last));
        ans+=dfs(s, inf);
    }   
} 
inline int num(int x, int y){return (x-1)*m+y;}
int main()
{
    read(n); read(m); tot=1;
    for(int i=1;i<=6;i++)
    {
        int N=n, M=m;
        if(i>=5) M--; else if(i>=3) N--; 
        for(int j=1;j<=N;j++)
        {
            for(int k=1;k<=M;k++)
            read(a[i][j][k]), sum+=a[i][j][k];
        }
    }
    s=0; t=n*m+1;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    {
        add(s, num(i, j), (a[1][i][j]<<1)+a[3][i][j]+a[3][i-1][j]+a[5][i][j]+a[5][i][j-1]);
        add(num(i, j), s, 0);
        add(num(i, j), t, (a[2][i][j]<<1)+a[4][i][j]+a[4][i-1][j]+a[6][i][j]+a[6][i][j-1]);
        add(t, num(i, j), 0);
        if(i!=n)
        {
            add(num(i, j), num(i+1, j), a[3][i][j]+a[4][i][j]);
            add(num(i+1, j), num(i, j), a[3][i][j]+a[4][i][j]);
        }
        if(j!=m)
        {
            add(num(i, j), num(i, j+1), a[5][i][j]+a[6][i][j]);
            add(num(i, j+1), num(i, j), a[5][i][j]+a[6][i][j]);
        }
    }
    n=n*m+1; dinic(s, t); printf("%d\n", sum-(ans>>1));
}

  bzoj38943894与上一题有些许不同,这题要求的是所有相邻的点选同样科目才会有额外的喜悦度,换句话说只要有一个相邻位置选科不同就会失去这个贡献,实际上只需要新建一个中转点往相邻节点连边即可…

bzoj38943894代码

#include<iostream> 
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath> 
#include<algorithm> 
using namespace std;
const int maxn=500010, inf=1e9;
struct poi{int too, cf, pre;}e[maxn<<1];
const int dx[4]={1, 0, -1, 0}, dy[4]={0, 1, 0, -1};
int n, m, s, t, x, y, z, tot, ans, sum, tott;
int v[maxn], dist[maxn], last[maxn], cur[maxn], h[maxn];
int a[10][110][110];
inline void read(int &k)
{
    int f=1; k=0; char c=getchar();
    while(c<'0' || c>'9') c=='-'&&(f=-1), c=getchar();
    while(c<='9' && c>='0') k=k*10+c-'0', c=getchar();
    k*=f;
}
inline void add(int x, int y, int z){e[++tot]=(poi){y, z, last[x]}; last[x]=tot;}
inline bool bfs(int s, int t)
{
    for(int i=1;i<=n;i++) v[i]=0, dist[i]=-1;
    dist[s]=0; int front=0, rear=1; h[1]=s; v[s]=1;
    while(front!=rear)
    {
        int now=h[++front];
        if(front==maxn-1) front=-1;
        for(int i=last[now], too;i;i=e[i].pre)
        if(!v[too=e[i].too] && e[i].cf)
        {
            dist[too]=dist[now]+1;
            v[too]=1; h[++rear]=too;
            if(rear==maxn-1) rear=-1;
            if(too==t) return 1;
        }
    } 
    return 0;
}
int dfs(int x, int flow)
{
    if(x==t || !flow) return flow; 
    int f=0, tmp;
    for(int &i=cur[x], too;i;i=e[i].pre)
    if(dist[too=e[i].too]==dist[x]+1 && e[i].cf)
    {
        tmp=dfs(too, min(flow-f, e[i].cf));
        e[i].cf-=tmp; e[i^1].cf+=tmp; f+=tmp;
        if(f==flow) break;
    } 
    return f;
}
inline void dinic(int s, int t)
{
    while(bfs(s, t))
    {
        memcpy(cur, last, sizeof(last));
        ans+=dfs(s, inf);
    }   
} 
inline int num(int x, int y){return (x-1)*m+y;}
int main()
{
    read(n); read(m); tot=1;
    for(int i=1;i<=4;i++)
    {
        for(int j=1;j<=n;j++)
        {
            for(int k=1;k<=m;k++)
            read(a[i][j][k]), sum+=a[i][j][k];
        }
    }
    s=0; t=n*m+1; tott=t;
    for(int i=1;i<=n;i++)
    for(int j=1;j<=m;j++)
    {
        add(s, num(i, j), a[1][i][j]+a[3][i][j]);
        add(num(i, j), s, 0);
        add(num(i, j), t, a[2][i][j]+a[4][i][j]);
        add(t, num(i, j), 0);
        add(++tott, num(i, j), a[4][i][j]);
        add(num(i, j), tott, 0);
        for(int k=0;k<4;k++)
        {
            int x=i+dx[k], y=j+dy[k];
            if(x<1 || x>n || y<1 || y>m) continue;
            add(num(x, y), tott, a[4][i][j]);
            add(tott, num(x, y), 0);
        }
        add(num(i, j), ++tott, a[3][i][j]);
        add(tott, num(i, j), 0);
        for(int k=0;k<4;k++)
        {
            int x=i+dx[k], y=j+dy[k];
            if(x<1 || x>n || y<1 || y>m) continue;
            add(tott, num(x, y), a[3][i][j]);
            add(num(x, y), tott, 0);
        }
    }
    n=tott; dinic(s, t); printf("%d\n", sum-ans);
}