Creator's World

一、简介

从数学上来说，传递闭包是在集合 $S$ 中求包含关系 $X$ 的最小传递关系。从图的角度来说，就是如果原图上有 $i$ 到 $j$ 的路径，则其传递闭包的图上就应有从 $i$ 到 $j$ 的边。简单来说，就是确定每个点是否能到达其他每个点。

二、算法

传递闭包就是用 floyd 来求的。

三、代码

for(int k = 1; k <= n; k++)
	for(int i = 1; i <= n; i++)
		for(int j = 1; j <= n; j++)
			if(e[i][k] && e[k][j])
				e[i][j] = true;

四、例题

POJ1975 Median Weight Bead

我们可以将水滴看作点，若 $w_i>w_j$ 则在 $i$ 和 $j$ 之间连边，那么接下来就是跑 floyd，然后计算每个点比几个点大，比几个点小，若有一个值大于 $\frac{n}{2}$ 则答案加一。

#include<cstdio>
#include<cstring>
using namespace std;
typedef long long ll;

inline ll read() {
	ll sum = 0, ff = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9') {
		if(ch == '-')
			ff = -1;
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9')
		sum = sum * 10 + ch - '0', ch = getchar();
	return sum * ff;
}

void write(ll x) {
	if(x < 0)
		putchar('-'), x = -x;
	if(x > 9)
		write(x / 10);
	putchar(x % 10 + '0');
}

const int N = 107;
int t, n, m;
bool vis[N][N];
int ans;
 
int main() {
//	freopen("", "r", stdin);
//	freopen("", "w", stdout);
	t = read();
	while(t--) {
		memset(vis, false, sizeof(vis));
		ans = 0;
		n = read(), m = read();
		for(int i = 1; i <= m; i++) {
			int u = read(), v = read();
			vis[u][v] = true;
		}
		for(int k = 1; k <= n; k++)
			for(int i = 1; i <= n; i++)
				for(int j = 1; j <= n; j++)
					if(vis[i][k] && vis[k][j])	
						vis[i][j] = true;
		for(int i = 1; i <= n; i++) {
			int in = 0, out = 0;
			for(int j = 1; j <= n; j++) 
				in += vis[j][i], out += vis[i][j];
			ans += in > n / 2 || out > n / 2;
		}
		write(ans), puts("");
	}
	return 0;
}

P2419 [USACO08JAN]Cow Contest S

我们在奶牛之间建边，然后跑 floyd 判断两只奶牛间是否能决定关系，然后统计满足条件的答案即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

inline ll read() {
	ll sum = 0, ff = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9') {
		if(ch == '-')
			ff = -1;
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9')
		sum = sum * 10 + ch - '0', ch = getchar();
	return sum * ff;
}

void write(ll x) {
	if(x < 0)
		putchar('-'), x = -x;
	if(x > 9)
		write(x / 10);
	putchar(x % 10 + '0');
}

const int N = 1e2 + 7;
int n, m, sum, ans;
bool vis[N][N];

int main() {
//	freopen("", "r", stdin);
//	freopen("", "w", stdout);
	n = read(), m = read();
	for(int i = 1; i <= m; i++) {
		int u = read(), v = read();
		vis[u][v] = true;
	}
	for(int k = 1; k <= n; k++)
		for(int i = 1; i <= n; i++)
			for(int j = 1; j <= n; j++)
				if(vis[i][k] && vis[k][j])
					vis[i][j] = true;
	for(int i = 1; i <= n; i++) {
		sum = 0;
		for(int j = 1; j <= n; j++)
			sum += vis[i][j] + vis[j][i];
		ans += (sum == n - 1);
	}
	write(ans);
	return 0;
}