「some」最大流最小割

时间：2024-02-16 22:49:32

记录一下自己被吊打的过程

一些全部代码的调试信息没删

主要是一些模型。

部分内容摘自最大流-OI-WiKi

网络流

网络

网络是指一个有向图 \(G=(V,E)\)，其中每条边\((u,v)\in E\)，都有一个权值 \(c(u,v)\) ，称为边的容量，若\((u,v)\notin E\)，则\(c(u,v)=0\) 。在整个网络中，有两个特殊的节点，分别为源点 \(S\in V\) 和汇点 \(T\in V\) 并且\(S\ne T\)。

流

设 \(f(u,v)\) 是定义在二元组 \((u\in V,v\in V)\) 上的实数函数，且满足：

  1. 容量限制，对于每条边，流经该边的的流量不大于该边的容量。即 \(f(u,v)\le c(u,v)\) 。
  2. 斜对称性，每条边的流量和其相反边的流量之和为0。即 \(f(u,v)=-f(v,u)\)
  3. 流守恒性，从源点流出的流量等于流入汇点的流量。即 \(\forall x\in V-\{S,T\},\sum_{(u,x)\in E}f(u,x)=\sum_{(u,v)\in E}f(x,v)\)。

也称为可行流。

流\(f\) 的值定义为 \(|f|=\sum_{v\in V}f(s,v)\)。

最大流

何为最大流？

最大的可行流

我们有一张图，要求从源点流向汇点的最大流量（可以有很多条路径到达汇点），就是所谓的最大流问题。

求解最大流，可以用EK，Dinic，ISAP等算法。

貌似ISAP一不小心就会被卡这跟我这个dinic选手有什么关系
其实是不会

在学习Dinic之前，先了解几个概念：

剩余容量

表示这条边的容量与流量之差，即 \(c_{f}(u,v)=c(u,v)-f(u,v)\) 。

残量网络

残量网络 \(G_{f}\) 是网络 \(G\) 中所有剩余容量大于0的边所构成的子图。

增广路

在原图G中，若一条源点到汇点的路径上的所有边的剩余容量都大于0，则这条路经被称为增广路，或者说，在残量网络中一条从源点到汇点的路径。

Dinic

粘贴

因为本人是dinic选手，所以只会说dinic，但EK板子还是会贴的

dinic流程：

从源点开始dfs，边权不为0就继续递归，直至到达汇点，在dfs过程中记录当前路径上的最小边权，因为流量会受到最小边权的限制。

然而当前找到的增广路不一定是最优的，所以对于每一条边都多建一条初始边权为0的反向边，回溯时把经过的边都减去最小值，相应的，把反向边都加上这个最小值。

然而每次只找一条增广路效率太低，那就每回找多条增广路。

具体来说，先从源点开始bfs给图分层，更新到达的点的深度，深度相同的点即在同一层，到达汇点就停止bfs。

在dfs过程中，每回只增广比当前深度大1的点，即只从当前层向下一层找，这样就可以做到多路增广。

简单概括一下：

来自lyd蓝书

dinic不断重复以下步骤，直到在残量网络中源点不能到达汇点：

  1. 在残量网络上bfs求出节点的层次，构造分层图。
  2. 在分层图上dfs求出增广路，在回溯时更新剩余容量。

为了效率，还可以使用当前弧优化和无用点优化。

当前弧优化：如果一条边已经被增广过一次，那么就不会再被增广第二次，所以在下一次增广的过程中，就没必要增广这些边。

无用点优化：如果一个点对答案没有贡献，那么就下次就不再访问。

复杂度 \(O(n^{2}m)\) ，然而根本跑不满。

模板

EK 
// Ek O(V×E^2)
#include<queue>
#include<cstdio>
#include<cstring>
#include<climits>
#define MAX 210
#define re register
#define INF INT_MAX
using std::queue;
namespace OMA
{
   int n,m,s,t;
   bool vis[MAX];
   long long ans;
   int rec[MAX],pre[MAX];
   struct graph
   {
     int next;
     int to;
     int w;
   }edge[MAX*50];
   int cnt=1,head[MAX];
   inline void add(int u,int v,int w)
   {
     edge[++cnt] = (graph){head[u],v,w},head[u] = cnt;
     edge[++cnt] = (graph){head[v],u,0},head[v] = cnt;
   }
   inline int read()
   {
     int s=0,w=1; char ch=getchar();
     while(ch<\'0\'||ch>\'9\'){ if(ch==\'-\')w=-1; ch=getchar(); }
     while(ch>=\'0\'&&ch<=\'9\'){ s=s*10+ch-\'0\'; ch=getchar(); }
     return s*w;
   }
   inline int min(int a,int b)
   { return a<b?a:b; }
   inline bool bfs()
   {
     queue<int>q; q.push(s);
     memset(vis,0,sizeof(vis));
     rec[s] = INF,vis[s] = true;
     while(!q.empty())
     {
       int u = q.front(); q.pop();
       for(re int i=head[u]; i; i=edge[i].next)
       {
         if(edge[i].w)
         {
           int v = edge[i].to;
           if(!vis[v])
           {
             rec[v] = min(rec[u],edge[i].w);
             pre[v] = i,vis[v] = true,q.push(v);
             if(v==t)
             { return 1; }
           }
         }
       }
     }
     return 0;
   }
   inline void update()
   {
     int u = t;
     while(u!=s)
     {
       int i = pre[u];
       edge[i].w -= rec[t];
       edge[i^1].w += rec[t];
       u = edge[i^1].to;
     }
     ans += rec[t];
   }
   signed main()
   {
     n = read(),m = read(),s = read(),t = read();
     for(re int i=1,u,v,w; i<=m; i++)
     { u = read(),v = read(),w = read(); add(u,v,w); }
     while(bfs())
     { update(); }
     printf("%lld\n",ans);
     return 0;
   }
}
signed main()
{ return OMA::main(); }
Dinic 
// Dinic O(V^2×E)
#include<queue>
#include<cstdio>
#include<climits>
#include<cstring>
#define MAX 210
#define re register
#define int long long
#define INF LONG_LONG_MAX
using std::queue;
namespace OMA
{
   int n,m,s,t;
   struct graph
   {
     int next;
     int to;
     int w;
   }edge[MAX*50];
   int dis[MAX];
   long long ans;
   int cnt=1,head[MAX][2];
   inline void add(int u,int v,int w)
   {
     edge[++cnt] = (graph){head[u][0],v,w},head[u][0] = cnt;
     edge[++cnt] = (graph){head[v][0],u,0},head[v][0] = cnt;
   }
   inline int read()
   {
     int s=0,w=1; char ch=getchar();
     while(ch<\'0\'||ch>\'9\'){ if(ch==\'-\')w=-1; ch=getchar(); }
     while(ch>=\'0\'&&ch<=\'9\'){ s=s*10+ch-\'0\'; ch=getchar(); }
     return s*w;
   }
   inline bool bfs()
   {
     queue<int>q; q.push(s);
     memset(dis,0,sizeof(dis));
     dis[s] = 1; head[s][1] = head[s][0];
     while(!q.empty())
     {
       int u = q.front(); q.pop();
       for(re int i=head[u][0],v; i; i=edge[i].next)
       {
         v = edge[i].to;
         if(!dis[v]&&edge[i].w)
         {
           q.push(v);
           dis[v] = dis[u]+1;
           head[v][1] = head[v][0];
           if(v==t)
           { return 1; }
         }
       }
     }
     return 0;
   }
   inline int min(int a,int b)
   { return a<b?a:b; }
   inline int dinic(int u,int flow)
   {
     if(u==t)
     { return flow; }
     int rest = flow;
     for(re int i=head[u][1],v,w; i&&rest; i=edge[i].next) // 注意此判断
     {
       v = edge[i].to,w = edge[i].w;
       if(w&&dis[v]==dis[u]+1)
       {
         int k = dinic(v,min(rest,w));
         if(!k) // 无用点优化
         { dis[v] = 0; }
         edge[i].w -= k;
         edge[i^1].w += k;
         rest -= k;
       }
       head[u][1] = i; // 当前弧优化
     }
     return flow-rest;
   }
   signed main()
   {
     n = read(),m = read(),s = read(),t = read();
     for(re int i=1,u,v,w; i<=m; i++)
     { u = read(),v = read(),w = read(); add(u,v,w); }
     while(bfs())
     { ans += dinic(s,INF); }
     printf("%lld\n",ans);
     return 0;
   }
}
signed main()
{ return OMA::main(); }

然后你发现这过不了加强版，那个要用预流推进或者叫什么HLPP？，不过我不会，所以...

然后你就可以开始做题了，但你发现，你基本上都不会做。

其实是我

因为网络流最重要的是建模，有了模型，直接跑板子即可。

在正式接触一些模型之前，可以先做一道水题来愉悦一下身心。

拆点

先引入几个大家都知道的东西:

超级（虚拟）源点/汇点：

  • 处理有多个源点的最大流问题,通常选择建立虚拟源点的方法,即设一个虚
    拟源点S,再从S到每个真实源点之间建一条流量无穷大的边。
  • 原网络的流一定与新网络的流一一对应: S到真实源点的流量等于该真实源
    点流出的流量之和,且真实源点在新网络中满足流守恒。
  • 多个汇点的处理方式类似。

摘自课件其实大家应该都知道吧QAQ

例题：蜥蜴

这道题应用到了网络流建模时的一个技巧，拆点。

之前应该有接触过拆点，所以此处不再赘述

何为拆点？ 以下内容摘自拆点-oi-wiki

拆点是一种图论建模思想，常用于 网络流，用来处理 点权或者点的流量限制 的问题，也常用于 分层图 。

简单一点来说，就是当流量限制存在于节点上时，通常选择将一个节点拆成两个节点，同时中间连一条容量为点权的边。

节点的流量限制对应到本题上，便是石柱的高度，也就是一个石柱能被蜥蜴跳上去的次数，就是一个节点的流量限制。

所以这题为什么要拆点？

发现有石柱高度或者说能跳的次数限制这一条件，如果我们不拆点的话，是不好去表示的，但如果我们拆点之后，我们就只需要去限制经过石柱多少次即可，而不用去管它向外连了多少条边。

所以如何解决本题？

我们将一个石柱看成两个部分，入口和出口。

如何建图？

首先，我们将超级源点与每个蜥蜴所在的石柱的入口，建一条容量为1的边，表示有一条蜥蜴可以通过。

然后，我们枚举当前石柱所能到达的石柱，将该石柱的出口于其能到达的石柱的入口之间建一条容量为 \(INF\) 的边。

同时注意每个石柱本身存在流量限制，所以需要再将每个石柱的入口和出口之间建一条容量为石柱的高度的边。

最后，将边界距离不超过 \(d\) 的石柱的出口与超级源点建一条容量为 \(INF\) 的边。

然后跑一边最大流。

根据我们的建图，考虑跑完最大流后，得到的是什么，显然，应该是能逃走的蜥蜴的数量。

最后答案拿蜥蜴总数量做差就好。

Code 
#include<queue>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<climits>
#define MAX 810
#define re register
#define INF INT_MAX
using std::min;
using std::queue;
namespace OMA
{
   int r,c,d,s,t,ans;
   int dis[MAX];
   struct graph
   {
     int next;
     int to;
     int w;
   }edge[MAX<<5];
   int tot,p[22][22][2];
   int cnt=1,head[MAX][2];
   char s1[22][22],s2[22][22];
   inline void add(int u,int v,int w)
   {
     edge[++cnt] = (graph){head[u][0],v,w},head[u][0] = cnt;
     edge[++cnt] = (graph){head[v][0],u,0},head[v][0] = cnt;
   }
   inline bool bfs()
   {
     queue<int>q; q.push(s);
     memset(dis,0,sizeof(dis));
     dis[s] = 1,head[s][1] = head[s][0];
     while(!q.empty())
     {
       int u = q.front(); q.pop();
       for(re int i=head[u][0],v; i; i=edge[i].next)
       {
         v = edge[i].to;
         if(!dis[v]&&edge[i].w)
         {
           q.push(v);
           dis[v] = dis[u]+1;
           head[v][1] = head[v][0];
           if(v==t)
           { return 1; }
         }
       }
     }
     return 0;
   }
   inline int dinic(int u,int flow)
   {
     if(u==t)
     { return flow; }
     int rest = flow;
     for(re int i=head[u][1],v; i&&rest; i=edge[i].next)
     {
       v = edge[i].to;
       if(edge[i].w&&dis[v]==dis[u]+1)
       {
         int k = dinic(v,min(rest,edge[i].w));
         if(!k)
         { dis[v] = 0; }
         rest -= k;
         edge[i].w -= k;
         edge[i^1].w += k;
       }
       head[u][1] = i;
     }
     return flow-rest;
   }
   inline double len(int x1,int y1,int x2,int y2)
   { return (double)sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)); }
   signed main()
   {
     scanf("%d%d%d",&r,&c,&d);
     s = 0,t = r*c*2+1;
     for(re int i=1; i<=r; i++)
     { scanf("%s",s1[i]+1); }
     for(re int i=1; i<=r; i++)
     { scanf("%s",s2[i]+1); }
     for(re int i=1; i<=r; i++)
     {
       for(re int j=1; j<=c; j++)
       {
         if(s1[i][j]!=\'0\')
         {
           p[i][j][0] = !p[i][j][0]?++tot:p[i][j][0];
           p[i][j][1] = !p[i][j][1]?++tot:p[i][j][1];
           add(p[i][j][0],p[i][j][1],s1[i][j]-\'0\');
           if(i<=d||j<=d||i+d>r||j+d>c)
           { add(p[i][j][1],t,INF); }
           for(re int k=1; k<=r; k++)
           {
             for(re int l=1; l<=c; l++)
             {
               if(s1[k][l]!=\'0\'&&(k!=i||l!=j)&&d*1.0>=len(i,j,k,l))
               {
                 p[k][l][0] = !p[k][l][0]?++tot:p[k][l][0];
                 add(p[i][j][1],p[k][l][0],INF);
               }
             }
           }
         }
         if(s2[i][j]==\'L\')
         { p[i][j][0] = !p[i][j][0]?++tot:p[i][j][0]; add(s,p[i][j][0],1); ans++; }
       }
     }
     int flow,times = 0;
     while(bfs())
     { ans -= dinic(s,INF); }
     printf("%d\n",ans);
     return 0;
   }
}
signed main()
{ return OMA::main(); }

判定性问题

课件里这么叫

例题：星际战争

赶进度，blog就先放放了。

被ac自动机+dp虐爆，所以又爬回来了。

所谓判定行问题，顾名思义，就是判断可行不可行，对应到本题上就是判断当前的时间能否摧毁Y军团。

读题后可知，本题时间是一个未知量，时间未知，伤害也就不知道，就没办法建图。

既然直接求解不好搞，考虑如何间接求解。

不难发现，随着时间的增加，武器造成的伤害是单调递增的，既然有了单调性，考虑用二分来求解，这样问题也就转换成了一个判定性问题，用最大流来检验是否可行。

具体来说，先二分出来一个时间，那就有了激光武器所能造成的总伤害，那么现在只需要考虑如何将伤害分到每个机器人上，使得它们都能被摧毁。

具体建图：

  1. 从源点向所有武器之间连一条容量为武器当前总伤害的边。
  2. 所有武器向机器人连一条容量为 \(INF\) 的边。
  3. 所有机器人向汇点连一条容量为 装甲值的边。

这样跑出来的最大流就是当前时间下，激光武器能对机器人所造成的总伤害，只需判断其与装甲值之和的关系即可。

代码里的图是反过来建的，都一样的。

Code 
#include<queue>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<climits>
#define MAX 5010
#define re register
using std::min;
using std::fabs;
using std::queue;
namespace OMA
{
   int n,m,s,t;
   int jud[55][55];
   int sum,a[55],b[55];
   const double eps = 1e-8;
   const double INF = 1e8;
   struct graph
   {
     int next;
     int to;
     double w;
   }edge[MAX<<1];
   int cnt=1,head[110][2];
   int dis[110],p[55][2],tot;
   inline void add(int u,int v,double w)
   {
     edge[++cnt] = (graph){head[u][0],v,w},head[u][0] = cnt;
     edge[++cnt] = (graph){head[v][0],u,0},head[v][0] = cnt;
   }
   inline int read()
   {
     int s=0,w=1; char ch=getchar();
     while(ch<\'0\'||ch>\'9\'){ if(ch==\'-\')w=-1; ch=getchar(); }
     while(ch>=\'0\'&&ch<=\'9\'){ s=s*10+ch-\'0\'; ch=getchar(); }
     return s*w;
   }
   inline bool bfs()
   {
     queue<int>q; q.push(s);
     memset(dis,0,sizeof(dis));
     dis[s] = 1,head[s][1] = head[s][0];
     while(!q.empty())
     {
       int u = q.front(); q.pop();
       for(re int i=head[u][0],v; i; i=edge[i].next)
       {
         v = edge[i].to;
         if(!dis[v]&&fabs(edge[i].w)>eps)
         {
           q.push(v);
           dis[v] = dis[u]+1;
           head[v][1] = head[v][0];
           if(v==t)
           { return 1; }
         }
       }
     }
     return 0;
   }
   inline double dinic(int u,double flow)
   {
     if(u==t)
     { return flow; }
     double rest = flow;
     for(re int i=head[u][1],v; i&&fabs(rest)>eps; i=edge[i].next)
     {
       v = edge[i].to;
       if(fabs(edge[i].w)>eps&&dis[v]==dis[u]+1)
       {
         double k = dinic(v,min(rest,edge[i].w));
         if(fabs(k)<=eps)
         { dis[v] = 0; continue ; }
         rest -= k;
         edge[i].w -= k;
         edge[i^1].w += k;
       }
       head[u][1] = i;
     }
     return flow-rest;
   }
   inline void build(double T)
   {
     cnt = 1; memset(head,0,sizeof(head));
     for(re int i=1; i<=n; i++)
     //{ add(s,p[i][0],1.0*a[i]); }
     { add(p[i][0],t,1.0*a[i]); }
     for(re int i=1; i<=m; i++)
     { add(s,p[i][1],b[i]*1.0*T); }
     //{ add(p[i][1],t,b[i]*1.0*T); }
     for(re int i=1; i<=m; i++)
     {
       for(re int j=1; j<=n; j++)
       { if(jud[i][j]){ add(p[i][1],p[j][0],INF); } }
     }
   }
   inline bool check(double T)
   {
     double ans = 0; build(T);
     while(bfs())
     { ans += dinic(s,INF); }
     if(ans>=1.0*sum)
     { return true; }
     else
     { return false; }
   }
   signed main()
   {
     n = read(),m = read(),t = n+m+1;
     for(re int i=1; i<=n; i++)
     { a[i] = read(); p[i][0] = ++tot; sum += a[i]; }
     for(re int i=1; i<=m; i++)
     { b[i] = read(); p[i][1] = ++tot; }
     for(re int i=1; i<=m; i++)
     {
       for(re int j=1; j<=n; j++)
       { jud[i][j] = read(); }
     }
     double l = 0,r = INF,mid;
     while(r-l>eps)
     { mid = (l+r)/2; if(check(mid)){ r = mid; } else{ l = mid; } }
     printf("%0.6lf\n",mid);
     return 0;
   }
}
signed main()
{ return OMA::main(); }

黑白染色

黑白染色适用于一类各元素之间有联系的棋盘问题上，染色后，同类颜色之间不会互相影响。

例题：奇怪的游戏

既然是二维棋盘上的问题，考虑黑白染色。

设黑格个数为 \(sum_{1}\) ，权值和为 \(val_{1}\) ，白格个数为 \(sum_{2}\) ，权值和为 \(val_{2}\) 。

每次操作都是对相邻的黑白格子操作，所以黑白各格子增加的总权值是相同的。

设最后棋盘上格子的权值都变成了 \(x\)，则有，

\(sum_{1}\times x-val_{1}=sum_{2}\times x-val_{2}\) ，则有 \(x=\frac{val_{1}-val_{2}}{sum_{1}-sum_{2}}\) 。

那么就有两种情况，

  1. 当 \(sum_{1} \neq sum_{2}\) 时，可以直接求解，用网络流去检验即可。

  2. 当 \(sum_{1}=sum_{2}\) 时，可以发现，对于一个合法的 \(x\)，那么 \(x+1\) 也是合法的。 所以可以二分 \(x\) ，用网络流来检验。

然后就是喜闻乐见的建图环节，

设棋盘中原来的数为 \(val\) ，则

  1. 源点向所有白点连一条容量为 \(x-val\) 的边。
  2. 白点和黑点之间连一条容量为 \(INF\) 的边。
  3. 黑点向汇点之间连一条容量为 \(x-val\) 的边。

只需检验最大流是否等于 \(\sum x-val\)。

需要注意此题二分的下界原棋盘中最大的数。

Code 
#include<queue>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<climits>
#define MAX 16010
#define re register
#define int long long
using std::min;
using std::max;
using std::queue;
namespace OMA
{
   int T,n,m,s,t;
   struct graph
   {
     int next;
     int to;
     int w;
   }edge[MAX*10];
   int num[2],sum[3];
   int dis[MAX],a[42][42];
   int cnt=1,head[MAX][2];
   int col[42][42],p[42][42],tot;
   const int INF = 1e14;
   inline void add(int u,int v,int w)
   {
     edge[++cnt] = (graph){head[u][0],v,w},head[u][0] = cnt;
     edge[++cnt] = (graph){head[v][0],u,0},head[v][0] = cnt;
   }
   inline int read()
   {
     int s=0,w=1; char ch=getchar();
     while(ch<\'0\'||ch>\'9\'){ if(ch==\'-\')w=-1; ch=getchar(); }
     while(ch>=\'0\'&&ch<=\'9\'){ s=s*10+ch-\'0\'; ch=getchar(); }
     return s*w;
   }
   inline bool bfs()
   {
     queue<int>q; q.push(s);
     memset(dis,0,sizeof(dis));
     dis[s] = 1,head[s][1] = head[s][0];
     while(!q.empty())
     {
       int u = q.front(); q.pop();
       for(re int i=head[u][0],v; i; i=edge[i].next)
       {
         v = edge[i].to;
         if(edge[i].w&&!dis[v])
         {
           q.push(v);
           dis[v] = dis[u]+1;
           head[v][1] = head[v][0];
           if(v==t)
           { return 1; }
         }
       }
     }
     return 0;
   }
   inline int dinic(int u,int flow)
   {
     if(u==t)
     { return flow; }
     int rest = flow;
     for(re int i=head[u][1],v; i&&rest; i=edge[i].next)
     {
       v = edge[i].to;
       if(edge[i].w&&dis[v]==dis[u]+1)
       {
         int k = dinic(v,min(rest,edge[i].w));
         if(!k)
         { dis[v] = 0; }
         rest -= k;
         edge[i].w -= k;
         edge[i^1].w += k;
       }
       head[u][1] = i;
     }
     return flow-rest;
   }
   inline void build(int x)
   {
     sum[2] = 0;
     cnt = 1,memset(head,0,sizeof(head));
     for(re int i=1; i<=n; i++)
     {
       for(re int j=1; j<=m; j++)
       {
         if(!col[i][j])
         { 
           sum[2] += x-a[i][j];
           //printf("delta=%lld\n",x-a[i][j]);
           add(s,p[i][j],x-a[i][j]);
           if(col[i][j+1])
           { add(p[i][j],p[i][j+1],INF); }//printf("x2=%lld y2=%lld\n",i,j+1); }
           if(col[i][j-1])
           { add(p[i][j],p[i][j-1],INF); }//printf("x3=%lld y3=%lld\n",i,j-1); }
           if(col[i+1][j])
           { add(p[i][j],p[i+1][j],INF); }//printf("x4=%lld y4=%lld\n",i+1,j); }
           if(col[i-1][j])
           { add(p[i][j],p[i-1][j],INF); }//printf("x5=%lld y5=%lld\n",i-1,j); }
         }
         else
         { add(p[i][j],t,x-a[i][j]); }
       }
     }
   }
   inline bool check(int x)
   {
     build(x);
     int delta = 0;
     while(bfs())
     { delta += dinic(s,INF); }
     //printf("%lld\n",delta);
     if(delta==sum[2])
     { return true; }
     else
     { return false; }
   }
   signed main()
   {
     //freopen("my.out","w",stdout);
     T = read();
     for(re int i=1; i<=40; i++)
     {
       for(re int j=1; j<=40; j++)
       { p[i][j] = ++tot; }
     }
     t = 1601;
     while(T--)
     {
       int tmp = 0;

       num[0] = num[1] = sum[0] = sum[1] = 0,tot = 0;
       n = read(),m = read();
       memset(col,0,sizeof(col));
       for(re int i=1; i<=n; i++)
       {
         for(re int j=1; j<=m; j++)
         { col[i][j] = (i+j)%2,sum[col[i][j]] += a[i][j] = read(),num[col[i][j]]++; tmp = max(tmp,a[i][j]); }
       }
       if(num[0]!=num[1])
       { int x = (sum[0]-sum[1])/(num[0]-num[1]); if(check(x)){ printf("%lld\n",x*num[0]-sum[0]); } else{ printf("-1\n"); } }
       else
       {
         int l = tmp,r = INF,mid;
         while(l<=r)
         {
           mid = (l+r)>>1;
           //printf("l=%lld r=%lld mid=%lld\n",l,r,mid);
           if(check(mid))
           { r = mid-1; }
           else
           { l = mid+1; }
         }
         if(!check(l))
         { printf("-1\n"); }
         else
         { printf("%lld\n",l*num[0]-sum[0]); }
       }
     }
     return 0;
   }
}
signed main()
{ return OMA::main(); }

逆向思维

发现有些题目正着做直接求满足条件的不好搞，可以考虑反着做求出不符合条件的，再拿总数做差得到答案。

例题：士兵占领

发现直接做不好搞其实是不会，考虑反着做，求出能省多少个士兵，那么最后拿士兵总数一减就是答案。

具体建图：

  1. 源点向各行之间连一条容量为 \(l_{i}\) 的边。
  2. 没有限制的行列之间连一条容量为1的边。
  3. 各列向汇点之间连一条容量为 \(r_{i}\) 的边。

这样跑出来的最大流就是可以省下多少个士兵，拿总数一减就是答案。

Code 
#include<queue>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<climits>
#define re register
#define INF INT_MAX
using std::min;
using std::queue;
namespace OMA
{
   int m,n,k,sum,s,t;
   int l[110],r[110];
   struct graph
   {
     int next;
     int to;
     int w;
   }edge[110*110<<1];
   int cnt=1,head[210][2];
   bool jud[110][110];
   int tot,p[110][2],dis[210];
   inline void add(int u,int v,int w)
   {
     edge[++cnt] = (graph){head[u][0],v,w},head[u][0] = cnt;
     edge[++cnt] = (graph){head[v][0],u,0},head[v][0] = cnt;
   }
   inline int read()
   {
     int s=0,w=1; char ch=getchar();
     while(ch<\'0\'||ch>\'9\'){ if(ch==\'-\')w=-1; ch=getchar(); }
     while(ch>=\'0\'&&ch<=\'9\'){ s=s*10+ch-\'0\'; ch=getchar(); }
     return s*w;
   }
   inline bool bfs()
   {
     queue<int>q; q.push(s);
     memset(dis,0,sizeof(dis));
     dis[s] = 1,head[s][1] = head[s][0];
     while(!q.empty())
     {
       int u = q.front(); q.pop();
       for(re int i=head[u][0],v; i; i=edge[i].next)
       {
         v = edge[i].to;
         if(!dis[v]&&edge[i].w)
         {
           q.push(v);
           dis[v] = dis[u]+1;
           head[v][1] = head[v][0];
           if(v==t)
           { return 1; }
         }
       }
     }
     return 0;
   }
   inline int dinic(int u,int flow)
   {
     if(u==t)
     { return flow; }
     int rest = flow;
     for(re int i=head[u][1],v; i&&rest; i=edge[i].next)
     {
       v = edge[i].to;
       if(edge[i].w&&dis[v]==dis[u]+1)
       {
         int k = dinic(v,min(rest,edge[i].w));
         if(!k)
         { dis[v] = 0; }
         rest -= k;
         edge[i].w -= k;
         edge[i^1].w += k;
       }
       head[u][1] = i;
     }
     //printf("%d %d\n",flow,rest);
     return flow-rest;
   }
   signed main()
   {
     //freopen("node.in","r",stdin);
     m = read(),n = read(),k = read(),t = n+m+1;
     for(re int i=1; i<=m; i++)
     { sum += l[i] = read(); p[i][0] = ++tot; add(s,p[i][0],l[i]); }
     for(re int i=1; i<=n; i++)
     { sum += r[i] = read(); p[i][1] = ++tot; add(p[i][1],t,r[i]); }
     for(re int i=1; i<=k; i++)
     { jud[read()][read()] = true; }
     for(re int i=1; i<=m; i++)
     {
       for(re int j=1; j<=n; j++)
       {
         if(!jud[i][j])
         { add(p[i][0],p[j][1],1); }
       }
     }
     int ans = 0;
     while(bfs())
     { ans += dinic(s,INF); }
     printf("%d\n",sum-ans);
     return 0;
   }
}
signed main()
{ return OMA::main(); }

最小割

一些概念

割

对于一个网络流图 \(G=(V,E)\) ，其割的定义为一种点的划分方式：将所有点划分为 \(S\) 和 \(T=V-S\) 两个集合，其中 \(s\in S\) ，\(t\in T\) 。

割的容量

割 \((S,T)\) 的容量 \(c(S,T)\)表示所有从 \(S\) 到 \(T\) 的边容量之和，即 \(c(S,T)=\sum_{u\in S,v\in T}c(u,v)\) 也可以用 \(c(s,t)\)来表示。

最小割

即求得一个割 \((S,T)\) 使得 \(c(S,T)\) 最小。

最大流最小割定理

\(f(s,t)_{max}=c(s,t)_{min}\)

证明：

对于任意一个可行流 \(f(s,t)\) 的割 \((S,T)\)，有：

\[f(s,t)=S_{出边的总流量}-S_{入边的总流量}\le S_{出边的总流量}=c(s,t) \]

若我们已经求出了最大流 \(f\) ，则残余网络中一定不存在 \(s\) 到 \(t\) 的增广路径，也就是说，\(S\) 的出边一定是满流， \(S\) 的入边一定是零流，于是有：

\[f(s,t)=S_{出边的总流量}-S_{入边的总流量}= S_{出边的总流量}=c(s,t) \]

结合前面的不等式可知，此时 \(f\) 已经最大。

摘自oi-wiki

所以求最小割跑遍最大流即可。

板子:狼抓兔子

直接按题意建图，跑遍最小割即可。

Code 
#include<queue>
#include<cmath>
#include<cstdio>
#include<climits>
#include<cstring>
#define MAX 1010
#define re register
#define INF INT_MAX
using std::min;
using std::queue;
namespace OMA
{
   int n,m,s,t,ans;
   struct graph
   {
     int next;
     int to;
     int w;
   }edge[MAX*MAX*6];
   int cnt=1,head[MAX*MAX][2];
   int dis[MAX*MAX],p[MAX][MAX],tot;
   inline void add(int u,int v,int w)
   {
     edge[++cnt] = (graph){head[u][0],v,w},head[u][0] = cnt;
     edge[++cnt] = (graph){head[v][0],u,w},head[v][0] = cnt;
   }
   inline int read()
   {
     int s=0,w=1; char ch=getchar();
     while(ch<\'0\'||ch>\'9\'){ if(ch==\'-\')w=-1; ch=getchar(); }
     while(ch>=\'0\'&&ch<=\'9\'){ s=s*10+ch-\'0\'; ch=getchar(); }
     return s*w;
   }
   inline bool bfs()
   {
     queue<int>q; q.push(s);
     memset(dis,0,sizeof(dis));
     dis[s] = 1,head[s][1] = head[s][0];
     while(!q.empty())
     {
       int u = q.front(); q.pop();
       for(re int i=head[u][0],v; i; i=edge[i].next)
       {
         v = edge[i].to;
         if(edge[i].w&&!dis[v])
         {
           q.push(v);
           dis[v] = dis[u]+1;
           head[v][1] = head[v][0];
           if(v==t)
           { return 1; }
         }
       }
     }
     return 0;
   }
   inline int dinic(int u,int flow)
   {
     if(u==t)
     { return flow; }
     int rest = flow;
     for(re int i=head[u][1],v; i&&rest; i=edge[i].next)
     {
       v = edge[i].to;
       if(edge[i].w&&dis[v]==dis[u]+1)
       {
         int k = dinic(v,min(rest,edge[i].w));
         if(!k)
         { dis[v] = 0; }
         rest -= k;
         edge[i].w -= k;
         edge[i^1].w += k;
       }
       head[u][1] = i;
     }
     return flow-rest;
   }
   signed main()
   {
     n = read(),m = read(),s = 1,t = n*m;
     for(re int i=1; i<=n; i++)
     {
       for(re int j=1; j<=m; j++)
       { p[i][j] = ++tot; }
     }
     for(re int i=1; i<=n; i++)
     {
       for(re int j=1; j<=m-1; j++)
       { add(p[i][j],p[i][j+1],read()); }
     }
     for(re int i=1; i<=n-1; i++)
     {
       for(re int j=1; j<=m; j++)
       { add(p[i][j],p[i+1][j],read()); }
     }
     for(re int i=1; i<=n-1; i++)
     {
       for(re int j=1; j<=m-1; j++)
       { add(p[i][j],p[i+1][j+1],read()); }
     }
     while(bfs())
     { ans += dinic(s,INF); }
     printf("%d\n",ans);
     return 0;
   }
}
signed main()
{ return OMA::main(); }

相关文章