自动搬运

查看原文

来自洛谷，原作者为

	Rainy7 恍惚间，宝石与花朵都死去了。

搬运于2025-08-24 21:57:43，当前版本为作者最后更新于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;
  }