差别

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

--- 2020-2021:teams:legal_string:王智彪:网络流入门 [2021/07/14 14:25]
王智彪 ↷ 页面名由2020-2021:teams:legal_string:网络流改为2020-2021:teams:legal_string:网络流入门
+++ 2020-2021:teams:legal_string:王智彪:网络流入门 [2021/07/15 18:26] (当前版本)
王智彪 ↷ 页面2020-2021:teams:legal_string:网络流入门被移动至2020-2021:teams:legal_string:王智彪:网络流入门
@@ 行 1: / 行 1: @@
-====== 网络流 ======
+====== 网络流入门 ======
@@ 行 681: / 行 681: @@
 		}
 		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

用户工具

站点工具

差别

页面工具