NKOJ 3213 牧草鉴赏家（Tarjan缩点+最长路）

发表于 |
字数统计: 1,186字 | 阅读时长 ≈ 6min

P3213【USACO 2015 Jan Gold】牧草鉴赏家

问题描述

约翰有n块草场，编号1到n，这些草场由若干条单行道相连。奶牛贝西是美味牧草的鉴赏家，她想到达尽可能多的草场去品尝牧草。

贝西总是从1号草场出发，最后回到1号草场。她想经过尽可能多的草场，贝西在通一个草场只吃一次草，所以一个草场可以经过多次。因为草场是单行道连接，这给贝西的品鉴工作带来了很大的不便，贝西想偷偷逆向行走一次，但最多只能有一次逆行。问，贝西最多能吃到多少个草场的牧草。

输入格式

第一行，两个整数N和M(1<=N,M<=100000)
接下来M行，表示有M条单向道路，每条道路有连个整数X和Y表示，从X出发到达Y。

输出格式

一个整数，表示所求答案

样例输入

7 10
1 2
3 1
2 5
2 4
3 7
3 5
3 6
6 5
7 2
4 7

样例输出

6

首先显然用Tarjan缩点，变成DAG。
由于只用一条反向边，因此我们可以枚举这条反向边，那么路径是1->反向边起点->反向边终点->1
那么显然我们只需要算出1到每一个点经过的最多点数，和每一个点到1经过的最多点数。然后枚举讨论即可。

关于正确性，我们只需要证明除了1号点经过两次外，所有点都只会经过一次即可。那么，首先，我们把这个DAG中的路径分成两种，一种是以1为起点的，一种是以1为终点的，其他的不讨论。那么显然这两种边是不能重合的，而且反向边肯定是从以1为起点的路径连到以1为终点的路径上。故正确性得证。

关于求出上述的最多点数，我们用缩点后的图跑最长路，将终点的缩点前包含点数当成边权即可。正图+反图跑两遍即可。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<stack>
#include<queue>
#include<cstring>
#define N 123456
#define M 234567
using namespace std;
inline int _R()
{
	int t=getchar();int o;
	while(t<48||t>57)t=getchar();
	for(o=0;t>47&&t<58;t=getchar())o=o*10+t-48;
	return o;
}
int n,m,VT,scc,size[N],ans=-1e9;
int TOT,LA[N],NE[M],EN[M],ST[M];
int NTOT,NLA[N],NNE[M],NEN[M],NST[M];
int ntot,nla[N],nne[M],nen[M],nst[M];
int dis[N],dist[N],dfn[N],low[N],be[N];
bool mark[N],Mark[N];
stack<int>S;
queue<int>Q;
void ADD(int x,int y)
{
	TOT++;
	ST[TOT]=x;
	EN[TOT]=y;
	NE[TOT]=LA[x];
	LA[x]=TOT;
}
void NADD(int x,int y)
{
	NTOT++;
	NST[NTOT]=x;
	NEN[NTOT]=y;
	NNE[NTOT]=NLA[x];
	NLA[x]=NTOT;
}
void nadd(int x,int y)
{
	ntot++;
	nst[ntot]=x;
	nen[ntot]=y;
	nne[ntot]=nla[x];
	nla[x]=ntot;
}
void Tarjan(int u)
{
	int i,v;
	dfn[u]=low[u]=++VT;
	S.push(u);
	mark[u]=1;
	for(i=LA[u];i;i=NE[i])
	{
		v=EN[i];
		if(!dfn[v])
		{
			Tarjan(v);
			low[u]=min(low[u],low[v]);
		}
		else if(mark[v])low[u]=min(low[u],dfn[v]);
	}
	if(dfn[u]==low[u])
	{
		scc++;
		do{
			v=S.top();
			S.pop();
			mark[v]=0;
			be[v]=scc;
			size[scc]++;
		}while(u!=v);
	}
}
void SPFA(int s)
{
	int i,x,y;
	for(i=1;i<=n;i++)dis[i]=-1e9;
	Mark[s]=1;dis[s]=size[s];Q.push(s);
	while(!Q.empty())
	{
		x=Q.front();
		Q.pop();
		Mark[x]=0;
		for(i=nla[x];i;i=nne[i])
		{
			y=nen[i];
			if(dis[y]<dis[x]+size[y])
			{
				dis[y]=dis[x]+size[y];
				if(!Mark[y])Mark[y]=1,Q.push(y);
			}
		}
	}
}
void spfa(int s)
{
	int i,x,y;
	for(i=1;i<=n;i++)dist[i]=-1e9;
	Mark[s]=1;dist[s]=size[s];Q.push(s);
	while(!Q.empty())
	{
		x=Q.front();
		Q.pop();
		Mark[x]=0;
		for(i=NLA[x];i;i=NNE[i])
		{
			y=NEN[i];
			if(dist[y]<dist[x]+size[y])
			{
				dist[y]=dist[x]+size[y];
				if(!Mark[y])Mark[y]=1,Q.push(y);
			}
		}
	}
}
int main()
{
	int i,j,x,y;
	n=_R();m=_R();
	for(i=1;i<=m;i++)
	{
		x=_R();y=_R();
		ADD(x,y);
	}
	for(i=1;i<=n;i++)if(!dfn[i])Tarjan(i);
	for(i=1;i<=TOT;i++)
	{
		x=ST[i];y=EN[i];
		if(be[x]!=be[y])
		{
			NADD(be[x],be[y]);
			nadd(be[y],be[x]);
		}
	}
	SPFA(be[1]);
	spfa(be[1]);
	for(i=1;i<=ntot;i++)
	{
		x=nst[i];y=nen[i];
		if(dist[x]!=-1e9&&dis[y]!=-1e9)ans=max(ans,dist[x]+dis[y]-size[be[1]]);
	}
	cout<<ans;
}