差别

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

--- 2020-2021:teams:legal_string:王智彪:网络流入门 [2021/07/13 21:07]
王智彪
+++ 2020-2021:teams:legal_string:王智彪:网络流入门 [2021/07/15 18:26] (当前版本)
王智彪 ↷ 页面2020-2021:teams:legal_string:网络流入门被移动至2020-2021:teams:legal_string:王智彪:网络流入门
@@ 行 1: / 行 1: @@
-====== 网络流 ======
+====== 网络流入门 ======
@@ 行 234: / 行 234: @@
 假装源点有无限的水，并向周围的点推流，推的流量不能超过自身的余流，也不能超过边的容量，并让周围的点入队( $s$ 和 $t$ 不能入队)。
 不断取队首的元素，对队首元素进行推流。
 队列为空的时候结束算法，此时汇点的余流即为最大流。
@@ 行 571: / 行 573: @@
 		}
 		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;

CVBB ACM Team

用户工具

站点工具

差别

页面工具