首页 > 其他分享 >【学习笔记】(1) 差分约束

【学习笔记】(1) 差分约束

时间：2023-05-20 18:45:20浏览次数：63  
标签：ch int 笔记 约束 ge le 差分 dis

1.算法介绍

差分约束系统 是一种特殊的 \(N\) 元一次不等式组，它包含 \(N\) 个变量 \(X_1 \sim X_N\) 以及 \(M\) 个约束条件，每个约束条件是由两个其中的变量做差构成的，形如 \(X_i - X_j \le c_k\)，其中 \(1 \le i,j \le N, 1 \le k \le N\) 并且 \(c_k\) 是常数（可以是非负数，也可以是负数）。我们要解决的问题是：求一组解 ，\(X_1 = a_1,X_2 = a_2,\dots,x_N = a_N\) 使得所有的约束条件得到满足，否则判断出无解。

差分约束系统中的每个约束条件 \(X_i - X_j \le c_k\) 都可以变形成 \(x_i \le X_j + c_k\)，这与单源最短路中的三角形不等式 \(dis[y] \le dis[x] + z\) 非常相似。因此，我们可以把每个变量 \(X_i\) 看做图中的一个结点 \(i\)，对于每个约束条件 \(X_i - X_j \le c_k\)，从结点 \(j\) 向结点 \(i\) 连一条长度为 \(c_k\) 的有向边，然后再从超级源点 0 向每个点连长度为 0 的边防止图不连通（或者一开始令所有 \(dis_i = 0\) 并将所有点入队），跑最短路，每个点的最短路长度就是一组解。。

注意到，如果 \(\{a_1,a_2,\dots,a_N \}\) 是该差分约束系统的一组解，那么对于任意的常数 \(\Delta\)，\(\{a_1+\Delta,a_2+\Delta,\dots,a_N+\Delta \}\) 显然也是该差分约束系统的一组解，因为这样做差后 \(\Delta\) 刚好被消掉。

因为一般这个 \(c_k\) 有负值（全是非负的话所有数相等不就行了嘛），所以用 Bellman-Ford 或 SPFA 求解最短路。显然，若出现负环则无解。最坏时间复杂度 \(O(nm)\)。

模板题 P5960 【模板】差分约束算法。

#include<bits/stdc++.h>
#define N 5005
using namespace std;
int read(){
	int x = 0, f = 1; char ch = getchar();
	while(ch < '0' || ch > '9'){if(ch == '-') f = -f; ch = getchar();}
	while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar();}
	return x * f;
}
int n, m, tot;
int to[N], Head[N], Next[N], edge[N];
bool vis[N];
int dis[N], in[N];
queue<int> q;
void add(int u, int v, int w){
	to[++tot] = v, Next[tot] = Head[u] ,Head[u] = tot, edge[tot] = w;
}
int main(){
	n = read(), m = read();
	for(int i = 1; i <= m; ++i){
		int v = read(), u = read(), w = read();
		add(u, v, w);
	}
	for(int i = 1; i <= n; ++i) q.push(i), vis[i] = 1, ++in[i]; //这里也可以建一个超级源点
	while(!q.empty()){
		int x = q.front(); q.pop(); vis[x] = 0;
		for(int i = Head[x]; i; i = Next[i]){
			int y = to[i];
			if(dis[y] > dis[x] + edge[i]){
				dis[y] = dis[x] + edge[i];
				if(!vis[y]) ++in[y], vis[y] = 1, q.push(y);
				if(in[y] > n) return printf("NO\n"), 0;
			}
		}
	}
	for(int i = 1; i <= n; ++i) printf("%d ",dis[i]); printf("\n");
	return 0;
}

2.解的字典序极值

一般而言差分约束系统的解没有 “字典序” 这个概念，因为我们只对变量之间的差值进行约束，而变量本身的值可以随着某个变量取值的固定而固定，所以解的字典序可以趋于无穷大或无穷小。

字典序的极值建立于变量有界的基础上，假如 \(X_i \le 0\) ,要求出整个差分约束系统的字典序最大。其实 \(X_i \le 0\) 可以看成 \(X_i \le X_0 + 0\)，所以我们建立虚点 0，将其初始 \(dis\) 赋为 0，并向其它所有变量连权值为 0 的边（这等价于一开始令所有点入队且 \(dis_i=0\)）。

首先明确一点，对于一条从 $ u → v$ 的边权为 \(w(u,v)\) 的边，它的含义为限制 $X_u+w(u,v)\ge X_v $。

那么通过 SPFA 求得的一组解，恰为字典序最大解。

证明：

考虑 0 到每个节点的最短路树。对于树上每条边均满足 \(X_i+w(i,j)=X_j\)。若 \(X_i+w(i,j)>X_j\)，那么整张图还可以继续松弛，若 \(X_i+w(i,j)<X_j\)，说明 \(j\) 的最短路不是由 \(i\) 继承而来，因此 \((i,j)\) 必然不会作为树边出现。

这说明树上的 \(X_i+w(i,j)\ge X_j\) 的限制已经取满，取到了等号（\(X_j\) 不能再大了，再大就破坏了限制），每个变量都取到了其理论上界，自然就得到了字典序最大解。

证毕

对于字典序最小解，我们限制 \(X_i\ge 0\)。那么其实我们可以将限制转为 \(X_i \ge X_0 + 0\), 0 向所有点连一个边 \(w(0,i)\) \(X_j \ge X_i - c_k\)，即与之前求最大时见相反的边，权值也相反，（可以自己画一下图好好理解一下），用 SPFA 跑最长路，得到的解就是字典序最小。

3.例题

3.1 P5590 赛车游戏

好题。

我们可以转化一下思路，与其设置边权使路径长度相等，不如设置路径长度去拟合边权的限制。

设 \(dis_i\)
为 \(1→i\) 的最短路，只需保证对于所有边 \(w(u,v)\) 有 $ w(u,v) = dis_v = dis_u $ 即可使任意一条简单路径长相等。于是 $ 1 \le dis_v - dis_u \leq 9$ ，转化为 \(dis_u+9 \ge dis_v\) 与 $ dis_v - 1\ge dis_u$，差分约束求解即可。注意不在 \(1→n\) 的任意一条路径上的边没有用，这些边不应计入限制，随便标权值，浅浅来个 rand就行了。

#include<bits/stdc++.h>
#define N 1005
#define M 4005
using namespace std;
int read(){
	int x = 0, f = 1; char ch = getchar();
	while(ch < '0' || ch > '9'){if(ch == '-') f = -f; ch = getchar();}
	while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar();}
	return x * f;
}
int n, m, tot;
int Head[N], to[M], Next[M], edge[M];
int dis[N], in[N];
bool vis[N], VIS[2][N], flag[N];
vector<int> E[2][N];
struct edge{
	int u, v;
}a[M];
void add(int u, int v, int w){
	to[++tot] = v, Next[tot] = Head[u], Head[u] = tot, edge[tot] = w;
}
void dfs(int x, int k){
	VIS[k][x] = 1;
	for(auto y : E[k][x]){
		if(VIS[k][y]) continue;
		dfs(y, k);
	}
}
bool spfa(int s){
	memset(dis, 0x3f, sizeof(dis));
	queue<int> q; q.push(s);
	vis[s] = 1, dis[s] = 0, ++in[s];
	while(!q.empty()){
		int x = q.front(); q.pop(), vis[x] = 0;
		for(int i = Head[x]; i; i = Next[i]){
			int y = to[i];
			if(dis[y] > dis[x] + edge[i]){
				dis[y] = dis[x] + edge[i];
				if(!vis[y]) ++in[y], vis[y] = 1, q.push(y);
				if(in[y] > n) return true;
			}
		}
	}
	return false;
}
int main(){
	srand(time(0));
	n = read(), m = read();
	for(int i = 1; i <= m; ++i){
		a[i].u = read(), a[i].v = read();
		E[0][a[i].u].push_back(a[i].v), E[1][a[i].v].push_back(a[i].u);
	}
	dfs(1, 0), dfs(n, 1);
	if(!VIS[0][n]) return printf("-1\n"), 0;
	for(int i = 1; i <= n; ++i) flag[i] = (VIS[0][i] & VIS[1][i]);
	for(int i = 1; i <= m; ++i){
		if(flag[a[i].u] && flag[a[i].v]) add(a[i].u, a[i].v, 9), add(a[i].v, a[i].u, -1);
	}
	if(spfa(1)) return printf("-1\n"), 0;
	printf("%d %d\n", n, m);
	for(int i = 1; i <= m; ++i){
		if(flag[a[i].u] && flag[a[i].v]) printf("%d %d %d\n", a[i].u, a[i].v, dis[a[i].v] - dis[a[i].u]);
		else printf("%d %d %d\n", a[i].u, a[i].v, rand() % 9 + 1);
	}
	return 0;
}

3.2 CF241E Flights

基本同上题，把边权限制改一下在进行差分约束就行了。

#include<bits/stdc++.h>
#define N 1005
#define M 10005
using namespace std;
int read(){
	int x = 0, f = 1; char ch = getchar();
	while(ch < '0' || ch > '9'){if(ch == '-') f = -f; ch = getchar();}
	while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar();}
	return x * f;
}
int n, m, tot;
int Head[N], to[M], Next[M], edge[M];
int dis[N], in[N];
bool vis[N], VIS[2][N], flag[N];
vector<int> E[2][N];
struct edge{
	int u, v;
}a[M];
void add(int u, int v, int w){
	to[++tot] = v, Next[tot] = Head[u], Head[u] = tot, edge[tot] = w;
}
void dfs(int x, int k){
	VIS[k][x] = 1;
	for(auto y : E[k][x]){
		if(VIS[k][y]) continue;
		dfs(y, k);
	}
}
bool spfa(int s){
	memset(dis, 0x3f, sizeof(dis));
	queue<int> q; q.push(s);
	vis[s] = 1, dis[s] = 0, ++in[s];
	while(!q.empty()){
		int x = q.front(); q.pop(), vis[x] = 0;
		for(int i = Head[x]; i; i = Next[i]){
			int y = to[i];
			if(dis[y] > dis[x] + edge[i]){
				dis[y] = dis[x] + edge[i];
				if(!vis[y]) ++in[y], vis[y] = 1, q.push(y);
				if(in[y] > n) return true;
			}
		}
	}
	return false;
}
int main(){
	srand(time(0));
	n = read(), m = read();
	for(int i = 1; i <= m; ++i){
		a[i].u = read(), a[i].v = read();
		E[0][a[i].u].push_back(a[i].v), E[1][a[i].v].push_back(a[i].u);
	}
	dfs(1, 0), dfs(n, 1);
	for(int i = 1; i <= n; ++i) flag[i] = (VIS[0][i] & VIS[1][i]);
	for(int i = 1; i <= m; ++i){
		if(flag[a[i].u] && flag[a[i].v]) add(a[i].u, a[i].v, 2), add(a[i].v, a[i].u, -1);
	}
	if(spfa(1)) return printf("No\n"), 0;
	printf("Yes\n");
	for(int i = 1; i <= m; ++i){
		if(flag[a[i].u] && flag[a[i].v]) printf("%d\n", dis[a[i].v] - dis[a[i].u]);
		else printf("%d\n", rand() % 2 + 1);
	}
	return 0;
}

3.3 P3275 [SCOI2011]糖果

这题可以将题中五个关系改成差分约束的限制。

  • 如果 \(X=1\)， 表示第 \(A\) 个小朋友分到的糖果必须和第 \(B\) 个小朋友分到的糖果一样多，改为 \(dis_A \ge dis_B + 0\) 和 \(dis_B \ge dis_A + 0\)；
  • 如果 \(X=2\)， 表示第 \(A\) 个小朋友分到的糖果必须少于第 \(B\) 个小朋友分到的糖果，改为 \(dis_B \ge dis_A + 1\) ；
  • 如果 \(X=3\)， 表示第 \(A\) 个小朋友分到的糖果必须不少于第 \(B\) 个小朋友分到的糖果，改为 \(dis_A \ge dis_B\)；
  • 如果 \(X=4\)， 表示第 \(A\) 个小朋友分到的糖果必须多于第 \(B\) 个小朋友分到的糖果，改为 \(dis_A \ge dis_B + 1\)；
  • 如果 \(X=5\)， 表示第 \(A\) 个小朋友分到的糖果必须不多于第 \(B\) 个小朋友分到的糖果，改为 $dis_B \ge dis_A $；

至于为什么这么改，因为题中要求的是满足限制的最少糖果数且 \(dis_i \ge 1\)，所以相当于是求字典序最小，可以本篇上文 2.解的字典序极值。另外，还要建立一个超级源点 0 向 所有点连边权为 1 的边，来满足 \(dis_i \ge 1\) 的限制。

还有这题由于数据范围比较大，我们最好不使用 SPFA ，以防被卡。我们可以使用 Tarjan 缩点来判正环，有正环就无解，具体地，对于在同一强连通分量的点来说，如果他们之间的边为 1 ,那么肯定有正环，因为边权要么为 1 ，要么为 0 。 之后由于 Tarjan 缩点后 成了 DAG 图，我们可以用拓扑来求解答案，对于同一强连通分量的点他们得到的糖果数显然是相同的。

#include<bits/stdc++.h>
#define M 300005
#define N 100005
#define ll long long
using namespace std;
int read(){
	int x = 0, f = 1; char ch = getchar();
	while(ch < '0' || ch > '9'){if(ch == '-') f = -f; ch = getchar();}
	while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar();}
	return x * f;
}
int n, m, tot, top, t, cnt;
ll ans = 0;
int to[M], Next[M], Head[N], edge[M], fr[M];
int f[N], in[N];
bool vis[N];
int dfn[N], low[N], s[N], col[N], sz[N];
void add(int u, int v, int w){
	to[++tot] = v, fr[tot] = u, Next[tot] = Head[u], Head[u] = tot, edge[tot] = w;
}
void tarjan(int x){
	dfn[x] = low[x] = ++t, s[++top] = x, vis[x] = 1;
	for(int i = Head[x]; i; i = Next[i]){
		int y = to[i]; 
		if(!dfn[y]) tarjan(y), low[x] = min(low[x], low[y]);
		else if(vis[y]) low[x] = min(low[x], dfn[y]);
 	} 
 	if(dfn[x] == low[x]){
 		int k = -1; ++cnt;
 		while(k != x){
 			k = s[top--], ++sz[cnt], vis[k] = 0, col[k] = cnt;
		}
	}
}
int main(){
//	freopen("1.in","r",stdin);
	n = read(), m = read();
	for(int i = 1; i <= m; ++i){
		int opt = read(), x = read(), y = read();
		if(opt == 1) add(x, y, 0), add(y, x, 0);
		else if(opt == 2) add(x, y, 1);
		else if(opt == 3) add(y, x, 0);
		else if(opt == 4) add(y, x, 1);
		else add(x, y, 0);
	}
	for(int i = 1; i <= n; ++i) add(0, i, 1);
	for(int i = 0; i <= n; ++i) if(!dfn[i]) tarjan(i);
	m = tot; memset(Head, 0, sizeof(Head)); tot = 0;
	for(int i = 1; i <= m; ++i){
		int x = col[fr[i]], y = col[to[i]];
		if(x == y && edge[i]) return printf("-1\n"), 0;
		if(x != y) add(x, y, edge[i]), ++in[y];
	}
	queue<int> q;
	for(int i = 1; i <= cnt; ++i) if(!in[i]) q.push(i);
	while(!q.empty()){
		int x = q.front(); q.pop(); 
		for(int i = Head[x]; i; i = Next[i]){
			int y = to[i]; --in[y];
			f[y] = max(f[y], f[x] + edge[i]);
			if(!in[y]) q.push(y);
		}
	}
	for(int i = 1; i <= cnt; ++i) ans += 1ll * f[i] * sz[i];
	printf("%lld\n", ans);
	return 0;
}

3.4 P3530 [POI2012]FES-Festival

将关系转为差分约束的限制，发现是稠密图，考虑使用 Floyd , \(n^3\) 剪枝一下还是能过的。

还是要 Tarjan 缩点，然后考虑无解的情况：

  1. 如果是负环，那么肯定无解，判定条件 : \(dis[i][i] < 0\)。

  2. 零环显然可以

  3. 如果对于正环，可以发现如果全是 1 的话 才是无解，因为在建 \(m1\) 的边时，有正反边权，那么 全是 1 的正环 其实也是全是 -1 的负环，如果环中没有为 0 的边，其实如果任意方向权值和不为0，一定无解，因为反一下就有正负环，而有 0 边 的话，可以限制方向，如果与大多数的 边权为1 的边相同的话，那么就有解，因为无法反转了，被 0 这条单向边限定死了，否则无解。

其实说了那么多，其实就只要判负环就可以了。

那最后的答案呢？其实就是各个强连通分量内的最长路之和 + 强连通分量数之和。为什么可以这样呢？因为各个强连通分量如果有连接的话，必然是 0 边，因为 1 和 -1 是配套，方向相反，那如果不是 0 边，其实两个强连通分量是在同一个强连通分量内的，不符合。那这样两个强连通分量之间就可以无限拉长，就可以分开来考虑。按照差分约束算法，从一个点 \(x_a\) 到另一个点 \(x_b\) 的最短路代表 \(x_b - x_a\) 的最大值，并考虑到边权只有 \(\{ 1,-1,0\}\) 三种，可以得到结论： 一个强连通分量内的最多取值个数等于强连通分量两两之间最短路的最大值

证明：

强连通分量两两之间最短路的最大值就代表 \(x_b - x_a\) 最大的值，即值域跨度最大，那在路径上，值要么 +1, 要么 -1 ,要么 0 （不变） ,那么显然能将 \([x_a,x_b]\) 之间的数都取一遍，那值域可以再大一些吗？显然不行，不然违反了两两之间最短路的最大值的定义。因为将 \(a\) 逆方向移动一下都会使值变大， 将 \(b\) 顺方向移动一下会使值变小，都会使得值域变小，显然不优，好好想一下吧，有些情况是无解，反正这样一定是最优的。

画一下图可以发现，这样的 \(a\), \(b\) 一定出现在边的临界点，而且最短路其实就是最长路，因为\(a \sim b\)路径值只可能有一种值。

证毕。

后记：一直以为自己懂了，直到写题解时才发现自己可能没有真的理解，这道题还有好多值得探究的问题，有些我可能讲不明白，讲起来还可能有点繁琐，没有图不是很直观，而且我也不想画了，那就这样吧，至少我知道了（bushi）。

#include<bits/stdc++.h>
#define N 605
#define M 200005 
#define INF 0x3f3f3f3f
using namespace std;
int read(){
	int x = 0, f = 1; char ch = getchar();
	while(ch < '0' || ch > '9'){if(ch == '-') f = -f; ch = getchar();}
	while(ch >= '0' && ch <= '9'){x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar();}
	return x * f;
}
int n, m1, m2, tot, t, top, scc, sum;
int Head[N], Next[M], to[M], edge[M];
int low[N], dfn[N], s[N], col[N], sz[N];
bool vis[N];
int dis[N][N], ans[N];
void add(int u, int v, int w){
	to[++tot] = v, Next[tot] = Head[u], Head[u] = tot, edge[tot] = w; 
}
void tarjan(int x){
	dfn[x] = low[x] = ++t, vis[x] = 1, s[++top] = x;
	for(int i = Head[x]; i; i = Next[i]){
		int y = to[i];
		if(!dfn[y]) tarjan(y), low[x] = min(low[x], low[y]);
		else if(vis[y]) low[x] = min(low[x], dfn[y]);
	}
	if(low[x] == dfn[x]){
		int k = -1; ++scc;
		while(k != x){
			k = s[top--], vis[k] = 0, ++sz[scc], col[k] = scc;
		} 
	}
}
int main(){
	n = read(), m1 = read(), m2 = read();
	memset(dis, 0x3f, sizeof(dis));
	for(int i = 1; i <= m1; ++i){
		int u = read(), v = read();
		dis[u][v] = 1, dis[v][u] = -1;
		add(u, v, 1), add(v, u, -1);
	}
	for(int i = 1; i <= m2; ++i){
		int u = read(), v = read();
		if(dis[v][u] == INF) dis[v][u] = 0;
		add(v, u, 0);
	} 
	for(int i = 1; i <= n; ++i){
		dis[i][i] = 0;
		if(!dfn[i]) tarjan(i);
	}
	for(int k = 1; k <= n; ++k){
		for(int i = 1; i <= n; ++i){
			if(col[i] != col[k] || dis[i][k] == INF) continue;
			for(int j = 1; j <= n; ++j){
				if(col[i] != col[j]) continue;
				dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
			}
		}
	}
	for(int i = 1; i <= n; ++i){
		if(dis[i][i] < 0) return printf("NIE\n"), 0;
		for(int j = 1; j <= n; ++j){
			if(col[i] == col[j]) ans[col[i]] = max(ans[col[i]], dis[i][j] + 1);
		}
	}
	for(int i = 1; i <= scc; ++i) sum += ans[i];
	printf("%d\n", sum);
	return 0;
}

参考资料： OI WiKi，初级图论，

标签：ch,int,笔记,约束,ge,le,差分,dis
From： https://www.cnblogs.com/jiangchenyyds/p/17417612.html

相关文章

  • 《程序员修炼之道--从小工到专家》阅读笔记01
    《程序员修炼之道–从小工到专家》是一本经典的软件开发实践指南书籍，被许多程序员视为进阶必读之书。以下是本人对该书第一章节的阅读笔记。第一章节题为：为什么需要修炼？显然，程序员和武林中的武功修炼者一样，都需要经过长期的学习、训练和实践，才能成为真正的专家。而与武术不同的是......
  • es笔记七之聚合操作之桶聚合和矩阵聚合
    本文首发于公众号：Hunter后端原文链接：es笔记七之聚合操作之桶聚合和矩阵聚合桶(bucket)聚合并不像指标(metric)聚合一样在字段上计算，而是会创建数据的桶，我们可以理解为分组，根据某个字段进行分组，将符合条件的数据分到同一个组里。桶聚合可以有子聚合，意思就是在分组之后，可以在每......
  • es笔记三之term，match，match_phrase 等查询方法介绍
    本文首发于公众号：Hunter后端原文链接：es笔记三之term，match，match_phrase等查询方法介绍首先介绍一下在es里有两种存储字符串的字段类型，一个是keyword，一个是text。keyword在存储数据的时候是作为一个整体存储的，不会对其进行分词处理text存储数据的时候会对字符串进行分......
  • babylon.js 学习笔记(3)
    一、理解babylon.js坐标系constcreateScene=function(){constscene=newBABYLON.Scene(engine);constcamera=newBABYLON.ArcRotateCamera("camera",-Math.PI/2,Math.PI/2.5,3,newBABYLON.Vector3(0,0,0));camera.attachControl......
  • 碧圈异步交易平台AsyncAlgoTrading学习笔记一：下载与编译
    下载无exe或Linux二进制，需源码编译安装GitHub地址：https://github.com/AsyncAlgoTrading/aat.git编译运行环境ubuntu20.04python3.8.10编译1.将Makefile中的PYTHON=python改为PYTHON=python32.安装必要的依赖：（1）sudoapt-getinstallpython3-dev（2）sudoapt-getinstallbui......
  • DAY10笔记及补充
    今日默写：1.创建数组的两种方式2.给数组赋值的两种方式3.for循环遍历数组4.描述下运算符的种类，并分别用代码展示下各自的使用方式5.if单分支，多分支各自的展示形式6.switch的使用方式得分：90补充：1.javascript变量可以由字母、数字、下划线以及美元符号组成，但是不能以数字开头2.j......
  • HD工作笔记
    1、相机标定步骤1.1棋盘标定相机思路1、建立终止准则：criteria=(cv2.TERM_CRITERIA_EPS+cv2.TERM_CRITERIA_MAX_ITER,30,0.001)#格式固定2、设置棋盘格规格 objp=np.zeros((w*h,3),np.float32)#w:棋盘宽度方向上的角点数，h:棋盘高度方......
  • 软构笔记-7-面向对象的编程
    目录软构7基本概念Interface在interface中使用default方法继承与重写重写AbstractClass抽象类Polymorphism,subtypingandoverloading多态、子类型、重载三种多态Overloading重载重载的规则Overridingvs.Overloading子类型多态继承和子类型：层次结构一瞥软构7本章......
  • 软构笔记-8-ADT和OOP中的“等价性”
    目录软构8ADT的等价操作不可变数据类型的等价性==vs.equals()可变数据类型的等价性软构8本章大纲：理解特性之间的等价关系站在观察者角度，利用AF，定义不可变对象之间的等价关系引用等价性和对象等价性可变数据类型的观察等价性和行为等价性理解Object的契约，正确实现等......
  • 软构笔记-9-面向复用的软件构造技术
    目录软构9面向复用的软件构造技术源代码复用模块级别的复用class/interfaceclass的复用在OOP中设计复用类子类型多态LSP原则协变反协变、逆变软构9面向复用的软件构造技术本章大纲：软件复用的优缺点为复用而construct通用可复用组件的特征开发便携式应用系统的方法可复......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99