先给出部分分的做法：离线并查集+点染色
排个序，每次往里面加即可。很显然偶环就是0（把相同颜色的没有连边的点扔一起），奇环就是最大边权（必须有两个连边的放一起）。
由于边权排过序了，所以两两之间的边一定是最小的。
1 #include<cstdio> 2 #include<queue> 3 #include<algorithm> 4 #define it register int 5 #define il inline 6 using namespace std; 7 const int N=1000005; 8 int n,m,Q,h[N],nxt[N],adj[N],w[N],f[N],u,v,x,t,p[N],maxn,ctg,s[N],tg[N],fa[N]; 9 bool inq[N],tag[N]; 10 struct ky{ 11 int u,v,x,id; 12 bool operator<(const ky&p)const{ 13 return x>p.x; 14 } 15 }a[N]; 16 il void fr(int &num) { 17 num=0;char c=getchar();int p=1; 18 while(c<'0'||c>'9') c=='-'?p=-1,c=getchar():c=getchar(); 19 while(c>='0'&&c<='9') num=num*10+c-'0',c=getchar(); 20 num*=p; 21 } 22 il void gc(char &c){ 23 c=getchar(); 24 while(c<'A'||c>'Z') c=getchar(); 25 } 26 il int fd(it x){ 27 return fa[x]==x?x:fa[x]=fd(fa[x]); 28 } 29 il void add(){ 30 it t1=fd(u),t2=fd(v); 31 if(t1==t2) return; 32 fa[t1]=t2,nxt[++t]=h[u],h[u]=t,adj[t]=v,nxt[++t]=h[v],h[v]=t,adj[t]=u; 33 } 34 il void dfs(it x){ 35 for(it i=h[x];i;i=nxt[i]) if(!(~f[adj[i]])) f[adj[i]]=f[x]^1,dfs(adj[i]); 36 } 37 il void qr(it now){ 38 for(it i=1;i<=n;++i) h[i]=0,f[i]=-1,fa[i]=i;t=0; 39 for(it i=1;i<=m;++i) if(a[i].id<=now&&!tag[a[i].id]) u=a[i].u,v=a[i].v,add(); 40 for(it i=1;i<=n;++i) if(f[i]==-1) f[i]=0,dfs(i); 41 for(it i=1;i<=m;++i) if(a[i].id<=now&&!tag[a[i].id]&&f[a[i].u]==f[a[i].v]){printf("%d ",a[i].x);return;} 42 puts("0"); 43 } 44 int main(){ 45 fr(n),fr(m),fr(Q); 46 for(it i=1;i<=m;++i) fr(a[i].u),fr(a[i].v),fr(a[i].x),a[i].id=i; 47 register char c; 48 for(it i=1;i<=Q;++i){ 49 gc(c); 50 if(c=='D') fr(p[++ctg]),tg[ctg]=1; 51 if(c=='A') ++m,fr(a[m].u),fr(a[m].v),fr(a[m].x),a[m].id=m; 52 if(c=='Q') s[++ctg]=m,tg[ctg]=-1; 53 } 54 sort(a+1,a+1+m); 55 for(it i=1;i<=ctg;++i) tg[i]==-1?qr(s[i]),0:tag[p[i]]=true; 56 return 0; 57 }
满分做法我不会。。这里给出sgygd2004大佬的优秀做法：线段树+分治
1 #include<bits/stdc++.h> 2 using namespace std; 3 int n,i,m,j,q,op[500005],x[500005],k,nc[700005],M,ok[10005],qnum,ed[700005],st[700005],limit[700005]; 4 char c[15]; 5 struct str{ 6 int u,v,w,x; 7 }a[700005]; 8 struct edge{ 9 int u,v; 10 }sta[700005]; 11 inline void read(int &x) 12 { 13 x=0; 14 char c=getchar(); 15 while(c<'0'||c>'9') 16 c=getchar(); 17 while(c>='0'&&c<='9') 18 { 19 x=x*10+c-'0'; 20 c=getchar(); 21 } 22 } 23 bool cmp(str a,str b) 24 { 25 return a.w>b.w; 26 } 27 int head[700005],Next[5000005],adju[5000005],adjv[5000005],nume,f[1005],dep[1005],top,numt[1005],t,vis[700005]; 28 edge tree[17][1005][1005]; 29 void Push(int x,int u,int v) 30 { 31 Next[++nume]=head[x]; 32 head[x]=nume; 33 adju[nume]=u; 34 adjv[nume]=v; 35 } 36 void modify(int i,int l,int r,int ll,int rr,int u,int v) 37 { 38 if(l>=ll&&r<=rr) 39 { 40 Push(i,u,v); 41 return; 42 } 43 int mid=l+r>>1; 44 if(mid>=ll) 45 modify(i<<1,l,mid,ll,rr,u,v); 46 if(mid<rr) 47 modify(i<<1|1,mid+1,r,ll,rr,u,v); 48 } 49 int tb=0; 50 int Find(int x) 51 { 52 if(f[x]==0) 53 { 54 tb=0; 55 return x; 56 } 57 f[x]=Find(f[x]); 58 tb^=dep[x]; 59 dep[x]=tb; 60 return f[x]; 61 } 62 void dfs(int i,int l,int r,int flag) 63 { 64 int td[1005],tf[1005]; 65 memcpy(tf,f,sizeof(tf)); 66 memcpy(td,dep,sizeof(td)); 67 int ttop=top; 68 for(int j=head[i];j!=0;j=Next[j]) 69 { 70 int x=Find(adju[j]),y=Find(adjv[j]); 71 if(x!=y) 72 { 73 sta[++top]=(edge){adju[j],adjv[j]}; 74 f[x]=y; 75 dep[x]=1; 76 } 77 else 78 if(((dep[adju[j]]^dep[adjv[j]])&1)==0) 79 flag=false; 80 } 81 if(l==r) 82 { 83 ok[i]=flag; 84 numt[l]=top; 85 for(int j=1;j<=top;j++) 86 tree[t][l][j]=sta[j]; 87 top=ttop; 88 memcpy(f,tf,sizeof(f)); 89 memcpy(dep,td,sizeof(dep)); 90 return; 91 } 92 int mid=l+r>>1; 93 dfs(i<<1,l,mid,flag); 94 dfs(i<<1|1,mid+1,r,flag); 95 top=ttop; 96 memcpy(f,tf,sizeof(f)); 97 memcpy(dep,td,sizeof(dep)); 98 } 99 int main() 100 { 101 freopen("redgreen.in","r",stdin); 102 freopen("redgreen.out","w",stdout); 103 read(n);read(m);read(q); 104 for(i=1;i<=m;i++) 105 { 106 read(a[i].u); 107 read(a[i].v); 108 read(a[i].w); 109 a[i].x=i; 110 } 111 k=m; 112 for(i=1;i<=q;i++) 113 { 114 scanf("%s",c); 115 if(c[0]=='D') 116 { 117 op[i]=1; 118 read(x[i]); 119 } 120 if(c[0]=='A') 121 { 122 op[i]=2; 123 x[i]=++k; 124 read(a[k].u); 125 read(a[k].v); 126 read(a[k].w); 127 a[k].x=k; 128 } 129 } 130 sort(a+1,a+1+k,cmp); 131 for(i=1;i<=k;i++) 132 nc[a[i].x]=i; 133 /*M=max(1,k/15); 134 for(i=1;i<=q;i++) 135 { 136 if(op[i]==0) 137 qnum++; 138 if(op[i]==1) 139 ed[nc[x[i]]]=qnum; 140 if(op[i]==2) 141 st[nc[x[i]]]=qnum+1; 142 } 143 for(i=1;i<=k;i++) 144 { 145 st[i]=max(1,st[i]); 146 if(ed[i]==0||ed[i]==qnum+1) 147 ed[i]=qnum; 148 } 149 for(t=1;t<=k;t+=M) 150 { 151 nume=0; 152 memset(head,0,sizeof(head)); 153 for(i=t;i<t+M&&i<=k;i++) 154 if(ed[i]!=0&&ed[i]>=st[i]) 155 modify(1,1,qnum,st[i],ed[i],a[i].u,a[i].v); 156 for(j=1;j<=qnum;j++) 157 if(ok[j]==0&&limit[j]==0) 158 limit[j]=(t-1)/M+1; 159 } 160 for(j=1;j<=qnum;j++) 161 if(limit[j]==0) 162 limit[j]=(t-1)/M+1;*/ 163 for(i=1;i<=m;i++) 164 vis[nc[i]]=1; 165 qnum=0; 166 for(t=1;t<=q;t++) 167 { 168 if(op[t]==2) 169 vis[nc[x[t]]]=1; 170 if(op[t]==1) 171 vis[nc[x[t]]]=0; 172 if(op[t]==0) 173 { 174 qnum++; 175 memset(f,0,sizeof(f)); 176 memset(dep,0,sizeof(dep)); 177 /*for(i=1;i<limit[qnum];i++) 178 { 179 bool flag=true; 180 for(j=1;j<=numt[i];j++) 181 { 182 int x=Find(tree[i][qnum][j].u),y=Find(tree[i][qnum][j].v); 183 if(x!=y) 184 { 185 f[x]=y; 186 dep[x]=1; 187 } 188 else 189 if(((dep[tree[i][qnum][j].u]^dep[tree[i][qnum][j].v])&1)==0) 190 flag=false; 191 } 192 if(!flag) 193 break; 194 } 195 limit[qnum]=i; 196 memset(f,0,sizeof(f)); 197 memset(dep,0,sizeof(dep)); 198 for(i=1;i<limit[qnum];i++) 199 { 200 bool flag=true; 201 for(j=1;j<=numt[i];j++) 202 { 203 int x=Find(tree[i][qnum][j].u),y=Find(tree[i][qnum][j].v); 204 if(x!=y) 205 { 206 f[x]=y; 207 dep[x]=1; 208 } 209 else 210 if(((dep[tree[i][qnum][j].u]^dep[tree[i][qnum][j].v])&1)==0) 211 flag=false; 212 } 213 if(!flag) 214 break; 215 } 216 for(i=limit[qnum]*M-M+1;i<=limit[qnum]*M&&i<=m;i++) 217 { 218 int x=Find(a[i].u),y=Find(a[i].v); 219 if(x!=y) 220 { 221 f[x]=y; 222 dep[x]=1; 223 } 224 else 225 if(((dep[a[i].u]^dep[a[i].v])&1)==0) 226 break; 227 }*/ 228 for(i=1;i<=k;i++) 229 if(vis[i]==1) 230 { 231 int x=Find(a[i].u); 232 int e=tb; 233 int y=Find(a[i].v); 234 e^=tb; 235 if(x!=y) 236 { 237 f[x]=y; 238 dep[x]=1^e; 239 } 240 else 241 { 242 if(((dep[a[i].u]^dep[a[i].v])&1)==0) 243 break; 244 } 245 } 246 printf("%d ",a[i].w); 247 } 248 } 249 }
upd:部分分的做法在我校OJ上可以通过所有测试数据。。。
只要数组大，咋写都不怕！只要常数小，哪里都敢交！