bzoj3887luogu3119
题目描述：John有n块草场，有m条单向道路j连接。Bessie从1号草场出发，最后回到1号操场。Bessie想要经过若干个草场，她想要经过尽可能多的草场。Bessie只可以逆行一次，求最多的草场数。
输入格式：第一行，两个整数n和m。 接下来m行，每行两个整数，表示两个相连的点。
输出格式：一行一个整数，表示最多的草场数。
输入样例： 7 10 1 2 3 1 2 5 2 4 3 7 3 5 3 6 6 5 7 2 4 7
输出样例： 6
解析：很明显可以可以用tarjan将所有的环缩在一起。 用co[i]表示i点所在的强连通分量，size[i]表示第i个强连通分量中点的个数。 再进行两次spfa，求出1号草场到该点所经过的最多点数dis1[i]和该点到1号草场所经过的最多点数dis2[i]。 枚举每个点作为逆行的店，那么ans = max(ans, dis1[co[i]] + dis2[j] - size[co[1]])，其中j与co[i]相连。 注意ans的初值为size[co[1]]，并且答案只有在dis1[i] > 0并且dis2[i] > 0时才可以统计。
代码如下：
#include<cstdio> #include<algorithm> using namespace std; const int maxn = 1e5 + 5; int n, m, size[maxn], que[maxn << 2], dis1[maxn], dis2[maxn], vis[maxn], ans; int hed1[maxn << 1], nxt1[maxn << 1], to1[maxn << 1], cnt1; int hed2[maxn << 1], nxt2[maxn << 1], to2[maxn << 1], cnt2; int hed3[maxn << 1], nxt3[maxn << 1], to3[maxn << 1], cnt3; int dfn[maxn], low[maxn], num, st[maxn], top, col, co[maxn]; int read(void) { char c; while (c = getchar(), c < '0' || c > '9'); int x = c - '0'; while (c = getchar(), c >= '0' && c <= '9') x = x * 10 + c - '0'; return x; } void add1(int x, int y) { nxt1[++ cnt1] = hed1[x]; hed1[x] = cnt1; to1[cnt1] = y; } void add2(int x, int y) { nxt2[++ cnt2] = hed2[x]; hed2[x] = cnt2; to2[cnt2] = y; } void add3(int x, int y) { nxt3[++ cnt3] = hed3[x]; hed3[x] = cnt3; to3[cnt3] = y; } void tarjan(int u) { //缩点 dfn[u] = low[u] = ++ num; st[++ top] = u; for (int i = hed1[u]; i ; i = nxt1[i]) { int v = to1[i]; 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]) { ++ col; co[u] = col; while (st[top] != u) { co[st[top]] = col; top --; } top --; } } void spfa1(void) { int h = 0, t = 1; que[t] = co[1]; for (int i = 1; i <= n; ++ i) dis1[co[i]] = 0, vis[co[i]] = 0; dis1[co[1]] = size[co[1]]; vis[co[1]] = 1; while (h ^ t) { int u = que[++ h]; vis[u] = 0; for (int i = hed2[u]; i ; i = nxt2[i]) { int v = to2[i]; if (dis1[v] < dis1[u] + size[v]) { dis1[v] = dis1[u] + size[v]; if (!vis[v]) { vis[v] = 1; que[++ t] = v; } } } } } void spfa2(void) { int h = 0, t = 1; que[t] = co[1]; for (int i = 1; i <= n; ++ i) dis2[co[i]] = 0, vis[co[i]] = 0; dis2[co[1]] = size[co[1]]; vis[co[1]] = 1; while (h ^ t) { int u = que[++ h]; vis[u] = 0; for (int i = hed3[u]; i ; i = nxt3[i]) { int v = to3[i]; if (dis2[v] < dis2[u] + size[v]) { dis2[v] = dis2[u] + size[v]; if (!vis[v]) { vis[v] = 1; que[++ t] = v; } } } } } int main() { n = read(); m = read(); for (int i = 1; i <= m; ++ i) { int x = read(), y = read(); add1(x, y); } for (int i = 1; i <= n; ++ i) if (!dfn[i]) tarjan(i); for (int i = 1; i <= n; ++ i) for (int j = hed1[i]; j ; j = nxt1[j]) { int v = to1[j]; if (co[i] == co[v]) continue; add2(co[i], co[v]); add3(co[v], co[i]); } for (int i = 1; i <= n; ++ i) size[co[i]] ++; spfa1(); spfa2(); ans = size[co[1]]; for (int i = 1; i <= n; ++ i) for (int j = hed3[co[i]]; j ; j = nxt3[j]) if (dis1[co[i]] > 0 && dis2[to3[j]] > 0) ans = max(ans, dis1[co[i]] + dis2[to3[j]] - size[co[1]]); printf("%d", ans); return 0; }转载于:https://www.cnblogs.com/Gaxc/p/9978161.html
相关资源：JAVA上百实例源码以及开源项目