1 条题解
-
1
#include<bits/stdc++.h> using namespace std; #define int long long int s, n, m; const int maxn = 205; int cnt, hd[maxn]; struct node{ int to, nxt; }e[305]; struct node2{ int lin[maxn][5], out[maxn]; }a[maxn]; int dfn[maxn], low[maxn], siz[maxn], co[maxn], st[maxn]; int tmp, top, col; int flag, vis[maxn][maxn]; int u[305], v[305], ans[maxn]; void add (int u, int v) { e[++cnt].to = v; e[cnt].nxt = hd[u]; hd[u] = cnt; } void input () { scanf ("%lld", &s); for (int i = 1; i <= s; i++) { scanf ("%lld %lld", &n, &m); for (int j = 1; j <= m; j++) { int t; scanf ("%lld", &t); t++; a[i].out[t] = 1; } for (int l = 1; l <= n; l++) { int aa, bb; scanf ("%lld %lld", &aa, &bb); aa++, bb++; a[i].lin[l][0] = aa, a[i].lin[l][1] = bb; } } } void find (int x, int y, int nx, int ny) { if (a[x].out[nx] == 1 and a[y].out[ny] == 0) { flag = 1; return; } if (vis[nx][ny]) return; vis[nx][ny] = 1; find (x, y, a[x].lin[nx][0], a[y].lin[ny][0]); find (x, y, a[x].lin[nx][1], a[y].lin[ny][1]); } void build () { for (int i = 1; i <= s; i++) { for (int j = 1; j <= s; j++) { if (i == j) continue; flag = 0, memset (vis, 0, sizeof vis); find (i, j, 1, 1); if (!flag) add (i, j), u[cnt] = i, v[cnt] = j; } } } void tarjan (int u) { dfn[u] = low[u] = ++tmp; st[++top] = u; for (int i = hd[u]; i; i = e[i].nxt) { int v = e[i].to; if (!dfn[v]) { tarjan (v); low[u] = min (low[u], low[v]); } else if (!co[v]) low[u] = min (low[u], dfn[v]); } if (dfn[u] == low[u]) { co[u] = ++col; siz[col] = 1; while (st[top] != u) { co[st[top]] = col; siz[col]++; top--; } top--; } } void rebuild () { for (int i = 1; i <= s; i++) if (!dfn[i]) tarjan (i); int recoc = cnt; cnt = 0; memset (hd, 0, sizeof hd); memset (e, 0, sizeof e); for (int i = 1; i <= recoc; i++) { if (co[u[i]] == co[v[i]]) continue; add (co[u[i]], co[v[i]]); } } int get (int u) { if (ans[u]) return ans[u]; ans[u] = siz[u]; for (int i = hd[u]; i; i = e[i].nxt) { int v = e[i].to; ans[u] = max (ans[u], get (v) + siz[u]); } return ans[u]; } void output () { int anss = 0; for (int i = 1; i <= col; i++) if (!ans[i]) anss = max (anss, get (i)); printf ("%lld\n", anss); } signed main () { input (); build (); rebuild (); output (); return 0; }
- 1
信息
- ID
- 1272
- 时间
- 1000ms
- 内存
- 125MiB
- 难度
- 6
- 标签
- 递交数
- 1
- 已通过
- 0
- 上传者