如果不可以反向走的话。这个题的难度就如此的变态。
先不考虑逆向走。
然后我们先分析一波这个图的。可以讲图中的点分为三类。
~标号为1的点
~能到达1的点
~能从1点到达的点
很显然，若只有能到达1的点，或者只有从1可以到达的点。这个图就无法从1出发，然后再回到1。
然后上面两部分点肯定不能所载一起。但是如果我们逆向走的话。就相当从1可以到达的点中，引出了一条连向可以到达1的点的一条边。就构成了一个环。
所以我们就可以枚举一下满足连接上这两部分点的边，然后取一个最优值
具体代码实现的话就是tarjan+spfa（两次，求出两部分的点和）
#include #include #include #include #include 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 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]
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
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);}