题面:洛谷P3119 Grass Cownoisseur G
本人最近在熟悉Tarjan的题,刷了几道蓝题后,我飘了
趾高气扬地点开这道紫题,我一瞅:
哎呦!这不是分层图吗?
突然就更飘了~~~
用时20min写了一个分层图+bfs上去,却看到了一片红......
我:????
苦(查)思(看)冥(题)想(解)后,我恍然大悟
我好像忘了比较大小了(→_→)
改了改,提交上去,果然A了~~~
下面进入正题:
大约的问题就是:已知有n个点,m条有向边,问从1点出发,最后回到1点,可以逆行一次,最多能到达几个点?(每个点可以经过多次)
(语文不好请别介意)
这个题如果只是从1点出发,最多能到几个点最后回到1点的话,那一个bfs就解决了
但是,既然有逆行一次,我们可以再建一层图当做是分层图中的一次优惠来做(具体可以看我的上一篇文)
然后用spfa(或bfs)通过tarjan缩点来维护点权
好,既然这样,这个题的解法大概就出来了:
分层图+tarjan+bfs(spfa)
下面上伪代码:
for (int i = 1; i <= n; i++){ for (int j = head[i]; j; j = e[j].nxt){//遍历边 v = e[j].v; if (num[i] != num[v]){//判断这个边缩点后是否存在 add(num[i], num[v]); add(num[v], num[i] + g);//将上一层v点与下一层u连接 add(num[i] + g, num[v] + g); }//建分层图 } }
假如有一条通过tarjan缩点后依然存在的边:从u点到v点
然后建分层图,将上一层的v点连接到下一点的u点(模拟逆行)
然后求从第一层的1点到第二层的1点最多经过多少个点
完整代码:
#include <cstdio> #include <iostream> #include <cstring> #include <cmath> #include <queue> #define MAXN 2000010 using namespace std; int vis[MAXN], head[MAXN], hed[MAXN], jl[MAXN]={0}; int js=0, n, m, op=0, cnt=0; int sta[MAXN], low[MAXN], dfn[MAXN], top=0; int num[MAXN], sum[MAXN], g=0, oq=0; struct edge{//建两个图,一个用来存缩点前的图,一个用来存缩点后的图 int v, nxt; }e[MAXN << 1], ed[MAXN << 1]; void addage(int u, int v){ e[++js].v = v; e[js].nxt = head[u]; head[u] = js; }//对缩点前的图进行加边 void add(int u, int v){ ed[++cnt].v = v; ed[cnt].nxt = hed[u]; hed[u] = cnt; }//对缩点后的图进行加边 void tarjan(int t){//用tarjan进行缩点(板子) sta[++top] = t; vis[t] = 1; low[t] = dfn[t] = ++op; for (int j = head[t]; j; j = e[j].nxt){ int v = e[j].v; if (!dfn[v]){ tarjan(v); low[t] = min (low[t], low[v]); } else if (vis[v]) low[t] = min (low[t], low[v]); } if (low[t] == dfn[t]){ int f = sta[top--]; vis[f] = 0; num[f] = ++g; sum[g]++; while (f != t){ f = sta[top--]; vis[f] = 0; num[f] = g; sum[g]++; } } } void spfa()//或者bfs(反正怎么叫是自己的事( ̄y▽ ̄)~*捂嘴偷笑) { int k; queue<int> q; memset(jl, 0, sizeof(jl)); memset(vis, 0, sizeof(vis)); vis[num[1]] = 0; jl[num[1]] = 1; q.push(num[1]); while (!q.empty()){ k = q.front(); q.pop(); jl[k] = 0; for (int i = hed[k]; i; i = ed[i].nxt) if (vis[ed[i].v] < vis[k] + sum[ed[i].v])//注意这里,sum[]存的是一个强连通分量中有几个点 { vis[ed[i].v] = vis[k] + sum[ed[i].v];//把sum[]当做点权来使用 if (!jl[ed[i].v]) { q.push(ed[i].v); jl[ed[i].v] = 1; } } } } int main(){ int x, y, v, ans=0, jss=0,mm; scanf("%d %d", &n, &m); for (int i = 1; i <= m; i++){ scanf("%d %d", &x, &y); addage(x, y); } for (int i = 1; i <= n; i++) if (!dfn[i]) tarjan(i);//tarjan缩点 for (int i = 1; i <= n; i++){ for (int j = head[i]; j; j = e[j].nxt){ v = e[j].v; if (num[i] != num[v]){ add(num[i], num[v]); add(num[v], num[i] + g); add(num[i] + g, num[v] + g); }//建分层图 } } for (int i = 1 + g; i <= g + g; i++) sum[i] = sum[i - g];//注意这里,我一开始样例死活过不去就是忘了加这一句 spfa(); printf("%d\n",vis[num[1] + g]); return 0; }