Codeforces Round #545 (Div. 2) E 强连通块 + dag上求最大路径 + 将状态看成点建图

https://codeforces.com/contest/1138/problem/E

题意

有n个城市(1e5),有m条单向边(1e5),每一周有d天(50),对于每个城市假如在某一天为1表示这天城市博物馆开放,反之闭馆,问你最多能去多少个博物馆

题解

第一个分出来的强连通块是dag的起点
假设博物馆每天都开放,那么求出图的强连通块后,dag上dp就行
现在加上有d天的话,只需要加多一维构成状态,然后将状态一维化看成点,再建图
计数的时候注意每个强联通块里面每个城市只能选一次

代码(链式前向星scc)

#include<bits/stdc++.h>

#define N 100005

#define D 55

#define MAXN N*D

using namespace std;

int hd[MAXN],nt[MAXN],to[MAXN],cnt;

int hd2[MAXN],nt2[MAXN],to2[MAXN],cnt2;

int dfn[MAXN],low[MAXN],vis[MAXN],stk[MAXN],top,Time,scc,blk[MAXN];

int dp[MAXN],sz[MAXN];

int n,m,d,u,v;

char s[N][D];

int id(int a,int b){

	return (a-1)*d+b%d+1;

}

void add(int u,int v){

	nt[++cnt]=hd[u];to[cnt]=v;hd[u]=cnt;

}

void add2(int u,int v){

	nt2[++cnt2]=hd2[u];to2[cnt2]=v;hd2[u]=cnt2;

}

void tarjan(int u){

	dfn[u]=low[u]=++Time;

	stk[++top]=u;vis[u]=1;

	for(int i=hd[u];i;i=nt[i]){

		int v=to[i];

		if(!dfn[v]){

			tarjan(v);

			low[u]=min(low[u],low[v]);

		}else if(vis[v]){

			low[u]=min(low[u],dfn[v]);

		}

	}

	if(dfn[u]==low[u]){

		++scc;

		for(;;){

			int x=stk[top];top--;

			vis[x]=0;blk[x]=scc;

			if(x==u)break;

		}

	}

}

void dfs(int u){

	if(dp[u])return;

	for(int i=hd2[u];i;i=nt2[i]){

		int v=to2[i];

		dfs(v);

		dp[u]=max(dp[u],dp[v]);

	}

	dp[u]+=sz[u];

	return;

}

int main(){

	scanf("%d%d%d",&n,&m,&d);

	for(int i=0;i<m;i++){

		scanf("%d%d",&u,&v);

		for(int j=0;j<d;j++)

			add(id(u,j),id(v,(j+1)%d));

	}

	for(int i=1;i<=n;i++)scanf("%s",s[i]);

	for(int i=1;i<=n*d;i++){

		if(!dfn[i])tarjan(i);

	}

	for(int i=1;i<=n;i++){

		for(int j=0;j<d;j++){

			int x=id(i,j);

			if(s[i][j]=='1'&&vis[blk[x]]!=i){

				sz[blk[x]]++;

				vis[blk[x]]=i;

			}

			for(int k=hd[x];k;k=nt[k]){

				int v=to[k];

				if(blk[v]!=blk[x])add2(blk[x],blk[v]);

			}

		}

	}

	dfs(blk[1]);

	printf("%d",dp[blk[1]]);

}

巴特西

Codeforces Round #545 (Div. 2) E 强连通块 + dag上求最大路径 + 将状态看成点建图

题意

题解

代码(链式前向星scc)

最新文章

热门文章