专栏首页wymP3119 [USACO15JAN]草鉴定Grass Cownoisseur 缩点 topo或最长路

P3119 [USACO15JAN]草鉴定Grass Cownoisseur 缩点 topo或最长路

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。

本文链接:https://blog.csdn.net/qq_41603898/article/details/102249025

题意:n个点 m条有向边,可以来回走一个点,问在可以逆行一次的情况下最多有能经过多少个不同的点。

解: 先缩点去环建新图,新图建正序(表示以1为起点到达的点)和逆序(以1为终点到达的点) ,然后最长路求出从1到每个点经过不同点的最大数目 正向.f[i]和反向.f[i] ,最后枚举每一条边,计算ans和当前边两点最大值。 输出 ans - sum[belong[1]] ,因为这个重复了。其他细节见代码

#include <bits/stdc++.h>
using namespace std;
const int N = 300000;
const int inf = 0x7fffffff;
struct NN{
	int nxt,v;
}edge[N];
int n,m,num,cnt,head[N],ct;
int low[N],dfn[N],book[N],belong[N],sum[N];
void add(int x,int y){
	++ct;
	edge[ct].v = y;
	edge[ct].nxt = head[x];
	head[x] = ct;
}
stack<int> s;
struct topo{
	struct No{
		int v,nxt;
	}edge[N];
	int ct,in[N],head[N],vis[N];
	int f[N];
	void add(int x,int y){
		++ct;
		edge[ct].nxt = head[x];
		edge[ct].v = y;
		head[x] = ct;
		in[y]++;
	}
	void to_Sort(){
		queue<int> q;
		for(int i=1;i<=n;i++) f[i] = -inf;
		//把其他点都设置为负无穷 只有和1所在联通块相连才能更大 
		f[belong[1]] = sum[belong[1]];
		//初始化 防止走不通  f[i] 表示到第 i 块联通分量的最大数目 
		for(int i=1;i<=n;i++){
			if(!in[i])q.push(i);
		}
		while(!q.empty()){
			int v = q.front();	q.pop();	vis[v] = 1;
			for(int i=head[v];i;i=edge[i].nxt){
				f[edge[i].v] = max(f[edge[i].v],f[v]+sum[edge[i].v]);
				in[edge[i].v]--;
				if(!in[edge[i].v]&&!vis[edge[i].v])q.push(edge[i].v),vis[edge[i].v] = 0;
			}
		}
	}
}pos,neg; 
void tarjan(int u){
	dfn[u] = low[u] = ++num;
	s.push(u); book[u]=1;
	for(int v,i=head[u];i;i=edge[i].nxt){
		v = edge[i].v;
		if(!dfn[v]){
			tarjan(v);
			low[u] = min(low[u],low[v]);
		}else if(book[v])low[u] = min(low[u],dfn[v]);
	}
	if(dfn[u]==low[u]){
		int v;
		++cnt;
		do{
		 v = s.top();
		 s.pop();
		 book[v] = 0;
		 belong[v] = cnt;
		 sum[cnt]++;
		}while(u!=v);
	}
}
int main()
{
	scanf("%d %d",&n,&m);
	for(int i=1;i<=m;i++){
		int u,v;
		scanf("%d %d",&u,&v);
		add(u,v);
	}
	for(int i=1;i<=n;i++)
		if(!dfn[i]){
			tarjan(i);
		}	
	for(int i=1;i<=n;i++){
		for(int v,j=head[i];j;j=edge[j].nxt){
			v = edge[j].v;
			if(belong[i]!=belong[v]){
				pos.add(belong[i],belong[v]);
				neg.add(belong[v],belong[i]);
			}
		}
	}
	pos.to_Sort();
	neg.to_Sort(); 
	int ans = sum[belong[1]];//初始化为一个块个数 防止走不通  
	for(int i=1;i<=n;i++){
		for(int v,j=head[i];j;j=edge[j].nxt){
			v = edge[j].v;
			if(pos.f[belong[v]]>0&&neg.f[belong[i]]>0)//两点都必须到达 
			ans = max(ans,pos.f[belong[v]]+neg.f[belong[i]]);
		}	
	}
	printf("%d\n",ans-sum[belong[1]]);
	return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【推荐】一文辨清SD-WAN的“多快好省”

    所谓多,就是网络带宽大;所谓快,就是专线从申请到建成的速度快,甚至达到秒级;所谓好,就是网络质量好;所谓省,就是价格便宜。

    SDNLAB
  • 旅行青蛙(旅かえる)的最全攻略

    IT派 - {技术青年圈} 持续关注互联网、大数据、人工智能领域 1、界面分为庭院和室内。 2、庭院内上方为【主菜单】,包括【现有物品】、【记录】、【帮助】三个...

    IT派
  • 用 上帝视角 来解答你的蛙到底在干什么?(逆向游戏程序逻辑)

    呱呱走火入魔 - 逆向游戏代码 - 终结玄学迷信 看到很多人对物品的使用上的很多猜测,很多都不是很准确。 为了理解你们的呱究竟在干什么,花了五个晚上逆向游戏程序...

    刀刀老高
  • 数据分析告诉你:旅行青蛙的秘密

    最近一款“佛系游戏”《旅行青蛙》(旅かえる)爆红朋友圈,一夜间刮起一股“养蛙(娃)热潮”,知乎一位名叫@黄小秋的程序员大佬,为了让老母亲老父亲们理解自己的呱究竟...

    钱塘数据
  • 使用Mask-RCNN在实例分割应用中克服过拟合

    代码:https://github.com/kayoyin/tiny-inst-segmentation

    小白学视觉
  • 收藏 | 使用Mask-RCNN在实例分割应用中克服过拟合

    代码:https://github.com/kayoyin/tiny-inst-segmentation

    3D视觉工坊
  • 独门秘籍奉上!听说这是CCF遥感地块分割比赛冠军的“获胜法宝”!

    【飞桨开发者说】黎昆昌,CCF BDCI遥感影像地块分割赛道冠军团队、CCF BDCI 2020 综合特等奖团队队长,中国科学院深圳先进技术研究院20级硕士。

    用户1386409
  • 成功上市、新品抱抱果销量过千万,百草味做对了什么?

    资本进入寒冬,“鲨鱼吃鲨鱼”即大公司合并现象还在不断蔓延。在美团点评、携程去哪儿、京东1号店、滴滴优步诸多合并大案之后,近日零食电商领域又上演并购案:零食电商巨...

    罗超频道
  • CVPR 2018 中国论文分享会之「视觉与语言」

    本文为 2018 年 5 月 11 日在微软亚洲研究院进行的 CVPR 2018 中国论文宣讲研讨会中第四个 Session——「Vision and Lang...

    AI科技评论

扫码关注云+社区

领取腾讯云代金券