ErikTse Runtime

  • 首页 / Home
  • | 算法学习 / Algorithm
    • 所有 / All
    • 简单 / Easy
    • 中等 / Medium
    • 困难 / Hard
  • | 技术分享 / Technology
    • 所有 / All
    • 网络技术 / NetWork
    • 资源共享 / Resource
    • 项目实践 / Event
Keep Going.
温故而知新.
  1. 首页
  2. 算法学习
  3. 中等
  4. 正文

[Tarjan模板 + topo模板 + dp]洛谷P3387 缩点

2022年5月5日 1191点热度 0人点赞 0条评论

传送门:P3387 【模板】缩点 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

顾名思义啊,一个模板题,用tarjan算法缩点之后topo + DAGdp就可以了,写一个模板,防止自己忘记。

代码

#include <bits/stdc++.h>
#define int long long
#define pb push_back
using namespace std;
const int maxn = 1e4 + 9;

int a[maxn];//点权ai 
vector<int> g[maxn];//存图 
vector<int> G[maxn];//存缩点后的 DAG
int dfn[maxn], low[maxn], col[maxn], tot = 0;//tot为强联通分量编号 
int idx = 0;//idx记录dfn和low的初始值 
int ind[maxn];//表示入度 
//栈,用于表示有哪些子节点 
int stk[maxn], top = 0;
bitset<maxn> ins;//表示是否在栈中 

int max_num(int tmp[],int st,int ed)
{
	int res = 0;
	for(int i = st;i < ed; ++ i)res = max(res, tmp[i]);
	return res;
}

void tarjan(int x)
{
	dfn[x] = low[x] = ++ idx;
	stk[++ top] = x;
	ins[x] = 1;
	
	for(auto& y : g[x])
	{
		//low[y] > dfn[x]判断割边 
		if(!dfn[y]) //如果y没有访问过 
		{
			tarjan(y);
			low[x] = min(low[x], low[y]);
		}
		else if(ins[y]) //如果访问过且在栈中,说明遇到父节点了,要回溯咯 
		{
			low[x] = min(low[x], dfn[y]);
		}
	}
	
	if(dfn[x] == low[x])//遇到了一个小父亲 
	{
		tot ++;//新建一个强联通分量 
		while(stk[top + 1] != x)//直到小父亲也加进去了,说明加完了 
		{
			col[stk[top]] = tot;
			ins[stk[top --]] = 0;
		}
	}
}

int topo(int n)
{
	queue<int> q;
	//由于变量实在太多了,就在堆里面开一下 
	int dp[maxn], val[maxn];
	memset(dp, 0, sizeof dp);
	memset(val, 0, sizeof val);
	for(int i = 1;i <= n; ++ i)val[col[i]] += a[i];
	
	//得到topo的起点 
	for(int i = 1;i <= tot; ++ i)if(!ind[i])q.push(i);
	
	while(!q.empty())
	{
		int x = q.front();q.pop();
		dp[x] = max(dp[x], val[x]);
		for(auto &y : G[x])
		{
			dp[y] = max(dp[y], dp[x] + val[y]);
			ind[y] --;
			if(!ind[y])q.push(y);
		}
	}
	return max_num(dp, 1, tot + 1);
}

signed main()
{
	ios::sync_with_stdio(0);
	
	int n, m;cin >> n >> m;
	for(int i = 1;i <= n; cin >> a[i ++]); // oh这糟糕的码风 
	
	vector<pair<int, int> > v;//存下点,便于加到新图中 
	for(int i = 1;i <= m; ++ i)
	{
		int x, y;cin >> x >> y;
		g[x].pb(y);
		v.pb({x, y});
	}
	
	for(int i = 1;i <= n; ++ i)if(!dfn[i])tarjan(i);
	//构造出了一个有向无环图
	for(auto &i : v)
	{
		int x = col[i.first], y = col[i.second];
		if(x == y)continue;//自环就不连接 
		//如果这条边不存在就加进去 
		if(find(G[x].begin(), G[x].end(), y) == G[x].end())
		{
			G[x].pb(y);
			ind[y] ++;
		}
	}
	
	cout << topo(n) << '\n';
	return 0;
}
本作品采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可
标签: C++ DP tarjan topo 模板 洛谷
最后更新:2022年7月9日

Eriktse

19岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌选手,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

点赞
< 上一篇
下一篇 >

文章评论

razz evil exclaim smile redface biggrin eek confused idea lol mad twisted rolleyes wink cool arrow neutral cry mrgreen drooling persevering
取消回复

订阅本站
Loading
文章目录
  • 代码

COPYRIGHT © 2022 ErikTse Runtime. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang

赣ICP备2022001555号-1

赣公网安备 36092402000057号