题解 P3119 【[USACO15JAN]草鉴定Grass Cownoisseur】
wuzhoupei
2017-10-29 19:46:55
****
这道题显然要先 Tarjan 缩点预处理；
这里就不多说了；
之后的点都是缩点之后点集；
我们考虑两种点：
> <1> 以 1 为起点可以直接到达的；
我们这里叫它一类点；
<2> 以该点为起点，可以直接到达 1 的；
我们这里叫它二类点；
所以我们先用 spfa 处理出来从 1 到这两种点的点权值；
统计 ans 用；
然后枚举每一个一类点；
由于我们只能走一次反边；
所以我们所要的反边一定与一类点和二类点相连；
因为这样才能确保从 1 出发，再回到 1 ；
所以我们可以确定一类点和二类点相连的边一定满足；
那么我们枚举这些边；
然后统计所连两点的点权和；
更新 ans ；
但是由于在一开始 spfa 处理时；
1 这个点的点权计算了两遍；
所以最后要减掉；
***
```cpp
#include "iostream"
#include "stdio.h"
#include "algorithm"
#include "vector"
#include "map"
#include "queue"
#define II int
#define R register
#define I 123546
using namespace std;
struct node {
II to,up;
} aa[I], aa_1[I];
II head[I], DFN[I], LOW[I], is[I], stack[I], vis[I], belong[I], nu[I];
II inq[I], in_just[I], dis_back[I], in_back[I], dis_just[I], head_1[I], dis[I];
II _tot,n,m,_top,_num,bit,ans,_tot_1;
vector <II> just[I], back[I];
queue <II> Q;
void add(R II x,R II y)
{
aa[++_tot].to=y;
aa[_tot].up=head[x];
head[x]=_tot;
}
void add_1(R II x,R II y)
{
aa_1[++_tot_1].to=y;
aa_1[_tot_1].up=head_1[x];
head_1[x]=_tot_1;
}
void Tarjan(R II x)
{
DFN[x]=LOW[x]=++_num;
stack[++_top]=x; vis[x]=1;
for(R II i=head[x];i;i=aa[i].up)
{
R II go=aa[i].to;
if(!DFN[go]) {
Tarjan(go);
LOW[x]=min(LOW[x],LOW[go]);
} else if(vis[go]) LOW[x]=min(LOW[x],DFN[go]);
}
if(LOW[x]==DFN[x]) {
bit++;
do {
R II o=stack[_top--];
vis[o]=0;
belong[o]=bit;
nu[bit]++;
} while (stack[_top+1]!=x) ;
}
}
void dfs_just(R II x)
{
in_just[x]=1;
for(R II i=0;i<just[x].size();i++)
{
R II go=just[x][i];
if(!in_just[go]) {
dfs_just(go);
}
}
}
void dfs_back(R II x)
{
in_back[x]=1;
for(R II i=0;i<back[x].size();i++)
{
R II go=back[x][i];
if(!in_back[go]) {
dfs_back(go);
}
}
}
void spfa_just()
{
for(R II i=1;i<=bit;i++) dis_just[i]=-1e9;
Q.push(belong[1]); inq[belong[1]]=1;
dis_just[belong[1]]=nu[belong[1]];
while (!Q.empty()) {
R II x=Q.front(); Q.pop(); inq[x]=0;
for(R II i=0;i<just[x].size();i++)
{
R II go=just[x][i];
if(dis_just[go]<dis_just[x]+nu[go]) {
dis_just[go]=dis_just[x]+nu[go];
if(!inq[go]) {
Q.push(go);
inq[go]=1;
}
}
}
}
}
void spfa_back()
{
for(R II i=1;i<=bit;i++) dis_back[i]=-1e9;
Q.push(belong[1]); inq[belong[1]]=1;
dis_back[belong[1]]=nu[belong[1]];
while (!Q.empty()) {
R II x=Q.front(); Q.pop(); inq[x]=0;
for(R II i=0;i<back[x].size();i++)
{
R II go=back[x][i];
if(dis_back[go]<dis_back[x]+nu[go]) {
dis_back[go]=dis_back[x]+nu[go];
if(!inq[go]) {
Q.push(go);
inq[go]=1;
}
}
}
}
}
int main()
{
// freopen("1.in","r",stdin);
scanf("%d%d",&n,&m);
for(R II i=1;i<=m;i++)
{
R II x,y;
scanf("%d%d",&x,&y);
add(x,y);
}
for(R II i=1;i<=n;i++)
{
if(!DFN[i]) {
Tarjan(i);
}
}
// 缩点;
for(R II i=1;i<=n;i++)
{
for(R II j=head[i];j;j=aa[j].up)
{
R II go=aa[j].to;
if(belong[go]!=belong[i]) {
just[belong[i]].push_back(belong[go]);
back[belong[go]].push_back(belong[i]);
}
}
}
// 建正反边;
dfs_just(belong[1]);
dfs_back(belong[1]);
// 记录一、二类点;
spfa_just();
spfa_back();
// 计算权值;
for(R II i=1;i<=bit;i++)
{
if(in_just[i]) {
for(R II j=0;j<back[i].size();j++)
{
R II go=back[i][j];
if(in_back[go]) {
ans=max(ans,dis_just[i]+dis_back[go]);
}
}
}
}
// 枚举合法的边;
printf("%d\n",ans-nu[belong[1]]);
// 减去 1 多算的的权值;
exit(0);
}
```
这个题的难点不在于思路，而是代码实现；
***