tarjan缩点 WA on #2 求调 玄关orzorz
查看原帖
tarjan缩点 WA on #2 求调 玄关orzorz
1121439
TMLY114514楼主2024/6/21 17:01
#include<bits/stdc++.h>
using namespace std;
namespace IO{
#define ll long long
#define ischar(ch) (32<ch&&ch<127)
#define SIZE 1<<18
	char ibuf[SIZE],*is=ibuf,*it=ibuf;
#define getchar() (is==it&&(it=(is=ibuf)+fread(ibuf,1,SIZE,stdin),is==it)?EOF:*is++)
	template<typename Type>
	inline void read(Type &a){
		Type x=0;int y=0,ch=getchar();
		while(!isdigit(ch)&&(ch^EOF))y|=(ch=='-'),ch=getchar();
		while(isdigit(ch))x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
		a=y?-x:x;
	}
	inline void read(char &a){
		int ch=getchar();
		while(!ischar(ch)&&(ch^EOF))ch=getchar();
		a=ch;
	}
	inline void read(string &a){
		a="";char ch;
		while(!ischar(ch)&&(ch^EOF))ch=getchar();
		while(ischar(ch))a+=ch,ch=getchar();
	}
	inline void read(short &a){
		int ch=getchar();
		while(!isdigit(ch)&&(ch^EOF))ch=getchar();
		a=(ch^48);
	}
	template<typename Type>
	inline void read(Type a[]){
		Type *pos=a;
		int ch=getchar();
		while(!ischar(ch)&&(ch^EOF))ch=getchar();
		while(ischar(ch))*pos++=ch,ch=getchar();
		*pos=0;
	}
	inline void read(double &a){
		int zh=0,w=0,ch=getchar();
		double xi=0.0,x=1.0;
		while (!isdigit(ch)&&(ch^EOF))w|=ch=='-',ch=getchar();
		while(isdigit(ch))zh=(zh<<1)+(zh<<3)+(ch^48),ch=getchar();
		if(ch^'.')return void(a=w?-zh:zh);
		ch=getchar();
		while(isdigit(ch))x*=10.0,xi+=(ch^48)*1.0/x,ch=getchar();
		a=w?-zh-xi:zh+xi;
	}
	template<typename Type,typename ...Args>
	inline void read(Type &a,Args &...as){read(a);read(as...);}
	char obuf[SIZE],*op=obuf;
	inline void putch(const char &c){
		if(op-obuf==SIZE)fwrite(obuf,1,op-obuf,stdout),op=obuf;
		*op++=c;
	}
	template<typename Type>
	inline void write(Type x){
		if(x<0)putch('-'),x=-x;
		static int s[35],top;top=0;
		do s[top++]=x%10,x/=10;
		while(x);
		while(top)putch(s[--top]+'0');
	}
	int precision;
	inline void write(double x){
		ll n=1,base=10,k=precision;
		while(k)n=(k&1)?n*base:n,base*=base,k>>=1;
		x=round(x*n)/n;
		if(!x){
			putch('0'),putch('.');
			for(int i=1;i<=precision;++i)putch('0');
			return;
		}
		if(x<0)putch('-'),x=-x;
		ll y=(ll)round(x*n)%n;x=(ll)x;
		write((ll)x);putch('.');
		int s[35],top=0;
		for(;top<precision;y/=10)s[++top]=y%10;
		while(top)putch(s[top--]+'0');
	}
	inline void write(char ch){putch(ch);}
	inline void write(string s){for(int i=0;i<s.size();++i)putch(s[i]);}
	template<typename Type,typename ...Args>
	inline void write(Type a,Args ...as){write(a);write(as...);}
	inline void oclear(){fwrite(obuf,1,op-obuf,stdout);}
#undef SIZE
#undef ischar
}
using namespace IO;
#define N 500010
const int inf=0x3f3f3f3f;
//对于需要回溯的图上dp,可以直接建反图拓排
int n,m,val[N],len[N],a[N],rt[N],np,f[N],g[N],ind[N];
ll ans1,ans2;
//缩环,取环里面的r最少的同时长度最短的串
//反图拓排,求出每个词的答案
namespace tire{
	int tree[N][26],cnt,id[N];
	inline int getid(string s){
		int p=0;
		for(int i=0;i<s.size();++i){
			int ch=tolower(s[i])-'a';
			if(!tree[p][ch])tree[p][ch]=++cnt;
			p=tree[p][ch];
		}
		if(!id[p]){
			id[p]=++np;
			len[np]=s.size();
			for(int i=0;i<s.size();++i)if(tolower(s[i])=='r')++val[np];
		}
		return id[p];
	}
}
vector<int>e[N],ne[N];
#define add(u,v) e[u].push_back(v)
namespace tarjan{
	int st[N],top,dfn[N],low[N],vis[N],num,tot;
	inline void solve(int u){
		low[u]=dfn[u]=++num;
		vis[st[++top]=u]=1;
		for(int v:e[u]){
			if(!dfn[v])solve(v),low[u]=min(low[u],low[v]);
			else if(vis[v])low[u]=min(low[u],dfn[v]);
		}
		if(low[u]==dfn[u]){//u是这个环的根
			++tot;
			while(st[top]^u)vis[st[top]]=0,rt[st[top--]]=tot;
			vis[u]=0,rt[st[top--]]=tot;
		}
	}	
}
inline void update(int u,int rnum,int len){//对于新图中的点u,加入有rnum个r,长度为len的答案
	if(rnum<f[u])f[u]=rnum,g[u]=len;
	else if(f[u]==rnum)g[u]=min(g[u],len);
}
queue<int>q;
inline void topu(){
	for(int i=1;i<=tarjan::tot;++i)if(!ind[i])q.push(i);
	while(q.size()){
		int u=q.front();q.pop();
		for(int v:ne[u]){
			update(v,f[u],g[u]);//因为是反向建图,v的答案来自u,类似于dfs中的回溯
			if(!--ind[v])q.push(v);
		}
	}
}
signed main(){
	read(n);
	string u,v;
	for(int i=1;i<=n;++i)read(u),a[i]=tire::getid(u);
	read(m);
	for(int i=1;i<=m;++i)read(u,v),add(tire::getid(u),tire::getid(v));
	for(int i=1;i<=np;++i)if(!tarjan::dfn[i])tarjan::solve(i);
	for(int i=1;i<=tarjan::tot;++i)f[i]=g[i]=inf;
	for(int u=1;u<=np;++u){
		update(rt[u],val[u],len[u]);
		for(int v:e[u])if(rt[u]^rt[v])ne[rt[v]].push_back(rt[u]),++ind[rt[u]];//反向建图
	}
	topu();
	for(int i=1;i<=n;++i)ans1+=f[rt[a[i]]],ans2+=g[rt[a[i]]];
	write(ans1,' ',ans2);
	oclear();
	return 0;
} 
2024/6/21 17:01
加载中...