夏晓光(loveJY)的博客

图论练习题

首先我们会发现可以缩下点,因为同一个连通分量里面就可以自由遍历所有的点,然后就可以得到一个拓扑图.....

注意是拓扑图不是树我也是服了自己

然后考虑在拓扑图上求这个答案,显然我们可以设计dp[i][0/1]表示点i是否已经走过反向边走到1的最长路径

然后显然这个东西要建反图才能处理每个点走到1的....

然后我们就这样建反图跑spfa就好了

显然,二维dp状态我们是可以用分层图的,所以可以再构造一个分层图,以更不错的常数解决此题

代码就用了这个

思维难度好小

code:

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN=4e5+7;
int n,m;
int home[MAXN],to[MAXN],nxt[MAXN],ccnt,frm[MAXN];
inline void ct(int x,int y) {
	ccnt++;
	nxt[ccnt]=home[x];
	home[x]=ccnt;
	to[ccnt]=y;
	frm[ccnt]=x;
}
int first[MAXN],cccnt;
struct rec {
	int to,nxt,vl;
} e[MAXN];
inline void ct2(int x,int y) {
	cccnt++;
	e[cccnt].nxt=first[x];
	first[x]=cccnt;
	e[cccnt].to=y;
}

int st[MAXN],tp,dfn[MAXN],dep,d[MAXN],low[MAXN],nw,num[MAXN],fl[MAXN];
inline void tarjan(int u) {
	fl[u]=1;
	dfn[u]=low[u]=++dep;
	st[++tp]=u;
	for(int i=home[u]; i; i=nxt[i]) {
		int v=to[i];
		if(!dfn[v]) {
			tarjan(v);
			low[u]=min(low[u],low[v]);
		} else if(!fl[v])continue;
		low[u]=min(dfn[v],low[u]);
	}
	if(low[u]==dfn[u]) {
		++nw;
		while(1) {
			int v=st[tp];
			fl[v]=0;
			d[v]=nw;
			num[nw]++;
			--tp;
			if(v==u)break;
		}
	}
	return ;
}

int que[MAXN],head,tail,vis[MAXN],ans,dis[MAXN];
inline void spfa() {
	int s=d[1];
	head=tail=1;
	que[tail++]=s;
	while(head<tail) {
		int u=que[head];
		++head;
		vis[u]=0;
//		printf("%d!%d\n",u,dis[u]);
		for(int i=first[u]; i; i=e[i].nxt) {
			int v=e[i].to;
//			printf("%d %d %d %d\n",v,dis[v],num[v],num[u]);
			if(dis[v]<dis[u]+num[u]) {
				dis[v]=dis[u]+num[u];
				if(!vis[v]) {
					vis[v]=1;
					que[tail++]=v;
				}
			}
		}
//		puts("--------");
	}
	for(int i=1; i<=2*nw+1; ++i)ans=max(ans,dis[i]);
	return ;
}

int main() {
	scanf("%d%d",&n,&m);
	for(int i=1,x,y; i<=m; ++i)
		scanf("%d%d",&x,&y),ct(x,y);
	for(int i=1; i<=n; ++i) {
		if(!dfn[i])tarjan(i);
	}
//	for(int i=1; i<=n; ++i)printf("%d %d\n",i,d[i]);
	for(int i=1; i<=nw; ++i)num[i+nw]=num[i];
	for(int i=1; i<=m; ++i) {
		int u=frm[i];
		int v=to[i];
		if(d[u]==d[v])continue;
//		printf("%d %d %d %d\n",u,v,d[u],d[v]);
		ct2(d[v],d[u]);
		ct2(d[u],d[v]+nw);
		ct2(d[v]+nw,d[u]+nw);
	}
	spfa();
	printf("%d\n",dis[d[1]+nw]);
	return 0;
}