差别

这里会显示出您选择的修订版和当前版本之间的差别。

--- 2020-2021:teams:legal_string:王智彪:网络流入门 [2021/07/12 17:39]
王智彪
+++ 2020-2021:teams:legal_string:王智彪:网络流入门 [2021/07/15 18:26] (当前版本)
王智彪 ↷ 页面2020-2021:teams:legal_string:网络流入门被移动至2020-2021:teams:legal_string:王智彪:网络流入门
@@ 行 1: / 行 1: @@
-====== 网络流 ======
+====== 网络流入门 ======
@@ 行 138: / 行 138: @@
 ==== $ISAP$ ====
-		$Dinic$ 算法中，每次求完增广路之后要跑一遍 $BFS$ 分层。ISAP的策略是在反图中，从 $t$ 到 $s$ 点进行 $BFS$ 。
+$Dinic$ 算法中，每次求完增广路之后要跑一遍 $BFS$ 分层。ISAP的策略是在反图中，从 $t$ 到 $s$ 点进行 $BFS$ 。
-		增广过程和 $Dinic$ 类似，选择比当前点层数少 $1$ 的点来增广，所以也存在当前弧优化。
+增广过程和 $Dinic$ 类似，选择比当前点层数少 $1$ 的点来增广，所以也存在当前弧优化。
-		但不同的是， $ISAP$ 在找增广路的途中会完成下一步的分层，比如现在到了 $i$ 号点，其层数为 $d_{i}$ ，结束这个点的增广过程后，遍历残量网络上 $i$ 的所有出边，找到层最小的出点 $j$ ，然后令 $d_{i}=d_{j}+1$ ，当无出边时，则 $d_{i}=n$ 。则当 $d_{s}≥n$ 时，图上不存在增广路，此时即可终止算法。
+但不同的是， $ISAP$ 在找增广路的途中会完成下一步的分层，比如现在到了 $i$ 号点，其层数为 $d_{i}$ ，结束这个点的增广过程后，遍历残量网络上 $i$ 的所有出边，找到层最小的出点 $j$ ，然后令 $d_{i}=d_{j}+1$ ，当无出边时，则 $d_{i}=n$ 。则当 $d_{s}≥n$ 时，图上不存在增广路，此时即可终止算法。
-		$ISAP$ 还存在 $GAP$ 优化，记录层数为 $i$ 的点的数量为 $num[i]$ ，每当将一个点的层数从 $x$ 更新到 $y$ 时，要同时更行 $num$ 数组的值，当某次更新之后，如果 $num[x]==0$ 则图中出现断层，必然找不到增广路，则可以直接终止算法(将 $d_{s}$ 标记为 $n$ )。
+$ISAP$ 还存在 $GAP$ 优化，记录层数为 $i$ 的点的数量为 $num[i]$ ，每当将一个点的层数从 $x$ 更新到 $y$ 时，要同时更行 $num$ 数组的值，当某次更新之后，如果 $num[x]==0$ 则图中出现断层，必然找不到增广路，则可以直接终止算法(将 $d_{s}$ 标记为 $n$ )。
-		时间复杂度与 $Dinic$ 等同，但是实际时间上优于 $Dinic$ 。
+时间复杂度与 $Dinic$ 等同，但是实际时间上优于 $Dinic$ 。
 <hidden 代码>
@@ 行 227: / 行 227: @@
 ==== 预流推进 ====
-		思想：从源点疯狂“灌水”，水不停流向汇点，能流多少流多少，最后汇点的水的量，就是最大流。
+思想：从源点疯狂“灌水”，水不停流向汇点，能流多少流多少，最后汇点的水的量，就是最大流。
-		余流：每个点当前有多少水。
+余流：每个点当前有多少水。
-		步骤：
+步骤：
-   		假装源点有无限的水，并向周围的点推流，推的流量不能超过自身的余流，也不能超过边的容量，并让周围的点入队( $s$ 和 $t$ 不能入队)。
+假装源点有无限的水，并向周围的点推流，推的流量不能超过自身的余流，也不能超过边的容量，并让周围的点入队( $s$ 和 $t$ 不能入队)。
-   		不断取队首的元素，对队首元素进行推流。
-   		队列为空的时候结束算法，此时汇点的余流即为最大流。
+不断取队首的元素，对队首元素进行推流。
+队列为空的时候结束算法，此时汇点的余流即为最大流。
 但是有可能会存在两个点之间来回推流，导致死循环。
@@ 行 245: / 行 247: @@
 ==== $HLPP$ ====
-	步骤：
+步骤：
 从 $t$ 到 $s$ 反向 $BFS$ ，使得每个点有一个初始高度。
@@ 行 259: / 行 261: @@
 为什么相较于普通的预流推进变快了呢？首先我们用$BFS$预处理了高度，并且因为有优先队列，所以我们可以每次选用高度最高的点，这样大大减少了推流的次数。
-	优化：
+优化：
-		$GAP$ 优化，同 $ISAP$ ，如果某个高度不存在，将所有比该高度高的节点标记为不可到达。（使它的高度为 $n+1$ ，这样就会直接向 $s$ 推流了）。
+ $GAP$ 优化，同 $ISAP$ ，如果某个高度不存在，将所有比该高度高的节点标记为不可到达。（使它的高度为 $n+1$ ，这样就会直接向 $s$ 推流了）。
-		时间复杂度：理论上是 $O(n^{2}\sqrt{m})$ ，但是有较大常数，实际状况下，一般 $ISAP$ 已经足够用。
+时间复杂度：理论上是 $O(n^{2}\sqrt{m})$ ，但是有较大常数，实际状况下，一般 $ISAP$ 已经足够用。
 <hidden 代码>
@@ 行 395: / 行 397: @@
 对于放在集合 $A$ 产生的代价，我们可以从源点 $s$ 向这个点连一条容量为 $a_{i}$ 的边，对于放在集合 $B$ 产生的代价，我们可以从这个点向汇点 $t$ 连一条容量为 $b_{i}$ 的边，于是利用最小割的思想，因为一个点只能属于一个集合，所以两条边至少要有一条被选中，不然会有从 $s$ 到 $t$ 的流。
-而对于最后一种情况，不妨设 $u_{i}$ 在 $A$ 集合里, $v_{i}$ 在 $B$ 集合里，所以现在是 $s→u_{i}   v_{i}→t$ ，而想要承担 $w_{i}$ 的代价，我们只需要在 $u_{i}$ , $v_{i}$ 之间连一条 $w_{i}$ 的边，因为另一种情况也有可能，所以这条边要是双向的，于是图就构建完毕了。
+而对于最后一种情况，不妨设 $u_{i}$ 在 $A$ 集合里, $v_{i}$ 在 $B$ 集合里，所以现在是 $s→u_{i}$ 和 $v_{i}→t$ 有边，而想要承担 $w_{i}$ 的代价，我们只需要在 $u_{i}$ , $v_{i}$ 之间连一条 $w_{i}$ 的边，因为另一种情况也有可能，所以这条边要是双向的，于是图就构建完毕了。
 ===== 代码练习 =====
@@ 行 433: / 行 435: @@
 		printf("%lld\n",ISAP());
 	}
+</code>
+</hidden>
+.[[https://www.luogu.com.cn/problem/P2857]]
+给定 $n$ 只牛和 $m$ 个牛棚 $(n≤1000,m≤20)$ ， $n$ 只牛每只都有自己的想法，将 $m$ 个牛棚按照喜欢程度进行排序，最后给出 $m$ 个牛棚的容量，求在所有的分配方案中，让牛所居牛棚的座次最高与最低的跨度最小
+每只牛看做一个点，每个牛棚也看做一个点，再构造一个源点和汇点。首先牛棚容量是牛棚的点连到汇点，容量为牛棚容量。源点连到各个牛，容量为 $1$ ，最后是牛和牛棚中间的边。注意到答案具有单调性，可以二分解决，最小为 $1$ ，最大为 $m$ ，对于每一个 $mid$ ，可以把从第 $i$ 到第 $i+mid-1$ 的牛棚和所有的牛都连起来，容量为 $1$ ，如果跑出的最大流是 $n$ ，证明所有的牛都能分进去，二分继续。这样点数是 $O(n+m)$ ，边数是 $O(n×m)$ ，二分次数是 $O(logm)$ 的，每次要建 $O(m)$ 次图，但是由于各种玄学优化以及实际数据较水，所以个位数 $ms$ 就通过了。
+<hidden 代码>
+<code cpp>
+bool check(int v) {
+	for(int i=1; i<=m-v+1; i++) {
+		cnt=1;
+		memset(head,0,sizeof(head));
+		s=m+n+1,t=m+n+2;
+		for(int j=1; j<=n; j++) {
+			addedge(s,j,1);
+			addedge(j,s,0);
+		}
+		for(int j=1; j<=m; j++) {
+			addedge(j+n,t,room[j]);
+			addedge(t,j+n,0);
+		}
+		for(int j=1; j<=n; j++) {
+			for(int k=i; k<=i+v-1; k++) {
+				addedge(j,bj[j][k]+n,1);
+				addedge(bj[j][k]+n,j,0);
+			}
+		}
+		ll anss=ISAP();
+		if(anss==n) return true;
+	}
+	return false;
+}
+int main() {
+	while(~scanf("%d %d",&n,&m)) {
+		for(int i=1; i<=n; i++) {
+			for(int j=1; j<=m; j++) {
+				scanf("%d",&bj[i][j]);
+			}
+		}
+		for(int i=1; i<=m; i++) {
+			scanf("%lld",&room[i]);
+		}
+		int l=1,r=m,ans=-1;
+		while(l<=r) {
+			int mid=l+r>>1;
+			if(check(mid)) {
+				ans=mid;
+				r=mid-1;
+			} else {
+				l=mid+1;
+			}
+		}
+		if(ans==-1) printf("%d\n",m);
+		else printf("%d\n",ans);
+	}
+	return 0;
+}
+</code>
+</hidden>
+.[[https://www.luogu.com.cn/problem/CF387D]]
+定义一个有趣的图是：
+.存在一个点 $u$ 有自环
+.这个点和其他所有点v都有边 $(u,v)$ 和边 $(v,u)$ 。
+.其他所有点的入度和出度刚好为 $2$ 。
+.没有重边
+保证输入没有重边
+现在可以进行增加一条边或者删除一条边的操作，问给定一个图最少操作多少次才能把它变成一张有趣的图。
+首先我们遍历每一个点，让它作为结点 $u$ 。对于自环和所有的那两条边，缺少则添加它。对于其他的点，因为要保证这些点的入度出度都为 $2$ ，因为有 $n-1$ 个点，发现正好要 $n-1$ 条边。并且相当于每一个点都只有一条边进入和一条边发出，所以我们可以拆点并用网络流或者二分图来解决。假设网络流跑出的结果是 $tmpans$ ，代表最多有这些边是有用的，其他边要删去，所以要删掉原来和 $u$ 无关的所有边的数量 $-tmpans$ ，还要补足 $n-1-tmpans$ 条边，并且补足这些边一定有一组解是满足题意的。三种答案加起来即为所求。复杂度 $O(mn^{\frac 3 2})$ 。
+<hidden 代码>
+<code cpp>
+int main() {
+	while(~scanf("%d %d",&n,&m)) {
+		for(int i=1,u,v; i<=m; i++) {
+			u=Read();
+			v=Read();
+			mapp[u][v]++;
+		}
+		int final_ans=INT_MAX;
+		for(int i=1; i<=n; i++) {
+			int anss=0;
+			if(!mapp[i][i]) anss++;
+			for(int j=1; j<=n; j++) {
+				if(j==i) continue;
+				if(!mapp[j][i]) anss++;
+				if(!mapp[i][j]) anss++;
+			}
+			memset(head,0,sizeof(head));
+			cnt=1;
+			int cntt=0;
+			for(int j=1; j<=n; j++) {
+				if(j==i) continue;
+				for(int k=1; k<=n; k++) {
+					if(k==i) continue;
+					if(mapp[j][k]) {
+						cntt++;
+						addedge(j,k+n,1);
+						addedge(k+n,j,0);
+					}
+				}
+			}
+			s=i,t=i+n;
+			for(int j=1;j<=n;j++){
+				addedge(s,j,1);
+				addedge(j,s,0);
+			}
+			for(int j=1;j<=n;j++){
+				addedge(j+n,t,1);
+				addedge(t,j+n,0);
+			}
+			ll tmp_ans=ISAP();
+			//printf("%lld\n",tmp_ans);
+			int qwq=cntt-tmp_ans+n-1-tmp_ans+anss;
+			if(qwq<final_ans){
+				final_ans=qwq;
+			}
+			//printf("%d %d\n",qwq,final_ans);
+		}
+		printf("%d\n",final_ans);
+	}
+	return 0;
+}
+</code>
+</hidden>
+.[[https://www.luogu.com.cn/problem/P1344]]
+给定 $n$ 个点， $1$ 是源点， $n$ 是汇点，给出 $m$ 条有向边，每条边有割掉的代价，我们想让代价最小，并且找到代价最小的前提下割掉最少的边。
+割掉最少的边貌似之前有提过，将所有的边权改为 $1$ ，跑一遍网络流，但是这样不一定是最大流。于是我们把原来的容量乘一个很大的权值最后再加 $1$ ，因为权值很大，剩下的 $1$ 不会改变最大流的值（除以原来的权值即可），而又通过最小割的理论得到结果必然是切掉最少的边的结果。注意数据范围把 $inf$ 设大一点即可。
+<hidden 代码>
+<code cpp>
+int main() {
+	while(~scanf("%d %d",&n,&m)) {
+		ll w;
+		cnt=1;
+		for(int i=1,u,v; i<=m; i++) {
+			u=Read();
+			v=Read();
+			scanf("%lld",&w);
+			addedge(u,v,(m+1)*w+1);
+			addedge(v,u,0);
+		}
+		s=1,t=n;
+		ll tmp=ISAP();
+		printf("%lld %lld\n",tmp/(m+1),tmp%(m+1));
+	}
+	return 0;
+}
+</code>
+</hidden>
+.[[https://www.luogu.com.cn/problem/P3153]]
+舞会上有 $n$ 个男生和 $n$ 个女生，每首曲子需要所有男女配对跳舞，但是有一些男女互相喜欢，其他的都是互相不喜欢，要求每个男生和每个女生最多只能和 $k$ 个不喜欢的异性跳舞，问最多能有多少首舞曲？
+答案显然具有单调性，因此二分解之，比如二分到 $v$ 。
+难点是如何限制只能和 $k$ 个不喜欢的异性跳舞，这里显然要把一个人拆成喜欢和不喜欢两个点，不然无法限制不喜欢这个点。
+然后是男女喜欢的话就男喜欢连向女喜欢，容量为 $1$ 。男女不喜欢是男不喜欢连女不喜欢，容量为 $1$ 。
+最后解决源点汇点以及喜欢不喜欢之间边的问题，因为是对不喜欢有限制，而对喜欢不限制，所以是源点连男喜欢 $v$ 的边，然后男喜欢连男不喜欢 $k$ 的边，女那边同理，跑一遍最大流，如果等于 $n×v$ ，则说明可以跳 $v$ 首，反之不可，于是此题可解。
+<hidden 代码>
+<code cpp>
+string str;
+int mapp[52][52];
+bool check(int v) {
+	cnt=1;
+	memset(head,0,sizeof(head));
+	for(int i=1; i<=n; i++) {
+		addedge(s,i,v);
+		addedge(i,s,0);
+		addedge(i,i+n,m);
+		addedge(i+n,i,0);
+		addedge(i+3*n,t,v);
+		addedge(t,i+3*n,0);
+		addedge(i+2*n,i+3*n,m);
+		addedge(i+3*n,i+2*n,0);
+	}
+	for(int i=1; i<=n; i++) {
+		for(int j=1; j<=n; j++) {
+			if(mapp[i][j]) {
+				addedge(i,j+3*n,1);
+				addedge(j+3*n,i,0);
+			} else {
+				addedge(i+n,j+n*2,1);
+				addedge(j+n*2,i+n,0);
+			}
+		}
+	}
+	ll tmpans=ISAP();
+	if(tmpans==v*n) return true;
+	return false;
+}
+int main() {
+	while(~scanf("%d %d",&n,&m)) {
+		for(int i=1; i<=n; i++) {
+			cin>>str;
+			for(int j=0; j<n; j++) {
+				if(str[j]=='Y') mapp[i][j+1]=1;
+			}
+		}
+		int l=0,r=1e9,ans=0;
+		s=4*n+1,t=4*n+2;
+		while(l<=r) {
+			int mid=(l+r)>>1;
+			if(check(mid)) {
+				l=mid+1;
+				ans=mid;
+			} else {
+				r=mid-1;
+			}
+		}
+		printf("%d\n",ans);
+	}
+	return 0;
+}
+</code>
+</hidden>
+.[[https://www.luogu.com.cn/problem/P3872]]
+给出 $N$ 部电影和依赖总数 $M$ ，某人对每部电影都有一个体验值，依赖关系指的是对于一个有序对 $(A,B)$ 和一个值 $C$ ，如果看了 $A$ 没看 $B$ ，则体验值减少 $C$ 。求最大体验值。这里原始的体验值范围是 $[-1000,1000]$ 。电影数不超过 $100$ 。
+有负数怎么建图呢？这里对于体验值正的电影，我们从源点连到这个电影代表的点，负数先不管，对于有序对 $(A,B)$ 和值 $C$ ，我用直觉从 $A$ 到 $B$ 连了一个权值为 $C$ 的边。
+剩下是原始体验值为负的情况，貌似还没出现汇点，我尝试着把这些点连向汇点，权值为给定值的相反数。这时如果对这张图跑最大流，最小割貌似是将所有的体验值正的电影选定的情况下，为了保证最后体验值最大，舍弃的最少的情况。
+具体地说，舍弃从源点开始的边表示退掉体验值为正的那部电影，舍弃电影之间的边表示就是看 $A$ 不看 $B$ ，舍弃到汇点的边表示为了不舍弃 $C$ 而看 $B$ 。所以用正的总量-最小割即为所求。
+<hidden 代码>
+<code cpp>
+int main() {
+	while(~scanf("%d %d",&n,&m)) {
+		cnt=1;
+		s=n+1,t=n+2;
+		ll sum=0;
+		for(int i=1,tmp; i<=n; i++) {
+			tmp=Read();
+			if(tmp>0) {
+				addedge(s,i,tmp);
+				addedge(i,s,0);
+				sum+=tmp;
+			} else {
+				addedge(i,t,-tmp);
+				addedge(t,i,0);
+			}
+		}
+		for(int i=1,u,v,w;i<=m;i++){
+			u=Read();v=Read();w=Read();
+			addedge(u,v,w);
+			addedge(v,u,0);
+		}
+		printf("%lld\n",sum-ISAP());
+	}
+	return 0;
+}
+</code>
+</hidden>
+.[[https://www.luogu.com.cn/problem/P4313]]
+经典问题。大意：一个班坐成 $n×m$ 的矩阵，每个人选文科会获得一种满意值，选理科会获得另一种满意值，这个人和周围（上下左右）的人都选理科会额外获得第三种满意值，都选文科会额外获得第四种满意值，问如何让满意值最大。
+仿照上一题，我们先将所有的满意值相加，再利用最小割减下去。对于一个点因为没有别的限制，所以不需要拆点，对于文科需要将源点连到这个点，理科是这个点连到汇点。
+后两种额外的需要自己和周围的人都选同一科，是且的关系。并且由于我们建图的意义是割掉哪条边代表排除哪条边代表的那种情况，只有把这个奖励单独作为一个点，并且如果是文科，从源点连到这个点，权值为奖励值，奖励点分别和那几个座位代表的点相连，权值为 $inf$ ，才能使得如果有一个点不连源点则一定连了汇点，那么会有流从源点到奖励点再到那个点最后到汇点，只能将这个奖励的流割掉，所以满足题意。
+<hidden 代码>
+<code cpp>
+int dx[5]={0,1,-1,0,0};
+int dy[5]={0,0,0,1,-1};
+bool check(int x,int y){
+	return x>=1&&x<=n&&y>=1&&y<=m;
+}
+int main() {
+	while(~scanf("%d %d",&n,&m)) {
+		cnt=1;
+		memset(head,0,sizeof(head));
+		s=n*m*4+1,t=n*m*4+2;
+		ll sum=0;
+		for(int i=1,tmp; i<=n; i++) {
+			for(int j=1; j<=m; j++) {
+				tmp=Read();
+				sum+=tmp;
+				addedge(s,(i-1)*m+j,tmp);
+				addedge((i-1)*m+j,s,0);
+			}
+		}
+		for(int i=1,tmp; i<=n; i++) {
+			for(int j=1; j<=m; j++) {
+				tmp=Read();
+				sum+=tmp;
+				addedge((i-1)*m+j,t,tmp);
+				addedge(t,(i-1)*m+j,0);
+			}
+		}
+		for(int i=1,tmp; i<=n; i++) {
+			for(int j=1; j<=m; j++) {
+				tmp=Read();
+				sum+=tmp;
+				addedge(s,(i-1+n)*m+j,tmp);
+				addedge((i-1+n)*m+j,s,0);
+				for(int k=0;k<5;k++){
+					int xx=i+dx[k],yy=j+dy[k];
+					if(check(xx,yy)){
+						addedge((i-1+n)*m+j,(xx-1)*m+yy,inf);
+						addedge((xx-1)*m+yy,(i-1+n)*m+j,0);
+					}
+				}
+			}
+		}
+		for(int i=1,tmp; i<=n; i++) {
+			for(int j=1; j<=m; j++) {
+				tmp=Read();
+				sum+=tmp;
+				addedge((i-1+2*n)*m+j,t,tmp);
+				addedge(t,(i-1+2*n)*m+j,0);
+				for(int k=0;k<5;k++){
+					int xx=i+dx[k],yy=j+dy[k];
+					if(check(xx,yy)){
+						addedge((xx-1)*m+yy,(i-1+2*n)*m+j,inf);
+						addedge((i-1+2*n)*m+j,(xx-1)*m+yy,0);
+					}
+				}
+			}
+		}
+		printf("%lld\n",sum-ISAP());
+	}
+	return 0;
+}
 </code>
 </hidden>

CVBB ACM Team

用户工具

站点工具

差别

页面工具