清橙A1201 Will的烦恼

清橙A1201 Will的烦恼

谁能告诉我A1200怎么做QAQ……暴力只有十分QAQ

发现可以按长度分层，长度相同的分在一层，不同层之间边加入顺序不会相互影响。

长度从大到小排序，对于某一层，首先把已经连通的块缩成一个点，接下来按美丽程度把同一层的边排序。

接下来一条一条地加边做最小生成树。假如某条边加入后会形成环，那么环上其它边必须在它之后，这个可以用LCT维护。

输出的地方有一些细节。

具体实现见代码，如果有错误欢迎指出。

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;
const int INF=1e9;
const int maxn=150100;
int n,m;
int vec[maxn],ilem;
bool cg[maxn];
void push_in(int x)
{if(!cg[x]){vec[++ilem]=x;cg[x]=1;}
}
struct LCT{int l[maxn],r[maxn],f[maxn],rev[maxn],mx[maxn],val[maxn];int stk[100010],tp;void print(){for(int i=1;i<=n+m;i++)printf("h:%d,f=%d,l=%d,r=%dn",i,f[i],l[i],r[i]);printf("n");}void csh(){for(int i=0;i<maxn;i++){mx[i]=0;val[i]=0;}}void huifu(){int u;while(ilem){u=vec[ilem];l[u]=r[u]=f[u]=rev[u]=0;mx[u]=val[u]=0;ilem--;cg[u]=0;}}bool isroot(int h){if(!f[h]) return 1;if(l[f[h]]==h||r[f[h]]==h) return 0;return 1;}
/*    void push_up(int h){mn[h]=val[h];if(mn[l[h]]<mn[h]) mn[h]=mn[l[h]];if(mn[r[h]]<mn[h]) mn[h]=mn[r[h]];}
*/    void push_down(int h){if(mx[h]){if(l[h]&&mx[h]>mx[l[h]])mx[l[h]]=mx[h];if(r[h]&&mx[h]>mx[r[h]])mx[r[h]]=mx[h];if(mx[h]>val[h])val[h]=mx[h];mx[h]=0;}if(!rev[h]) return;swap(l[h],r[h]);rev[l[h]]^=1;rev[r[h]]^=1;rev[h]=0;}void rotate(int h){int fa=f[h],gfa=f[fa];if(fa==l[gfa]) l[gfa]=h;else if(fa==r[gfa]) r[gfa]=h;f[h]=gfa;if(h==l[fa]){l[fa]=r[h];f[r[h]]=fa;r[h]=fa;f[fa]=h;}else{r[fa]=l[h];f[l[h]]=fa;l[h]=fa;f[fa]=h;}
//        push_up(fa);push_up(h);}void splay(int h){int fa,gfa;tp=1;stk[1]=h;for(int i=h;!isroot(i);i=f[i])stk[++tp]=f[i];while(tp){push_down(stk[tp]);tp--;}while(!isroot(h)){fa=f[h];if(isroot(fa)){rotate(h);return;}gfa=f[fa];if((h==l[fa])^(fa==l[gfa])){rotate(h);rotate(h);}else{rotate(fa);rotate(h);}}}void access(int x){int s=0;while(x){splay(x);push_down(x);r[x]=s;s=x;x=f[x];}}void makeroot(int h){access(h);splay(h);rev[h]^=1;}void link(int x,int y){if(x==y) return;makeroot(x);f[x]=y;}void push_lazy(int s,int t,int v){//print();makeroot(t);access(s);splay(s);if(v>mx[s]) mx[s]=v;}int qury(int x){int res=val[x];if(mx[x]>res) res=mx[x];while(!isroot(x)){if(mx[f[x]]>res)res=mx[f[x]];x=f[x];}return res;}
}lct;
struct node{int bh;int s,t,l,v;
}a[100100];
struct SAK{int bh,frm;
};
bool operator < (SAK A,SAK B)
{return A.bh>B.bh;
}
priority_queue <SAK> pq;
vector<int> b[100100];
int zz[100100];
bool cmp1(node A,node B)
{return A.l>B.l;
}
bool cmp2(node A,node B)
{if(A.v==B.v)return A.bh>B.bh;return A.v>B.v;
}
bool cmp3(node A,node B)
{return A.bh<B.bh;
}
int f[50010];
int fa(int x)
{if(f[x]==x) return x;return f[x]=fa(f[x]);
}
int g[50010];
int ga(int x)
{if(g[x]==x) return x;return g[x]=ga(g[x]);
}
int wtf[100010],wt;
int main(){lct.csh();int s,t,l,v;scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){scanf("%d%d%d%d",&a[i].s,&a[i].t,&a[i].l,&a[i].v);a[i].bh=i;}for(int i=1;i<=n;i++)f[i]=g[i]=i;sort(a+1,a+m+1,cmp1);s=1,t=1;SAK sak;while(s<=m){while(t<m&&a[t+1].l==a[s].l)t++;sort(a+s,a+t+1,cmp2);for(int i=s;i<=t;i++){if(ga(a[i].s)!=ga(a[i].t)){lct.link(fa(a[i].s),n+i);lct.link(fa(a[i].t),n+i);push_in(fa(a[i].s));push_in(fa(a[i].t));push_in(n+i);wtf[++wt]=ga(a[i].s);g[ga(a[i].s)]=ga(a[i].t);}else{if(fa(a[i].s)!=fa(a[i].t))lct.push_lazy(fa(a[i].s),fa(a[i].t),a[i].bh); }}for(int i=s;i<=t;i++){l=lct.qury(n+i);if(!l){sak.bh=a[i].bh;sak.frm=a[i].bh;pq.push(sak);}elseb[l].push_back(a[i].bh);}sort(a+s,a+t+1,cmp3);while(wt){v=wtf[wt];f[v]=g[v];wt--;}lct.huifu();s=t+1;t=s;}for(int i=1;i<=m;i++)sort(b[i].begin(),b[i].end());while(!pq.empty()){sak&#p();pq.pop();printf("%d ",sak.bh);l=sak.frm;if(zz[l]<b[l].size()){sak.bh=b[l][zz[l]];sak.frm=l;zz[l]++;pq.push(sak);}}printf("n");
/*    for(int i=1;i<=m;i++){printf("%d:n",i);for(int j=0;j<b[i].size();j++)printf("%d ",b[i][j]);printf("n");}
*/    return 0;
}
/*
1 3 4 5 6 2 7 8
*/