【BZOJ 1791】 [Ioi2008]Island 岛屿

 1 #include<cstdio>
 2 #include<iostream>
 3 using namespace std;
 4 const int N=1000005;
 5 struct ee{int to,next,w;}e[N*2];
 6 long long head[N],c[N],f[N],du[N],d[N],b[N*2],a[N*2],q[2*N];
 7 int n,timer,cnt;
 8 long long ans;
 9 bool vis[N];
10 void ins(int u,int v,int w){
11     e[++cnt].to=v;e[cnt].next=head[u];e[cnt].w=w;head[u]=cnt;du[u]++;
12     e[++cnt].to=u;e[cnt].next=head[v];e[cnt].w=w;head[v]=cnt;du[v]++;
13 }
14  
15 void dfs(int now,int k){
16     c[now]=k;
17     for (int i=head[now];i;i=e[i].next){
18         int v=e[i].to;
19         if(!c[v]) dfs(v,k);
20     }
21 }
22  
23 void topsort(){
24     int l=0,r=0;
25     for (int i=1;i<=n;i++) if(du[i]==1) q[++r]=i;
26     while(l<r) {
27         int now=q[++l];
28         for (int i=head[now];i;i=e[i].next){
29             int v=e[i].to;
30             if(du[v]>1){
31                 du[v]--;
32                 d[c[now]]=max(d[c[now]],f[now]+f[v]+e[i].w);
33                 f[v]=max(f[v],f[now]+e[i].w);
34                 if(du[v]==1)q[++r]=v;
35             }
36         }
37     }
38 }
39  
40 void dp(int t,int x){
41     int m=0,y=x,i;
42     do{
43         a[++m]=f[y];du[y]=1;
44         for(i=head[y];i;i=e[i].next){
45             int v=e[i].to;
46             if(du[v]>1){
47                 b[m+1]=b[m]+e[i].w;
48                 y=e[i].to;
49                 break;
50             }
51         }
52     }while(i);
53     if(m==2){//
54         int l=0;
55         for (int i=head[y];i;i=e[i].next) 
56             if(e[i].to==x) l=max(l,e[i].w);
57         d[t]=max(d[t],f[x]+f[y]+l);
58         return;
59     }
60     for(int i=head[y];i;i=e[i].next){
61         int v=e[i].to;
62         if(v==x) {
63             b[m+1]=b[m]+e[i].w;
64             break;
65         }
66     }
67     for (int i=1;i<=m;i++){
68             a[i+m]=a[i];
69             b[m+i]=b[m+1]+b[i];
70         }
71     int l,r;
72     q[l=r=1]=1;
73     for (int i=2;i<2*m;i++){
74         while(l<=r&&i-q[l]>=m)l++;
75         d[t]=max(b[i]-b[q[l]]+a[i]+a[q[l]],d[t]);
76         while(l<=r&&a[q[r]]+b[i]-b[q[r]]<=a[i]) r--;
77         q[++r]=i;
78     }
79      
80 }
81  
82 int main(){
83     scanf("%d",&n);
84     int v,w;
85     for (int i=1;i<=n;i++){
86         scanf("%d%d",&v,&w);
87         ins(i,v,w);
88     }
89     for (int i=1;i<=n;i++) if (!c[i]) dfs(i,++timer);
90     topsort();
91     for (int i=1;i<=n;i++){
92         if(du[i]>1&&!vis[c[i]]) {
93             vis[c[i]]=1;
94             dp(c[i],i);
95             ans+=d[c[i]];
96         }
97     }
98     cout<<ans<<endl;
99 }