题解 P4210 【土地划分】

Rainy7 · 2020-05-14 23:16:34 · 题解

• 分析

  考虑最小割。

  可以用总和减去最小扣除分数来算答案。

  对于每个城市，可以分给A或者B。所以不妨设置一个源点 s ，汇点 t 。源点代表A，汇点代表B。

  即连边 (s,i,va_i) 和 (i,t,vb_i) 。再考虑城市与城市之间的连边。

  但是城市之间的连边会被两个城市所属A或B的影响。

  所以可以将一些边权除以 2 ，具体连边如下：

  对于2个城市先建立双向边：(u,v,\frac{ea}{2}+\frac{eb}{2}+ec) 。

  然后再连边：(s,u,\frac{ea}{2})(s,v,\frac{ea}{2})(u,t,\frac{eb}{2})(v,t,\frac{eb}{2}) 。

  这样就可以巧妙的解决这个所属A，B的情况了。

  因为数据可能有奇数，所以开始先全部乘二。

• 代码

  #include<iostream>
  #include<cstdio>
  #include<cmath>
  #include<queue>
  #include<cstring>
  using namespace std;
  const int Maxn=100005,Maxm=800005;
  const int inf=1e9;
  struct edge{
    int v,w,nx;
  }e[Maxm];
  int n,m,ne=-1,f[Maxn],deep[Maxn];
  int cur[Maxn];
  queue<int>q;
  void read(int u,int v,int w)
  { e[++ne].v=v;
    e[ne].w=w;
    e[ne].nx=f[u];
    f[u]=ne;
  }
  bool bfs(int s,int t)
  { memset(deep,0x7f,sizeof(deep));
    while(!q.empty())q.pop();
    for(int i=0;i<=n;i++)cur[i]=f[i];
    deep[s]=0;
    q.push(s);
    while(!q.empty())
    { int now=q.front();
        q.pop();
        for(int k=f[now];k!=-1;k=e[k].nx)
            if(deep[e[k].v]>inf&&e[k].w)
            { deep[e[k].v]=deep[now]+1;
                q.push(e[k].v);
            }
    }
    if(deep[t]<inf)return 1;
    return 0;
  }
  int dfs(int now,int t,int limit)
  { if(!limit||now==t)return limit;
    int flow=0,x;
    for(int i=cur[now];i!=-1;i=e[i].nx)
    { cur[now]=i;
        if(deep[e[i].v]==deep[now]+1)
        { x=dfs(e[i].v,t,min(limit,e[i].w));
            if(!x)continue;
            flow+=x;
            limit-=x;
            e[i].w-=x;
            e[i^1].w+=x;
            if(!limit)break;
        }
    }
    return flow;
  }
  int dinic(int s,int t)
  { int maxflow=0;
    while(bfs(s,t))maxflow+=dfs(s,t,inf);
    return maxflow;
  }
  int main()
  { int s,t,sum=0;
    scanf("%d%d",&n,&m);
    for(int i=0;i<=n+1;i++)f[i]=-1;
    s=0;t=n+1;
    read(s,1,inf);
    read(n,t,inf);
    for(int i=2;i<=n-1;i++)
    { int x;
        scanf("%d",&x);
        x*=2;
        sum+=x;
        read(s,i,x);read(i,s,0);
    }
    for(int i=2;i<=n-1;i++)
    { int x;
        scanf("%d",&x);
        x*=2;
        sum+=x;
        read(i,t,x);read(t,i,0);
    }
    for(int i=1;i<=m;i++)
    { int u,v,x1,x2,x3;
        scanf("%d%d%d%d%d",&u,&v,&x1,&x2,&x3);
        x1*=2;x2*=2;x3*=2;
        sum+=x1+x2;
        read(u,v,(x1/2+x2/2+x3));
        read(v,u,(x1/2+x2/2+x3));
        read(s,u,x1/2);read(u,s,0);
        read(s,v,x1/2);read(v,s,0);
        read(u,t,x2/2);read(t,u,0);
        read(v,t,x2/2);read(t,v,0);
    }
    n++;
    printf("%d\n",(sum-dinic(s,t))/2);
    return 0;
  }