题意:给定一个有向图,从一个节点出发到所有的节点需要翻转多少次方向,问最小翻转次数为多少次
条件:1 如果是无向图,这整个图都是通的
2 题目给出的n节点的个数是2·10^5
思路:题目给出的n节点的个数是2·10^5,所以存地图的时候要用vector,而且绝对不能暴力。想必肯定只用遍历一次就可以得到其它点的关系,以此想法为突破口,就会发现我任选一个起始点,只要遍历起始点到其他所有的顶点的到翻转次数和起始点到该个点需要的翻转和不翻转次数。其它点的到其它所有点翻转次数=起始点到其他所有的顶点的到翻转次数-起始点到该个点需要的翻转次数+起始点到该个点需要的不翻转次数。(ans[i]=count1-vis[i][1]+vis[i][3])
代码:
#include
#include
#include
#include
#include
#include
总结:1 那次题目做的还是不错,挺多人没做出来,想法真的挺重要的,但也需要平时多多积累
2 看了队里大家补题的记录,别人都那么努力,凭什么自己不加把劲










