题解 P3119 【[USACO15JAN]草鉴定Grass Cownoisseur】
noco
2017-12-12 20:02:53
# **来自蒟蒻的题解**
\*orz-orz写了超级久啊\*
表示写之前都~~不会spfa~~啊（求大佬勿喷QAQ)
1. 缩点，变成DAG。
2. 求每个点到1所在scc的路径权值和f1，1所在的scc到每个点的路径权值和f2。
3. 枚举一条边（u->v），用f1[v]+f2[u]+1所在bsz中更新答案。
其实就是一个Tarjan模板+spfa模板+重构图
~~好像不难~~
首先需要穿\*库头\*
```cpp
#include <iostream>
#include <cstring>
#include <cstdio>
#include <stack>
#include <queue>
#include<cmath>
using namespace std;
const int maxn=1e5+50;
```
然后定义一些数组啊
```cpp
int n,m,S;
int tot,idx,dfn[maxn],low[maxn];
stack<int> st;
bool ins[maxn];
int belong[maxn],bsz[maxn];
int f1[maxn],f2[maxn];
bool vis[maxn];
```
我用的是链式前向星存图啊 然后至于权值 自己思考一下
```cpp
struct nd{
int fr,to,ne,op;
}e[maxn],t[maxn];
int he[maxn], cnt;
void add(int a,int b,int w=1){
cnt++;
e[cnt].fr=a;
e[cnt].to=b;
e[cnt].ne=he[a];
he[a]=cnt;
e[cnt].op=w;
}
```
然后Tarjan的模板 ~~没什么好解释的 ~~大家应该都会
```cpp
void tarjan(int u){
dfn[u]=low[u]=++idx;
st.push(u);
ins[u]=true;
for(int i=he[u];i;i=e[i].ne){
int v=e[i].to;
if(!dfn[v]){
tarjan(v);
low[u]=min(low[u],low[v]);
}
else if(ins[v])low[u]=min(low[u],dfn[v]);
}
if(low[u]==dfn[u]){
tot++;
int x=0;
while(x!=u){
x=st.top();
st.pop();
ins[x]=false;
belong[x]=tot;
bsz[tot]++;
}
}
}
```
然后重构图( ⊙ o ⊙ )
```cpp
void rebuild(){
for(int i=1;i<=cnt;i++) t[i]=e[i];
int total=cnt;
cnt=0;
memset(he,0,sizeof(he));
for(int i=1;i<=total;i++){
int u=t[i].fr, v=t[i].to;
u=belong[u];
v=belong[v];
if(u!=v){
add(u,v,1);
add(v,u,0);
}
}
}
```
最后~\(≧▽≦)/~spfa 当然几乎没改 纯模板
```cpp
void spfa(int p,int d[]){
memset(vis,false,sizeof(vis));
queue<int> q;
q.push(S);
d[S]=0;
while(!q.empty()){
int u=q.front();
q.pop();
vis[u]=false;
for(int i=he[u];i;i=e[i].ne){
if(e[i].op!=p) continue;
int v=e[i].to;
if(d[v]<d[u]+bsz[v]){
d[v]=d[u]+bsz[v];
if(!vis[v]){
vis[v]=true;
q.push(v);
}
}
}
}
}
```
部分主函数部分
```cpp
S=belong[1];
rebuild();
n=tot;
for(int i=1;i<=n;i++)f1[i]=f2[i]=-maxn;
spfa(1,f1);spfa(0,f2);
int ans=bsz[S];
for(int i=1;i<=cnt;i++){
int u=e[i].fr,v=e[i].to;
ans=max(ans,f1[v]+f2[u]+bsz[S]);
}
```
#### 请勿copy
### 建议自己思考主要过程 最好画图模拟一下
祝各位神犇刷题愉快！！
orz望神佬勿喷**qwq**