题目链接
https://nanti.jisuanke.com/t/19979
题意
给出n个点 m 条边 求选出最大的点数使得这个点集之间 任意两点不可达 题目中给的边是有向边
思路
这道题 实际上是求 二分图的最大独立集
二分图的最大独立集 = 顶点数 - 二分图最大匹配
相关概念： https://blog.csdn.net/whosemario/article/details/8513836
那操作就是
先Flyod 跑出 可达矩阵 再二分匹配
答案就是 n - res
AC代码
#pragma comment(linker, "/STACK:102400000,102400000") #include <cstdio> #include <cstring> #include <ctype.h> #include <cstdlib> #include <cmath> #include <climits> #include <ctime> #include <iostream> #include <algorithm> #include <deque> #include <vector> #include <queue> #include <string> #include <map> #include <stack> #include <set> #include <list> #include <numeric> #include <sstream> #include <iomanip> #include <limits> #define pb push_back #define fi first #define se second #define L(on) ((on)<<1) #define R(on) (L(on) | 1) #define mkp(a, b) make_pair(a, b) #define bug puts("***bug***"); #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define CLR(a, b) memset(a, (b), sizeof(a)); #define syn_close ios::sync_with_stdio(false); cin.tie(0); #define sp system("pause"); //#define gets gets_s using namespace std; typedef long long ll; typedef long double ld; typedef long double ld; typedef unsigned long long ull; typedef pair <int, int> pii; typedef pair <double, double> pdd; typedef pair <ll, ll> pll; typedef vector <int> vi; typedef vector <ll> vll; typedef vector < vi > vvi; const double PI = acos(-1.0); const double EI = exp(1.0); const double eps = 1e-8; inline int read() { char c = getchar(); int ans = 0, vis = 1; while (c < '0' || c > '9') { if (c == '-') vis = -vis; c = getchar(); } while (c >= '0' && c <= '9') { ans = ans * 10 + c - '0'; c = getchar(); } return ans * vis; } const int INF = 0x3f3f3f3f; const ll INFLL = 0x3f3f3f3f3f3f3f3fll; const int maxn = (int)1e2 + 10; const int MAXN = (int)1e4 + 10; const ll MOD = (ll)1e9 + 7; int G[maxn][maxn]; int n, m; void input() { n = read(), m = read(); for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) G[i][j] = 0; int x, y; for (int i = 0; i < m; i++) { x = read() - 1, y = read() - 1; G[x][y] = 1; } } void Floyd() { for (int k = 0; k < n; k++) for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) G[i][j] = (G[i][j] || G[i][k] && G[k][j]); } int uN, vN; int linker[maxn]; bool used[maxn]; bool dfs(int u) { for (int v = 0; v < vN; 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 hungary() { int res = 0; CLR(linker, -1); for (int u = 0; u < uN; u++) { CLR(used, false); if (dfs(u)) res++; } return res; } void solve() { Floyd(); uN = vN = n; printf("%d\n", n - hungary()); } int main() { int t = read(); while (t--) { input(); solve(); } }转载于:https://www.cnblogs.com/Dup4/p/9433060.html
相关资源：JAVA上百实例源码以及开源项目