社区讨论

缩点+dij最短路,29ptsWA求助,真没找到错哪QAQ

P3119[USACO15JAN] Grass Cownoisseur G参与者 3已保存回复 3

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
3 条
当前快照
1 份
快照标识符
@lo2ichcr
此快照首次捕获于
2023/10/23 14:19
2 年前
此快照最后确认于
2023/10/23 14:19
2 年前
查看原帖
CPP
#include<bits/stdc++.h>
#define N 100004
using namespace std;
int n,m,cnt,cc,cs,ans;
struct side{
	int u,v;
}sd[N];
vector<int>g[N],g_[N],h_[N];

int dfn[N],low[N],col[N],val[N];
stack<int>s;
bool ins[N];

int d1[N],d2[N];
bool f1[N],f2[N];

inline int read(){
	int x=0;
	char ch=getchar();
	while(!isdigit(ch))ch=getchar();
	while(isdigit(ch)){
		x=(x<<1)+(x<<3)+(ch&15);
		ch=getchar();
	}
	return x;
}
void tarjan(int u){
	dfn[u]=low[u]=++cnt;
	ins[u]=1,s.push(u);
	for(int v:g[u]){
		if(dfn[v]){
			if(ins[v])low[u]=min(low[u],dfn[v]);
		}
		else{
			tarjan(v);
			low[u]=min(low[u],low[v]);
		}
	}
	if(dfn[u]==low[u]){
		cc++;
		int x;
		while(1){
			x=s.top();
			col[x]=cc;
			val[cc]++;
			ins[x]=0;
			s.pop();
			if(x==u)break;	
		}
	}
}
struct node{
	int v,w;
};
bool operator<(const node &x,const node &y){
	return x.w<y.w;
}
void dij(vector<int>g[],int dis[],bool f[]){
	priority_queue<node>q;
	int u=col[1];
	dis[u]=val[u];
	q.push({u,dis[u]});
	while(!q.empty()){
		u=q.top().v;
		q.pop();
		if(f[u])continue;
		f[u]=1;
		for(int v:g[u]){
			if(dis[v]<dis[u]+val[v]){
				dis[v]=dis[u]+val[v];
				q.push({v,dis[v]});
			}
		}
	}
}
int main(){
	memset(d1,-63,sizeof(d1));
	memset(d2,-63,sizeof(d2));
	int u,v;
	n=read(),m=read();
	for(int i=1;i<=m;i++){
		u=read(),v=read();
		g[u].push_back(v);
	}
	for(int i=1;i<=n;i++)
		if(!dfn[i])tarjan(i);
	#define u col[i]
	#define v col[j]
	for(int i=1;i<=n;i++)
		for(int j:g[i])
			if(u!=v){
				g_[u].push_back(v);
				h_[v].push_back(u);
				sd[++cs]={v,u};
			}
	#undef u
	#undef v
	
	dij(g_,d1,f1),dij(h_,d2,f2);
	ans=val[col[1]];//不逆向 
	for(int i=1;i<=cs;i++)
		ans=max(ans,d1[sd[i].u]+d2[sd[i].v]-val[col[1]]);
	printf("%d",ans);
}

回复

3 条回复,欢迎继续交流。

正在加载回复...