题目大意
给定一个n个点m条边的有向图，以n为源点.对于一个点u，求在所有n->u的路径上都出现的点的编号之和.
n <= 50000,m <= 1000000
题解
终于有时间来学支配树了。
支配树裸题，直接用支配树模板去搞就好了。 关于支配树，我正在写这个ppt 写好了我把链接发到这个博客上有想看的可以看 (不知不觉，一个大坑) UPD : 课件写好了，想要看的可以私信~~#include#include #include #include using namespace std;typedef long long ll;inline void read(int &x){ x=0;static char ch;static bool flag;flag = false; while(ch=getchar(),ch<'!');if(ch == '-') ch=getchar(),flag = true; while(x=10*x+ch-'0',ch=getchar(),ch>'!');if(flag) x=-x;}#define rg register int#define rep(i,a,b) for(rg i=(a);i<=(b);++i)#define per(i,a,b) for(rg i=(a);i>=(b);--i)const int maxn = 50010;const int maxm = 100010;struct Graph{ struct Edge{ int to,next; }G[maxm]; int head[maxn],cnt; void clear(){ memset(head,0,sizeof head); cnt = 0; } void add(int u,int v){ G[++cnt].to = v; G[cnt].next = head[u]; head[u] = cnt; }}ori,inv,nwg;int ufa[maxn],pos[maxn],ido[maxn],sdo[maxn];int find(int x){ if(x == ufa[x]) return ufa[x]; int r = find(ufa[x]); if(sdo[pos[ufa[x]]] < sdo[pos[x]]) pos[x] = pos[ufa[x]]; return (ufa[x] = r);}inline int eval(int x){ find(x);return pos[x];}int n,m,dfn[maxn],seq[maxn],dfs_clock;int fa[maxn];void dfs(int u){ dfn[u] = ++ dfs_clock; seq[dfs_clock] = u; sdo[u] = dfs_clock; for(int i = ori.head[u],v;i;i = ori.G[i].next){ v = ori.G[i].to; if(dfn[v]) continue; fa[v] = u; dfs(v); }}int sum[maxn];void dfs(int u,int f){ for(rg i = nwg.head[u],v;i;i=nwg.G[i].next){ v = nwg.G[i].to; if(v == f) continue; sum[v] = sum[u] + v; dfs(v,u); }}vector ve[maxn];int main(){ while(scanf("%d%d",&n,&m) != EOF){ rep(i,1,n) ufa[i] = i,pos[i] = i; ori.clear();inv.clear();nwg.clear(); rep(i,1,n) ve[i].clear(),dfn[i] = seq[i] = ido[i] = sdo[i] = sum[i] = fa[i] = 0; dfs_clock = 0; int u,v; rep(i,1,m){ read(u);read(v); ori.add(u,v); inv.add(v,u); } dfs(n); per(id,dfs_clock,2){ u = seq[id]; for(int i = inv.head[u];i;i=inv.G[i].next) if(dfn[inv.G[i].to]) sdo[u] = min(sdo[u],sdo[eval(inv.G[i].to)]); ve[seq[sdo[u]]].push_back(u); int f = fa[u];ufa[u] = fa[u]; for(vector ::iterator it = ve[f].begin();it != ve[f].end();++it){ int x = eval(*it); ido[*it] = sdo[*it] == sdo[x] ? f : x; }ve[f].clear(); } rep(i,2,dfs_clock) u = seq[i],ido[u] = ido[u] == seq[sdo[u]] ? ido[u] : ido[ido[u]]; rep(i,1,n-1) nwg.add(ido[i],i);sum[n] = n; dfs(n,n); rep(i,1,n){ printf("%d",sum[i]); if(i != n) putchar(' '); else putchar('\n'); } } return 0;}