P3119 [USACO15JAN]草鉴定Grass Cownoisseur
题目描述
约翰有(n)块草场，编号1到(n)，这些草场由若干条单行道相连。奶牛贝西是美味牧草的鉴赏家，她想到达尽可能多的草场去品尝牧草。
贝西总是从1号草场出发，最后回到1号草场。她想经过尽可能多的草场，贝西在通一个草场只吃一次草，所以一个草场可以经过多次。因为草场是单行道连接，这给贝西的品鉴工作带来了很大的不便，贝西想偷偷逆向行走一次，但最多只能有一次逆行。问，贝西最多能吃到多少个草场的牧草。
输入输出格式
输入格式：
第一行：草场数(n)，道路数(m)。
以下(m)行，每行(x)和(y)表明有(x)到(y)的单向边，不会有重复的道路出现。
输出格式：
一个数，逆行一次最多可以走几个草场。
数据范围：
(1<=N,M<=100,000)
思路：先缩点，以新点的大小为点权，正反跑最长路，枚举每条边上的两个点更新答案。
需要注意的是，(dis)数组得先置(-inf)，因为(dis==0)表示不可以到，但它可能更新答案。就这个卡了我两个月直到今天一位洛谷群群友@ysj1173886760才告诉我原因真是万分感谢
Code:
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
const int N=100010;
int max(int x,int y){return x>y?x:y;}
int min(int x,int y){return x<y?x:y;}
struct Edge
{
int to,next;
}edge[N];
struct Edge0
{
int to,next,w;
}edge0[N<<1];
int head[N],cnt=0,head0[N],cnt0=0;
void add(int u,int v)
{
edge[++cnt].next=head[u];edge[cnt].to=v;head[u]=cnt;
}
void add0(int u,int v,int w)
{
edge0[++cnt0].next=head0[u];edge0[cnt0].to=v;edge0[cnt0].w=w;;head0[u]=cnt0;
}
int n,m;
int time=0,tot,s[N],dfn[N],is[N],low[N],ha[N],n0=0,siz[N],m_max=0,typ[N];
void tarjan(int now)
{
dfn[now]=low[now]=++time;
is[now]=1;
s[++tot]=now;
for(int i=head[now];i;i=edge[i].next)
{
int v=edge[i].to;
if(!dfn[v])
{
tarjan(v);
low[now]=min(low[now],low[v]);
}
else if(is[v])
low[now]=min(low[now],dfn[v]);
}
if(dfn[now]==low[now])
{
int k;n0++;
do
{
k=s[tot--];
siz[n0]++;
is[k]=0;
ha[k]=n0;
}while(k!=now);
}
}
queue <int > q;
int used[N],dis[N];
void spfa(int ty)
{
q.push(ha[1]);
memset(used,0,sizeof(used));
while(!q.empty())
{
int u=q.front();
q.pop();
used[u]=0;
for(int i=head0[u];i;i=edge0[i].next)
{
int v=edge0[i].to,w=edge0[i].w;
if(w!=ty) continue;
if(dis[v]<dis[u]+siz[v])
{
dis[v]=dis[u]+siz[v];
if(!used[v])
{
used[v]=1;
typ[v]=ty;
q.push(v);
}
}
}
}
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
{
int u,v;
scanf("%d%d",&u,&v);
add(u,v);
}
for(int i=1;i<=n;i++)
if(!dfn[i])
tarjan(i);
for(int i=1;i<=n;i++)
for(int j=head[i];j;j=edge[j].next)
{
int v=edge[j].to;
if(ha[i]!=ha[v])
{
add0(ha[i],ha[v],1);
add0(ha[v],ha[i],0);
}
}
memset(dis,-0x3f,sizeof(dis));
dis[ha[1]]=0;
spfa(1);
spfa(0);
for(int i=1;i<=n0;i++)
if(ha[1]!=i)
for(int j=head0[i];j;j=edge0[j].next)
{
int v=edge0[j].to,w=edge0[j].w;
if((typ[i]^typ[v]||ha[1]==v)&&typ[i]^w)
m_max=max(m_max,dis[i]+dis[v]);
}
printf("%d
",m_max+siz[ha[1]]);
return 0;
}
2018.7.26