• 周四. 5月 30th, 2024

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

[hdu6990]Directed Minimum Spanning Tree

admin

11月 28, 2021

模板题:在有向图中,对每一个点求以其为根的最小(外向)生成树

(当图是强连通时)可以使用朱刘算法,算法过程如下:

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

《[hdu6990]Directed Minimum Spanning Tree》有6个想法
  1. 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

  2. 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

  3. 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.

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注