题意,从0点出发,遍历所有点,遍历边时候要付出代价,在一个SCC中的边不要付费。求最小费用。
有向图缩点(无需建立新图,,n《=50000,建则超时),遍历边,若不在一个SCC中,用一个数组更新记录最小到达该连通分量的最小边权即可。。。边聊天,边1A,哈哈。。。
#include
#include
#include
#include
#include
using namespace std; const int inf=0x3f3f3f3f; const int maxv=50005,maxe=100005; int nume=0;int head[maxv];int e[maxe][3]; void inline adde(int i,int j,int c) { e[nume][0]=j;e[nume][1]=head[i];head[i]=nume; e[nume++][2]=c; } int dfn[maxv];int low[maxv];int vis[maxv];int ins[maxv]; stack
sta; int scc[maxv];int numb=0;int times=0; int n,m; void tarjan(int u) { dfn[u]=low[u]=times++; ins[u]=1; sta.push(u); for(int i=head[u];i!=-1;i=e[i][1]) { int v=e[i][0]; if(!vis[v]) { vis[v]=1; tarjan(v); if(low[v]