本文主要是介绍[Usaco2015 Jan]Grass Cownoisseur 图论 tarjan spfa，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
先缩点，对于缩点后的DAG，正反跑spfa，枚举每条边进行翻转即可
#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
using namespace std;
struct pp{struct edge{int u,v,w,next;}ed[200005];int e,head[100005];pp(){e=1;memset(head,0,sizeof head);}void add(int u,int v,int w){ed[e].u=u; ed[e].v=v; ed[e].w=w;ed[e].next=head[u]; head[u]=e++;}
};pp orgp,newp,newf;
int dfn[100005],low[100005],q[100005];
int top=0,tot=0,id[100005],size[100005];
bool bo[100005];void tarjan(int x){dfn[x]=low[x]=++top;q[top]=x; bo[x]=1;for(int i=orgp.head[x];i;i=orgp.ed[i].next){int v=orgp.ed[i].v;if(!dfn[v]){tarjan(v);low[x]=min(low[x],low[v]);}else if(bo[v])low[x]=min(low[x],dfn[v]);}if(dfn[x]==low[x]){int y; tot++;do{y=q[top--];bo[y]=0;id[y]=tot;size[tot]++;}while(y!=x);}
}int dis[100005][2];void spfa(pp &ppp,int x,int t){memset(bo,0,sizeof bo);queue<int > q; q.push(x); dis[x][t]=size[x]; int now,v,w;while(!q.empty()){now=q.front(); q.pop(); bo[now]=0;for(int i=ppp.head[now];i;i=ppp.ed[i].next){v=ppp.ed[i].v; w=ppp.ed[i].w;if(dis[v][t]<dis[now][t]+w){dis[v][t]=dis[now][t]+w;if(!bo[v]){bo[v]=1;q.push(v);}}}}
}int n,m;int main()
{//freopen("cown.in","r",stdin);//freopen("cown.out","w",stdout);scanf("%d%d",&n,&m);int u,v;for(int i=1;i<=m;i++){scanf("%d%d",&u,&v);orgp.add(u,v,1);}for(int i=1;i<=n;i++)if(!dfn[i])tarjan(i);for(int i=1;i<=m;i++){if(id[orgp.ed[i].u]!=id[orgp.ed[i].v]){newp.add(id[orgp.ed[i].u],id[orgp.ed[i].v],size[id[orgp.ed[i].v]]);newf.add(id[orgp.ed[i].v],id[orgp.ed[i].u],size[id[orgp.ed[i].u]]);}}int ans=-0x7fffffff;memset(dis,-0x3f,sizeof dis);spfa(newp,id[1],0);spfa(newf,id[1],1);for(int i=1;i<newp.e;i++){u=newp.ed[i].u;v=newp.ed[i].v;ans=max(ans,dis[u][1]+dis[v][0]-size[id[1]]);}printf("%d\n",ans);
}这篇关于[Usaco2015 Jan]Grass Cownoisseur 图论 tarjan spfa的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
