CodeForces - 219D Choosing Capital for Treeland--遍历+找规律

   声明:本站部分内容来自互联网,如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。

24

题意:给定一个有向图,从一个节点出发到所有的节点需要翻转多少次方向,问最小翻转次数为多少次

条件: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 
#include 
#include 
#include 
using namespace std;
const int maxn=200005;
int count1;//总逆置步数
vectornum[maxn*2];//地图
int vis[maxn][4];//记录有没有办拜访过,起始点到该店翻转数和不翻转数
int ans[maxn];//统计每一个节点翻转数
int main()
{int n;scanf("%d",&n);memset(vis,0,sizeof(vis));count1=0;for(int i=0;is;s.push(1);int numcount=1;while(numcount

总结:1 那次题目做的还是不错,挺多人没做出来,想法真的挺重要的,但也需要平时多多积累

            2 看了队里大家补题的记录,别人都那么努力,凭什么自己不加把劲