这题。。。咋说呢,我们没看到所有边都和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