模板题：在有向图中，对每一个点求以其为根的最小（外向）生成树
（当图是强连通时）可以使用朱刘算法，算法过程如下：
1.对每一个节点，选择指向该点的边权最小的边，即得到一张子图
2.任选这张子图的一个简单环，并对这个环执行以下操作——
(1)对于环上的边$(u,v)$，将所有以$v$为终点的边边权减去$(u,v)$的边权
(2)新建一个点为将环上所有点合并后的结果，并删除新点的自环
3.重复此过程，直至仅剩下一个点
（不难证明第1步中每一个点入度都非0，第2步中一定存在一个环）
在此过程中，再另外维护一棵树：在第2.(2)中，环上的每一个点向新建的点连一条边权为其对应边（即环上指向该点的边）的边权的边，显然这是一棵内向树，且根即为最后剩下的节点
此时，每一个节点的答案即树上的边权和-其到根路径上的边权和
下面，问题即如何（快速）实现之前的过程——
先对每一个点的边集（指到该点的边）维护一个可并堆，显然即可支持1的查询和2.(2)的合并，2.(1)的修改也可以用懒标记实现
此时，考虑从任意一点dfs，由于每一个点入度都非0，那么不断选择”指向自己的边权最小的边”，当重复访问一个节点时即可进行缩点，缩点后继续递归即可
另外，图并不一定强连通，这个问题可以通过加入边$(1,2,infty),(2,3,infty),…,(n,1,infty)$来解决，若最终某个点的答案为$infty$即说明不存在以该点为根的生成树，进而图即变为强连通的
综上，总复杂度为$o(nlog n)$，可以通过
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 200005 4 #define ll long long 5 #define ull unsigned ll 6 #define pil pair<int,ll> 7 #define fi first 8 #define se second 9 vector<int>v[N<<1]; 10 int V,t,n,m,x,y,z,rt[N],ls[N<<1],rs[N<<1],fa[N],st[N],vis[N]; 11 ll tag[N<<1],Val[N]; 12 ull ans[N]; 13 pil val[N<<1],pos[N]; 14 int find(int k){ 15 if (k==fa[k])return k; 16 return fa[k]=find(fa[k]); 17 } 18 void upd(int k,ll x){ 19 tag[k]+=x,val[k].se+=x; 20 } 21 void down(int k){ 22 if (!tag[k])return; 23 if (ls[k])upd(ls[k],tag[k]); 24 if (rs[k])upd(rs[k],tag[k]); 25 tag[k]=0; 26 } 27 int New(int x,ll z){ 28 int k=++V; 29 ls[k]=rs[k]=tag[k]=0; 30 val[k]=make_pair(x,z); 31 return V; 32 } 33 int merge(int k1,int k2){ 34 if ((!k1)||(!k2))return k1+k2; 35 if (val[k1].se>val[k2].se)swap(k1,k2); 36 down(k1); 37 rs[k1]=merge(rs[k1],k2); 38 swap(ls[k1],rs[k1]); 39 return k1; 40 } 41 void add(int x,int y,ll z){ 42 rt[y]=merge(rt[y],New(x,z)); 43 } 44 void del(int x){ 45 down(rt[x]); 46 rt[x]=merge(ls[rt[x]],rs[rt[x]]); 47 } 48 void dfs(int x,ull s){ 49 if (x<=n)ans[x]=s; 50 for(int i=0;i<v[x].size();i++)dfs(v[x][i],s-Val[v[x][i]]); 51 } 52 int main(){ 53 scanf("%d",&t); 54 while (t--){ 55 scanf("%d%d",&n,&m); 56 V=st[0]=ans[0]=0; 57 for(int i=1;i<=(n<<1);i++){ 58 fa[i]=i; 59 rt[i]=vis[i]=0; 60 v[i].clear(); 61 } 62 for(int i=1;i<=m;i++){ 63 scanf("%d%d%d",&x,&y,&z); 64 add(x,y,z); 65 } 66 for(int i=1;i<=n;i++)add(i,i%n+1,1e14); 67 st[++st[0]]=1,vis[1]=1; 68 int nn=n; 69 while (1){ 70 x=st[st[0]]; 71 while ((rt[x])&&(find(val[rt[x]].fi)==x))del(x); 72 if (!rt[x])break; 73 y=find(val[rt[x]].fi); 74 Val[x]=val[rt[x]].se,del(x); 75 if (rt[x])upd(rt[x],-Val[x]); 76 if (!vis[y]){ 77 st[++st[0]]=y,vis[y]=1; 78 continue; 79 } 80 nn++; 81 while (1){ 82 v[nn].push_back(x); 83 fa[x]=nn,rt[nn]=merge(rt[nn],rt[x]); 84 if (x==y){ 85 st[st[0]]=nn,vis[nn]=1; 86 break; 87 } 88 x=st[--st[0]]; 89 } 90 } 91 for(int i=1;i<nn;i++)ans[0]+=Val[i]; 92 dfs(nn,ans[0]); 93 for(int i=1;i<=n;i++){ 94 if (ans[i]>1e14)printf("-1 "); 95 else printf("%llu ",ans[i]); 96 } 97 } 98 return 0; 99 }
View Code
Wow, wonderful blog format! How lengthy have you ever been blogging for?
you make running a blog look easy. The full glance of your web site is
fantastic, let alone the content material! You can see similar here najlepszy sklep
Hello, its pleasant piece of writing about media print,
we all know media is a impressive source
of facts. I saw similar here: Najlepszy sklep
continuously i used to read smaller articles or reviews that also clear
their motive, and that is also happening with this post which I am
reading now. I saw similar here: Ecommerce
Hi there! Do you know if they make any plugins to assist with Search
Engine Optimization? I’m trying to get my blog to rank for
some targeted keywords but I’m not seeing very good success.
If you know of any please share. Thank you! You can read similar article here: Ecommerce
Monitoruj telefon z dowolnego miejsca i zobacz, co dzieje się na telefonie docelowym. Będziesz mógł monitorować i przechowywać dzienniki połączeń, wiadomości, działania społecznościowe, obrazy, filmy, WhatsApp i więcej. Monitorowanie w czasie rzeczywistym telefonów, nie jest wymagana wiedza techniczna, nie jest wymagane rootowanie.
celecoxib 200 mg price