P3119 [USACO15JAN]草鉴定Grass Cownoisseur
如果不可以反向走的话。这个题的难度就如此的变态。
先不考虑逆向走。
然后我们先分析一波这个图的。可以讲图中的点分为三类。
~标号为1的点
~能到达1的点
~能从1点到达的点
很显然，若只有能到达1的点，或者只有从1可以到达的点。这个图就无法从1出发，然后再回到1。
然后上面两部分点肯定不能所载一起。但是如果我们逆向走的话。就相当从1可以到达的点中，引出了一条连向可以到达1的点的一条边。就构成了一个环。
所以我们就可以枚举一下满足连接上这两部分点的边，然后取一个最优值
具体代码实现的话就是tarjan+spfa（两次，求出两部分的点和）
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<vector>
#include<queue>
using namespace std;
const int maxn=101000;
struct node
{
int from;
int point;
int nxt;
};
node L1[maxn<<1],L2[maxn<<1],L3[maxn<<1];
int H1[maxn],H2[maxn],H3[maxn],T1,T2,T3;
int belong[maxn],num[maxn],cnt;
int Map[maxn];
int dfn[maxn],low[maxn],t;
int stack[maxn],top;
int insta[maxn];
vector<int>Contain[maxn];
bool inque[maxn];
int Dis1[maxn],Dis2[maxn],ans;
void add1(int a,int b)
{
L1[++T1].point=b;
L1[T1].nxt=H1[a];
H1[a]=T1;
}
void add2(int a,int b)
{
L2[++T2].point=b;
L2[T2].nxt=H2[a];
H2[a]=T2;
}
void add3(int a,int b)
{
L3[++T3].from=a;
L3[T3].point=b;
L3[T3].nxt=H3[a];
H3[a]=T3;
}
void tarjan(int now)
{
dfn[now]=low[now]=++t;
stack[++top]=now;
insta[now]=true;
for(int i=H1[now];i;i=L1[i].nxt)
{
int nxt=L1[i].point;
if(!dfn[nxt])
{
tarjan(nxt);
low[now]=min(low[now],low[nxt]);
}
else if(insta[nxt]&&dfn[nxt]<low[now])
low[now]=dfn[nxt];
}//缩点的模板
if(dfn[now]==low[now])
{
cnt+=1;
int tot=0,pas;
do
{
pas=stack[top--];
belong[pas]=cnt;//记录属于哪一个强连通分量
num[cnt]+=1;//点数更新
insta[pas]=false;
Contain[cnt].push_back(pas);//将一个强连通分量中的点存下来
}while(pas!=now);
}
return ;
}
void build(int now)
{
for(int i=0;i<Contain[now].size();i++)//遍历强连通分量里的点
{
int nxt=Contain[now][i];//取出来
for(int j=H1[nxt];j;j=L1[j].nxt)//遍历原图
if(belong[nxt]!=belong[L1[j].point]&&Map[belong[L1[j].point]]!=now)//如果这个强连通分量和这条边所连的分量之间没有建立边，而且是不同的强连通分量
{
Map[belong[L1[j].point]]=now;//打一个标记
add2(belong[nxt],belong[L1[j].point]);//正向存图
add3(belong[L1[j].point],belong[nxt]);//反向存图
}
}
}
void Spfa1()//正图上跑
{
queue<int>q;
q.push(belong[1]);
inque[belong[1]]=true;
Dis1[belong[1]]=-num[belong[1]];//存负，跑最短路
while(!q.empty())
{
int pas=q.front();q.pop();
inque[pas]=false;
for(int i=H2[pas];i;i=L2[i].nxt)
if(Dis1[L2[i].point]>Dis1[pas]-num[L2[i].point])
{
Dis1[L2[i].point]=Dis1[pas]-num[L2[i].point];
if(!inque[L2[i].point]);
{
inque[L2[i].point]=true;
q.push((L2[i].point));
}
}
}
}
void Spfa2()//反图上跑
{
queue<int>q;
q.push(belong[1]);inque[belong[1]]=true;
Dis2[belong[1]]=-num[belong[1]];
while(!q.empty())
{
int pas=q.front();q.pop();
inque[pas]=false;
for(int i=H3[pas];i;i=L3[i].nxt)
if(Dis2[L3[i].point]>Dis2[pas]-num[L3[i].point])
{
Dis2[L3[i].point]=Dis2[pas]-num[L3[i].point];
if(!inque[L3[i].point])
{
inque[L3[i].point]=true;
q.push(L3[i].point);
}
}
}
}
void Star()
{
for(int i=1;i<=cnt;i++)
for(int j=H3[i];j;j=L3[j].nxt)
if(Dis1[L3[j].from]<0&&Dis2[L3[j].point]<0)//枚举
ans=min(ans,Dis1[L3[j].from]+Dis2[L3[j].point]+num[belong[1]]);
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
int a,b;
for(int i=1;i<=m;i++)
{
scanf("%d%d",&a,&b);
add1(a,b);//存图
}
for(int i=1;i<=n;i++)
if(!dfn[i])
tarjan(i);//tarjan缩点
for(int i=1;i<=cnt;i++)
build(i);//建出缩完点后的图
Spfa1();//求出从1开始可以到达的点数和
Spfa2();//求出可以到达1的点数和
Star();//瞎 star star 枚举
printf("%d",-ans);
}