[Codeforces g100520F][ASC 45]Flights

題目敘述
傳code

說明：
$SUM[i]$為城市$i$連出去的道路數字總和

可以注意到首都是和所有城市相連的
所以一定可以讓$SUM[1]$ (首都的數字總和) 最大，有個方法是把數字$(M-N+2)\sim(M)$分配給連到首都的道路

先不用確定$(M-N+2)\sim(M)$要分配給哪些道路
我們可以先把其他城市之間的道路隨便給一個數字
然後算好每個城市 (不包括首都$1$) 連出去的道路數字總和
將這些城市依照目前的道路數字總和排序
假設排序後的城市為$\{c_{1},c_{2},c_{3},...,c_{N-1}\}$

發現了嗎？
對於城市$c_{i}$，將$c_{i}$和首都相連的道路的數字設定成$M-N+1+i$
可以發現，我們可以保證$SUM[c_{i}]<SUM[c_{i+1}]<SUM[1],\forall i\in [1,N-2]$

時間複雜度：$O(M+N\log N)$

code:

#include<cstdio>
#include<cassert>
#include<vector>
#include<algorithm>
using namespace std;
struct Edge
{
    int a,b,val;
    Edge(){}
    Edge(const int _a,const int _b,const int _val):a(_a),b(_b),val(_val){}
};
vector<Edge>EDGE;
vector<int>ET[1000];
int N,M,SUM[1000];
int main()
{
    freopen("flights.in","r",stdin);
    freopen("flights.out","w",stdout);
//    freopen("in.txt","r",stdin);
    while(scanf("%d%d",&N,&M)==2)
    {
        if(N==0&&M==0)break;
        for(int i=0;i<N;i++)ET[i].clear();
        EDGE.clear();
        for(int i=0,a,b;i<M;i++)
        {
            scanf("%d%d",&a,&b),a--,b--;
            EDGE.push_back(Edge(a,b,0));
            ET[a].push_back(i),ET[b].push_back(i);
        }
        for(int i=0;i<N;i++)SUM[i]=0;
        int count=0;
        for(int i=0;i<M;i++)
        {
            Edge &e=EDGE[i];
            if(e.a!=0&&e.b!=0)
            {
                count++;
                e.val=count;
                SUM[e.a]+=count,SUM[e.b]+=count;
            }
        }
        assert((int)ET[0].size()==N-1&&count+(N-1)==M);
        vector<int>order;
        for(int i=1;i<N;i++)order.push_back(i);
        sort(order.begin(),order.end(),[](const int a,const int b)->bool{return SUM[a]<SUM[b];});
        static int eis[1000];
        for(int i=0;i<N-1;i++)eis[max(EDGE[ET[0][i]].a,EDGE[ET[0][i]].b)]=ET[0][i];
        for(const int i:order)
        {
            Edge &e=EDGE[eis[i]];
            count++;
            e.val=count;
            assert(e.a==0||e.b==0);
            SUM[e.a]+=count,SUM[e.b]+=count;
        }
        assert(count==M);
        puts("Yes");
        for(int i=0;i<M;i++)
        {
            if(i)putchar(' ');
            printf("%d",EDGE[i].val);
        }
        puts("");
        sort(SUM,SUM+N);
        for(int i=1;i<N;i++)assert(SUM[i-1]<SUM[i]);
    }
    return 0;
}