2013-2014 Winter Petrozavodsk Camp, Andrew Stankevich Contest 45 (ASC 45) F - Flights

这题。。。咋说呢,我们没看到所有边都和1有且仅有一条边相连,然后就一直卡着。。
思路就是除了和1相连的边,其他边随便给个值,和1相连的边看另一个点当前边权值和大小,越大就给个越大的权值

#include<stdio.h>
#define LOCAL
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 1e5+10;
struct E
{
    ll x,y;
}e[maxn];
struct Node
{
    ll id,x,num;
}s[maxn];ll n,m;
bool cmp(Node a,Node b)
{
    return a.x<b.x;
}
ll ans[maxn];
int main()
{
    #ifdef LOCAL
    freopen("flights.in","r",stdin);
	freopen("flights.out","w",stdout);
#endif
    while(scanf("%lld %lld",&n,&m)!=EOF)
   {
       if(n==0&&m==0) break;
       ll id=0;for(ll i=1;i<=n;i++) s[i].id=1,s[i].x=0;
        for(int i=1;i<=m;i++)
        {
            ll x,y;
            scanf("%lld %lld",&x,&y);
            if(x==1)
            {
                s[y].num=i;
            }
            else if(y==1) s[x].num=i;
            else
            {
                ++id;
                s[x].x+=id;
                s[y].x+=id;
                ans[i]=id;
            }

        }
        sort(s+2,s+1+n,cmp);
        for(int i=2;i<=n;i++)
        {
            ++id;
            ans[s[i].num]=id;
        }
        printf("Yes\n");
        for(ll i=1;i<=id;i++)
        {
            printf("%lld%c",ans[i],i==id?‘\n‘:‘ ‘);
        }
   }


}
/*
5 8
1 5
1 3
1 4
1 2
2 3
3 4
4 5
5 2
*/

2013-2014 Winter Petrozavodsk Camp, Andrew Stankevich Contest 45 (ASC 45) F - Flights

上一篇:c# 05抽象类


下一篇:c# 03 里式转换