本文共 1213 字，大约阅读时间需要 4 分钟。
题意：有n个点，m条单向边，每个机器人能沿着单向边走，能重复经过一个点，问最少几个机器人走遍n个点
思路：原来以前学的都是不能相交的算法....可相交的做法是跑Floyd把能到达的都加上边，然后跑最小覆盖
代码：
#include #include #include #include #include #include #include #include #include #include #include #include typedef long long ll;using namespace std;const int maxn = 500 + 10;const int MOD = 1e9 + 7;const int INF = 0x3f3f3f3f;int linker[maxn], n, m;int g[maxn][maxn];bool used[maxn];bool dfs(int u){ for(int v = 1; v <= n; v++){ if(g[u][v] && !used[v]){ used[v] = true; if(linker[v] == -1 || dfs(linker[v])){ linker[v] = u; return true; } } } return false;}int hungry(){ int res = 0; memset(linker, -1, sizeof(linker)); for(int u = 1; u <= n; u++){ memset(used, false, sizeof(used)); if(dfs(u)) res++; } return res;}void floyd(){ for(int k = 1; k <= n; k++){ for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ if(g[i][k] && g[k][j]) g[i][j] = 1; } } }}int main(){ while(~scanf("%d%d", &n, &m) && n + m){ memset(g, 0, sizeof(g)); while(m--){ int u, v; scanf("%d%d", &u, &v); g[u][v] = 1; } floyd(); printf("%d\n", n - hungry()); } return 0;}
转载于:https://www.cnblogs.com/KirinSB/p/10472998.html