1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122
| #include<cstdio> #include<cstring> #include<algorithm> using namespace std;
inline int Read(){ register int r=0,c=getchar(); while(c<'0' || '9'<c) c=getchar(); while('0'<=c && c<='9') r=(r<<1)+(r<<3)+c-'0',c=getchar(); return r; }
#define cs const int & const int N=50005,M=100005;
struct GRAPH{ int head[N],to[N<<1],nxt[N<<1],ncnt; void AddEdge(cs u,cs v){ int p=++ncnt,q=++ncnt; nxt[p]=head[u],to[p]=v,head[u]=p; nxt[q]=head[v],to[q]=u,head[v]=q; } inline int operator [](cs u){return head[u];} }Gr;
struct DSU{ int fa[N]; void Init(int siz){for(int i=1;i<=siz;i++) fa[i]=i;} inline int Find(cs u){return fa[u]==u? u:fa[u]=Find(fa[u]);} inline bool Merge(int u,int v){ u=Find(u),v=Find(v); if(u==v) return false; fa[u]=v; return true; } }Ds;
int n,m,org; int edg[M][3],id[M],anc[N][20],dep[N],tag[N]; bool del[M];
inline bool cmp(cs a,cs b){return edg[a][2]<edg[b][2];} void DFS(cs u,cs fa){ anc[u][0]=fa,dep[u]=dep[fa]+1; for(int i=1;i<20;i++) anc[u][i]=anc[anc[u][i-1]][i-1]; for(int it=Gr[u];it;it=Gr.nxt[it]){ int v=Gr.to[it]; if(v==fa) continue; DFS(v,u); } } int LCA(int u,int v){ if(dep[u]<dep[v]) swap(u,v); for(int i=19;i>=0;i--) if(dep[anc[u][i]]>=dep[v]) u=anc[u][i]; if(u==v) return u; for(int i=19;i>=0;i--) if(anc[u][i]!=anc[v][i]) u=anc[u][i],v=anc[v][i]; return anc[u][0]; } void Mark(int u,int v,int len){ int lca=LCA(u,v); while(true){ u=Ds.Find(u); if(dep[u]<=dep[lca]) break; tag[u]=len; Ds.Merge(u,anc[u][0]); } while(true){ v=Ds.Find(v); if(dep[v]<=dep[lca]) break; tag[v]=len; Ds.Merge(v,anc[v][0]); } } int main(){ n=Read(),m=Read(); Ds.Init(n); for(int i=1;i<=m;i++){ for(int j=0;j<3;j++) edg[i][j]=Read(); id[i]=i; } sort(id+1,id+1+m,cmp); int ecnt=0; for(int I=1;I<=m;I++){ int i=id[I]; if(Ds.Merge(edg[i][0],edg[i][1])){ org+=edg[i][2]; Gr.AddEdge(edg[i][0],edg[i][1]); del[i]=true; ecnt++; } } DFS(1,0); Ds.Init(n); memset(tag,-1,sizeof tag); for(int I=1;I<=m;I++){ int i=id[I]; if(del[i]) continue; Mark(edg[i][0],edg[i][1],edg[i][2]); } int q=Read(); while(q--){ int i=Read(),p; if(ecnt<n-1){ printf("Not connected\n"); continue; } if(!del[i]) printf("%d\n",org); else{ if(dep[edg[i][0]]<dep[edg[i][1]]) p=edg[i][1]; else p=edg[i][0]; if(~tag[p]) printf("%d\n",org-edg[i][2]+tag[p]); else printf("Not connected\n"); } } return 0; }
|