LG3119 「USACO2015JAN」Grass Cownoisseur

问题描述

题解

显然，如果有个环，一定是全部走完的。

所以缩点，缩出一个 \(\mathrm{DAG}\) 。

只能走一次反向，于是在正图和反图上各跑一次，枚举边，取 \(\mathrm{max}\) 即可。

\(\mathrm{Code}\)

#include<bits/stdc++.h>

using namespace std;

#define maxn 100007

template <typename Tp>

void read(Tp &x){

	x=0;char ch=1;int fh;

	while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();

	if(ch=='-') {

		ch=getchar();fh=-1;

	}

	else fh=1;

	while(ch>='0'&&ch<='9'){

		x=(x<<1)+(x<<3)+ch-'0';

		ch=getchar();

	}

	x*=fh;

}

int n,dfn[maxn],low[maxn];

int m,Head1[maxn],Next1[maxn],to1[maxn],u1[maxn],tot1;

int Head2[maxn],Next2[maxn],to2[maxn],u2[maxn],tot2;

int Head3[maxn],Next3[maxn],to3[maxn],u3[maxn],tot3;

int xx,yy;

int stac[maxn],top,ind,cnt;

int sd[maxn],val[maxn];

bitset<maxn>ins;

void tarjan(int x){

	dfn[x]=low[x]=++ind;stac[++top]=x;

	ins[x]=1;

	for(int i=Head1[x];i;i=Next1[i]){

		int y=to1[i];

		if(dfn[y]) {if(ins[y]) low[x]=min(low[x],dfn[y]);}

		else{

			tarjan(y);

			low[x]=min(low[x],low[y]);

		}

	}

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

		cnt++;val[cnt]=1;

		while(stac[top]!=x){

			ins[stac[top]]=0;sd[stac[top]]=cnt;top--;++val[cnt];

		}

		sd[stac[top]]=cnt;top--;ins[x]=0;

	}

}

void add1(int x,int y){

	to1[++tot1]=y,Next1[tot1]=Head1[x],Head1[x]=tot1,u1[tot1]=x;

}

void add2(int x,int y){

	to2[++tot2]=y,Next2[tot2]=Head2[x],Head2[x]=tot2,u2[tot2]=x;

}

void add3(int x,int y){

	to3[++tot3]=y,Next3[tot3]=Head3[x],Head3[x]=tot3,u3[tot3]=x;

}

set <pair<int,int> > st;

void rebuild(){

	for(register int i=1;i<=m;i++){

//		if(sd[to1[i]]==0||sd[u1[i]]==0) continue;

		int x=sd[u1[i]],y=sd[to1[i]];

		if(st.count(make_pair(x,y))||x==y) continue;

		st.insert((make_pair(x,y)));

		add2(x,y);add3(y,x);

	}

}

int dis[2][maxn];

void fir(){

	memset(dis[0],0xcf,sizeof(dis[0]));

	dis[0][sd[1]]=val[sd[1]];queue<int>q;q.push(sd[1]);

	while(!q.empty()){

		int x=q.front();q.pop();

		for(int i=Head2[x];i;i=Next2[i]){

			int y=to2[i];

			if(dis[0][y]>=dis[0][x]+val[y]) continue;

			dis[0][y]=dis[0][x]+val[y];

			q.push(y);

		}

	}

}

void sec(){

	memset(dis[1],0xcf,sizeof(dis[1]));

	dis[1][sd[1]]=val[sd[1]];queue<int>q;q.push(sd[1]);

	while(!q.empty()){

		int x=q.front();q.pop();

		for(int i=Head3[x];i;i=Next3[i]){

			int y=to3[i];

			if(dis[1][y]>=dis[1][x]+val[y]) continue;

			dis[1][y]=dis[1][x]+val[y];

			q.push(y);

		}

	}

}

int ans=0;

void calc(){

	for(register int i=1;i<=tot2;i++){

		int x=u2[i],y=to2[i];//错误笔记：写为to2[i]，开-Wall之后会有警告。

		ans=max(ans,dis[0][y]+dis[1][x]);

	}

	printf("%d\n",ans-val[sd[1]]);//错误笔记：将sd[1]写为1，所点后1所在的结点不一定是新1号点。

}

int main(){

	read(n);read(m);

	for(register int i=1;i<=m;i++){

		read(xx);read(yy);add1(xx,yy);

	}

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

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

//	puts("********************************");

//	printf("%d\n",cnt);

//	system("pause");

//	puts("********************************");

	rebuild();

	fir();sec();

	calc();

	return 0;

}

巴特西

LG3119 「USACO2015JAN」Grass Cownoisseur

问题描述

题解

\(\mathrm{Code}\)

最新文章

热门文章