https://v.qzyz.com/problem/show/2711

没有题解我来发一个。

有环删安全值最小，相当于维护安全值的最大生成树;

安全值一样删最后，相当于以排列中的位置为第二关键字(升序)。

如果要求最大价值，就按安全值为第一关键字(降序)，价值为第二关键字(降序)排序做kruscal

但还要让排列的字典序最小

就贪心枚举每一位，从小到大枚举这一位填什么，然后判断是否可以达到最大价值。

判断的方法就是按安全值为第一关键字(降序)，排列中的位置为第二关键字(升序)，价值为第三关键字(降序)排序做kruscal
(对不在排列中的边就令他们位置都为最大)
(一开始我令在排列中的边位置都为最小。。居然还过了)

每次只改变一条边的位置，不用重新排序，可以直接特判

所以复杂度$O(m^3)$

(好像说有$mlogm$的做法？我不会)

#include<bits/stdc++.h>
using namespace std;

#define rep(i,l,r) for(int i=l;i<=r;++i)
#define rep0(i,n) for(int i=0;i<n;++i)

#define gc (c=getchar())
int read()
{
    char c;
    while(gc<'0');
    int x=c-'0';
    while(gc>='0')x=x*10+c-'0';
    return x;
}

const int N=300+5;
int n,m,fa[N];
struct edge
{
    int x,y,p,c,dy;
}l[N];int nex[N],pre[N];
int dy[N];
bool operator <(const edge &e1,const edge &e2)
{
    if(e1.p!=e2.p) return e1.p>e2.p;
    return e1.c>e2.c;
}
int ans;

namespace get
{
int ans;
int find(int x)
{
    return fa[x]==0?x:fa[x]=find(fa[x]);
}
void add(int i)
{
    edge *it=l+i;
    int x=find(it->x),y=find(it->y);
    if(x==y)return ;
    fa[x]=y;ans+=it->c;
}
int g(int x)
{
    memset(fa+1,0,n*sizeof(int));
    ans=0;
    int i=1;
    while(i<=m)
    {
        if(i==pre[x])add(x);
        int j=nex[i];
        rep(k,i,j-1)add(k);
        i=j;
    }
    return ans;
}
};

int main()
{
    freopen("1.in","r",stdin);
    cin>>n>>m;
    rep(i,1,m)l[i]=(edge){read(),read(),read(),read(),i};
    sort(l+1,l+m+1);
    rep(i,1,m)dy[l[i].dy]=i;
    nex[m]=m+1;
    for(int i=m;--i;)
    if(l[i].p==l[i+1].p) nex[i]=nex[i+1];
    else nex[i]=i+1;
    nex[0]=1;
    rep(i,1,m)
    if(nex[i-1]==i)
    rep(j,i,nex[i]-1)
     pre[j]=i;

    ans=get::g(0);
    cout<<ans<<endl;
    static bool in[N];
    int top=0;
    while(++top<=m)
    {
        int i=0;
        while(++i<=m)
        if(!in[i])
        {
            in[i]=1;
            int x=dy[i];
            if(get::g(x)==ans)
            {
               int j=pre[x];
               while(x!=j)
               {
                 swap(l[x],l[x-1]);swap(dy[l[x].dy],dy[l[x-1].dy]);
                 --x;
               }
               while(++j<nex[x]) pre[j]=x+1;
               nex[x]=x+1;
               break;
            }
            in[i]=0;
        }
        printf("%d ",i);
    }
}