洛谷P 3119[USACO 15 JAN]草鑑定Grass Cownoisseur tarjan縮点spfa双方向建図走spfa
4327 ワード
タイトルリンク:
https://www.luogu.org/problem/P3119
参考ブログ:
https://wangym.blog.luogu.org/solution-p3119
このブログをもう一度詳しく読むことをお勧めします
考え方:
1:tarjan縮点
2:図を作って、縮み点の後のすべての強い連通成分を1つのノードと見なす
1:順方向図を作成し、color[1]からspfaを走ると、color[1]から各点までの最短経路(負をとると最長経路)が得られる
2:逆方向図を作成し、color[1]からspfaを走ると、各点からcolor[1]までの最短経路(負を取ると最長経路)が得られる
3:エッジの重み値は、エッジの終点のノードに含まれる元の図のノード数、すなわち、この強い連通成分の-colornum値である
3:順方向図において、点iに点tを指すエッジがある場合、i->tの経路を逆行し、(-d[t]-d 2[i]+cornum[color[1]))個の芝生場を通過する.したがって、ans=max(-d[t]-d 2[i]+colornum[color[1],ans);
一:最も簡単なコード
二:spfaのコードを2回書く(spfaをパラメータに設定せず、コードを繰り返すのはよくない)
https://www.luogu.org/problem/P3119
参考ブログ:
https://wangym.blog.luogu.org/solution-p3119
このブログをもう一度詳しく読むことをお勧めします
考え方:
1:tarjan縮点
2:図を作って、縮み点の後のすべての強い連通成分を1つのノードと見なす
1:順方向図を作成し、color[1]からspfaを走ると、color[1]から各点までの最短経路(負をとると最長経路)が得られる
2:逆方向図を作成し、color[1]からspfaを走ると、各点からcolor[1]までの最短経路(負を取ると最長経路)が得られる
3:エッジの重み値は、エッジの終点のノードに含まれる元の図のノード数、すなわち、この強い連通成分の-colornum値である
3:順方向図において、点iに点tを指すエッジがある場合、i->tの経路を逆行し、(-d[t]-d 2[i]+cornum[color[1]))個の芝生場を通過する.したがって、ans=max(-d[t]-d 2[i]+colornum[color[1],ans);
一:最も簡単なコード
#include
using namespace std;
const int maxn=1e5+1;
vectore[maxn];
setee[maxn];
int dfn[maxn],low[maxn],ins[maxn],color[maxn],timing,cnt,n,m;
int colornum[maxn];
stacks;
vector >mapp[maxn],mapp2[maxn];
int d[maxn],ing[maxn],d2[maxn],ing2[maxn];
void tarjan(int x)
{
low[x]=dfn[x]=++timing;
s.push(x);
ins[x]=1;
for(int i=0;i >*mapp,int *d,int *ing)
{
queueq;
q.push(x);
d[x]=0;
ing[x]=1;
while(!q.empty())
{
int now=q.front();
q.pop();
ing[now]=0;
for(int i=0;id[now]+mapp[now][i].second)
{
d[v]=d[now]+mapp[now][i].second;
if(ing[v])
continue;
q.push(v);
ing[v]=1;
}
}
}
}
int main()
{
ios::sync_with_stdio(0);
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int a,b;
cin>>a>>b;
e[a].push_back(b);
}
for(int i=1;i<=n;i++)
{
if(!dfn[i])
tarjan(i);
}
for(int i=1;i<=n;i++)
{
for(int j=0;j
二:spfaのコードを2回書く(spfaをパラメータに設定せず、コードを繰り返すのはよくない)
#include
using namespace std;
const int maxn=1e5+1;
vectore[maxn];
setee[maxn];
int dfn[maxn],low[maxn],ins[maxn],color[maxn],timing,cnt,n,m;
int colornum[maxn];
stacks;
vector >mapp[maxn],mapp2[maxn];
int d[maxn],ing[maxn],d2[maxn],ing2[maxn];
void tarjan(int x)
{
low[x]=dfn[x]=++timing;
s.push(x);
ins[x]=1;
for(int i=0;iq;
q.push(x);
d[x]=0;
ing[x]=1;
while(!q.empty())
{
int now=q.front();
q.pop();
ing[now]=0;
for(int i=0;id[now]+mapp[now][i].second)
{
d[v]=d[now]+mapp[now][i].second;
if(ing[v])
continue;
q.push(v);
ing[v]=1;
}
}
}
}
void spfa2(int x)
{
queueq;
q.push(x);
d2[x]=0;
ing2[x]=1;
while(!q.empty())
{
int now=q.front();
q.pop();
ing2[now]=0;
for(int i=0;id2[now]+mapp2[now][i].second)
{
d2[v]=d2[now]+mapp2[now][i].second;
if(ing2[v])
continue;
q.push(v);
ing2[v]=1;
}
}
}
}
int main()
{
ios::sync_with_stdio(0);
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int a,b;
cin>>a>>b;
e[a].push_back(b);
}
for(int i=1;i<=n;i++)
{
if(!dfn[i])
tarjan(i);
}
for(int i=1;i<=n;i++)
{
for(int j=0;j