首页 > 代码库 > codeforces#244(div.2) C
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不存在,则u可以通过上述情况2,u自成一个强连通分量
(2)若vi存在,则继续用判断1判断有后继(祖先)在S中
至此,证明完毕。可以保证,在栈S中的节点必然是以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; }