[BZOJ3887][Usaco2015 Jan]Grass Cownoisseur（tarjan+spfa）

Jan]Grass Cownoisseur（tarjan+spfa）"/>

[BZOJ3887][Usaco2015 Jan]Grass Cownoisseur（tarjan+spfa）

题目描述

传送门

题解

边是可以重复走的，所以在同一个强连通分量里，无论从那个点进入从哪个点出，所有的点一定能被一条路走到。
那么首先用tarjan将所有的强连通分量缩成一个点，每个点的权为该强连通分量中点的个数。然后我们考虑将一条边反置。
强连通分量里的边反置是没有价值的，所以只需要考虑DAG里的边。枚举一条要反置的边，如果将这条边反置的话，答案应该为它的起点到1最多能走到的点数和1到它的终点最多能走到的点数，也就是相当于这条边将一个环连通起来了。而从它到1最多能走到的点数和1到它的终点最多能走到的点数可以用两遍spfa最长路预处理好，这个问题就被解决了。

代码

#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
using namespace std;
#define N 100005int n,m,dfs_clock,scc,ans;
struct hp{int x,y;}e[N];
int dfn[N],low[N],stack[N],tmp,belong[N],size[N],dis[N],_dis[N];
int tot,point[N],nxt[N],v[N];
bool vis[N];
queue <int> q;void add(int x,int y)
{++tot; nxt[tot]=point[x]; point[x]=tot; v[tot]=y;
}
void tarjan(int x)
{dfn[x]=low[x]=++dfs_clock;vis[x]=true;stack[++tmp]=x;for (int i=point[x];i;i=nxt[i])if (!dfn[v[i]]){tarjan(v[i]);low[x]=min(low[x],low[v[i]]);}else if (vis[v[i]])low[x]=min(low[x],dfn[v[i]]);if (dfn[x]==low[x]){++scc;int now=0;while (now!=x){now=stack[tmp--];vis[now]=false;belong[now]=scc;size[scc]++;}}
}
void build()
{tot=0;memset(point,0,sizeof(point));for (int i=1;i<=m;++i)if (belong[e[i].x]!=belong[e[i].y])add(belong[e[i].x],belong[e[i].y]);
}
void rebuild()
{tot=0;memset(point,0,sizeof(point));for (int i=1;i<=m;++i)if (belong[e[i].x]!=belong[e[i].y])add(belong[e[i].y],belong[e[i].x]);
}
void spfa(int *dis)
{memset(vis,0,sizeof(vis));dis[belong[1]]=size[belong[1]];vis[belong[1]]=true;q.push(belong[1]);while (!q.empty()){int now=q.front();q.pop();vis[now]=false;for (int i=point[now];i;i=nxt[i])if (dis[v[i]]<dis[now]+size[v[i]]){dis[v[i]]=dis[now]+size[v[i]];if (!vis[v[i]]){vis[v[i]]=true;q.push(v[i]);}}}
}
int main()
{scanf("%d%d",&n,&m);for (int i=1;i<=m;++i){scanf("%d%d",&e[i].x,&e[i].y);add(e[i].x,e[i].y);}for (int i=1;i<=n;++i)if (!dfn[i]) tarjan(i);build();spfa(dis);rebuild();spfa(_dis);ans=size[belong[1]];for (int i=1;i<=m;++i)if (belong[e[i].x]!=belong[e[i].y])if (_dis[belong[e[i].x]]&&dis[belong[e[i].y]])ans=max(ans,_dis[belong[e[i].x]]+dis[belong[e[i].y]]-size[belong[1]]);printf("%d\n",ans);
}

总结

①一定要好好读题！希望以后不要再有读题方面的失误。