本文主要是介绍codeforces#244（div.2） C，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
动漫节一游回来之后一直处于一种意识模糊的状态
看到大家都陆陆续续地过了C心里还是有点着急（自己没思路啊囧）
其实当时就在想该如何找到DFS中的一个环，然后再找到环路上最小的一个值
把所有环路上最小的值加起来就是结果，后来看到有人在群里说是tarjan求强连通分量，我就愉（bei）快（shang）地去睡觉了
第二天起来就学习了一下强连通分量的相关知识和tarjan，现在整理下思路
https://www.byvoid.com/blog/scc-tarjan
tarjan的思路就是通过DFS找到一条环路，将以DFS访问的顺序的节点盖上时间戳，当该点u时间戳与该点（直接或间接）能够访问到的最早入栈的点相同（即可以说成是自身就是该子树的根）时，即表示它就是一个强连通量的根节点。我们不妨直接找到树中的一个“叶子”（姑且这么叫吧，把这里的“叶子”定义为除了栈S中的节点不能到达其他任何节点的节点（好绕囧））节点v,那么它只有两种可能：
1.可以在未处理节点的栈S中找到一个V使得（v，V）∈E，因此可以由V出发到v构成一个环路
2.不可以在未处理节点的栈S中找到一个V使得（v，V）∈E，因此它自成一个强连通分量（因为它不能到达任何的节点）（上述称为判断1）
如果讨论清楚了“叶子”节点，它必然成为某一个强连通分量中的一个顶点；再讨论栈中v的上一个节点u（即（u，v）∈E，且u∈栈S）
1.若为上述情况1，则根据上述链接和大白书上的定理，u,v必在同一个强连通分量中
2.若为上述情况2，则可以通过DFS找到u的其他后继vi：
（1）若vi存在，则继续用判断1判断有后继(祖先）在S中
（2）若vi不存在，则说明u没有其他后继了（自然也没有在栈S中的后继），则u可以通过上述情况2，u自成一个强连通分量
至此，证明完毕。可以保证，在栈S中的节点必然是以U为根“最大”（不知道这样说准不准确）的强连通量（因为不满足的已经被标记上强连通序号且弹出栈了）。
此说明是基于所有不属于以U为根的强连通分量的顶点已经被标记且弹出栈了。
上述描述即是以DFS序来进行描述的。
OK，回到这道题，如果找到了一个强连通分量，则可以统计出它的最小权值和最小权值点的个数
总的方案数就是所有强连通分量中的最小权值点个数的乘积
下面是C题的程序
#include<cstdio>
#include<cstring>
#include<stack>
#include<algorithm>
using namespace std;
typedef long long LL;
const int SIZEN=100005;
const int SIZEM=300005;
const int INF=1e9;
const int MOD=1e9+7;
struct edge{int to,next;
};
edge e[SIZEM];
int cost[SIZEN],head[SIZEN];
int DFN[SIZEM],low[SIZEN],sscn[SIZEN];
LL sz,s_cost,num_cost,dfs_time,ssc_cnt;
void addedge(int u,int v){e[sz].to=v;e[sz].next=head[u];head[u]=sz++;
}
void init(){memset(DFN,0,sizeof(DFN));memset(low,0,sizeof(low));memset(sscn,0,sizeof(sscn));memset(head,-1,sizeof(head));sz=0;num_cost=1;s_cost=0;dfs_time=1;ssc_cnt=0;
}
stack<int> S;
void tarjan(int u){DFN[u]=low[u]=dfs_time++;S.push(u);for(int i=head[u];i!=-1;i=e[i].next){int v=e[i].to;if(!DFN[v]){tarjan(v);low[u]=min(low[u],low[v]);//回溯过程，如果low[v]<low[u],则必然是因为v的某子孙和u的某祖先相连}else if(DFN[v]&&!sscn[v]){low[u]=min(low[u],DFN[v]);//即上述判断1的情况1（找到后继在S中）}}if(DFN[u]==low[u]){//找到一个强连通分量，找到分量中的最小值，和最小值的个数int x;int Min=INF,cnt=0;ssc_cnt++;for(;;){x=S.top();S.pop();sscn[x]=ssc_cnt;if(cost[x]<Min){Min=cost[x];cnt=1;}else if(cost[x]==Min) cnt++;if(x==u) break;}s_cost=s_cost+Min;num_cost=(LL)num_cost*cnt%MOD;}
}
int main()
{//freopen("data.in","r",stdin);int i,j;int n,m;int u,v;while(scanf("%d",&n)!=EOF){init();for(i=1;i<=n;i++) scanf("%d",&cost[i]);scanf("%d",&m);while(m--){scanf("%d%d",&u,&v);addedge(u,v);}for(i=1;i<=n;i++)if(!DFN[i]) tarjan(i);printf("%I64d %I64d\n",s_cost,num_cost);}return 0;
}
这篇关于codeforces#244（div.2） C的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
