Pilot Work Experience （URAL 1888 并查集+floyd）

Pilot Work Experience

Time Limit: 1000MS

Memory Limit: 65536KB

64bit IO Format: %I64d & %I64u

Submit Status

Description

Leonid had  n Oceanic Airlines flights during his business trip. He studied the latest issue of the monthly on-board magazine of this company from cover to cover. In particular, he learned about the rules of forming an airplane crew. It turned out that the work experience of the captain (i.e., the number of complete years of work in civil aviation) was always greater by exactly one than the work experience of the second pilot.

The Oceanic Airlines company does not disclose information on the work experience of their pilots. Leonid is interested in the largest possible difference between the work experiences of pilots on the flights he had. He has written the names of the two pilots on each flight but couldn't remember who was the captain and who was the second pilot. Leonid assumes that the work experience of each pilot is in the range from 1 to 50 years and that the work experiences didn't change in the period between his first and last flights with Oceanic Airlines.

Help Leonid use the available information to find out the maximum possible difference in the work experiences of pilots on the flights he had.

Input

The first line contains integers  n and  p, which are the number of flights Leonid had and the number of pilots flying the planes on these flights (2 ≤  n ≤ 1 000; 2 ≤  p ≤ 50). The pilots are numbered from 1 to   p. In the  ith of the following  n lines you are given two different integers denoting the pilots of the  ith flight.

Output

In the first line output the maximum possible difference in the work experiences of the pilots. In the second line output  p integers. The  ith integer must be the work experience of the  ith pilot. If there are several possible answers, output any of them. If Leonid is wrong in his assumptions or his data are incorrect, output “-1”.

Sample Input

input	output
4 4 1 2 3 1 2 4 3 4	2 1 2 2 3
3 3 1 2 2 3 1 3	-1

Source

Problem Author: Magaz Asanov 
Problem Source: NEERC 2011, Eastern subregional contest 

题意： 有n个航班，p个飞行员，每个航班要两个机长一起飞，一个机长一个副机长，现在每个机长的有一个经验值，并且正机长比副机长的经验值大1，现在不知道每个机长的经验值，只知道每个航班是那两个机长飞的，要求给每个机长规定一个经验值，并且尽量要最小值与最大值之差最大，输出任意一组解，若不存在解输出-1.

思路：在训练赛过程中我的思路是最短路，如果存在可行解并且图是联通的，那么差值的最大值为最短路中的最大值，这个就很好处理了，求一遍floyd再求出mp[i][j]的最大值并记录下起点和终点，起点处的经验值为1，那其他点的经验值为该点到起点的距离+1，这个应该很好理解；如果图是不连通的，那么把其中一个集合内的任意一点s的经验值赋为1使它最小，其他集合选择任意一点s赋为50,使它最大。好，怎样判断时候存在解呢？我当时想到的是带权并查集，这个就可以用并查集来判断是否有解，就和poj 2492 A Bug‘s Life找同性恋的一样。哎，比赛时手抖把并查集的num数组初始化为1了，WA到死=-=

下来后看到网上都是dfs+bfs做的，以后补上。

代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#include<string>
#include<iostream>
#include<queue>
#include<cmath>
#include<map>
#include<stack>
#include<set>
using namespace std;
#define REPF( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define REP( i , n ) for ( int i = 0 ; i < n ; ++ i )
#define CLEAR( a , x ) memset ( a , x , sizeof a )
const int INF=0x3f3f3f3f;
typedef long long LL;

const int maxn = 1000;
int mp[maxn][maxn];
int n,p;
int father[maxn],num[maxn];
bool ok;
vector<int>g[maxn];
int cnt;
bool vis[maxn];
int ans[maxn];

void init()
{
    for (int i=0;i<maxn;i++)
    {
        father[i]=i;
        num[i]=0;       //这里开始赋的1，作死
    }
}

int find_father(int x)
{
    if (x==father[x]) return x;
    int t=father[x];
    father[x]=find_father(father[x]);
    num[x]=(num[x]+num[t])%2;
    return father[x];
}

void Union(int a,int b)
{
    int fa=find_father(a);
    int fb=find_father(b);
    if (fa==fb)
    {
        if ((num[a]+num[b]+2)%2==0)
            ok=false;
        return ;
    }
    father[fa]=fb;
    num[fa]=(num[b]-num[a]+1)%2;
    return ;
}

void floyd()    //floyd求最短路
{
    for (int k=1;k<=p;k++)
    {
        for (int i=1;i<=p;i++)
        {
            if (mp[i][k]==INF) continue;
            for (int j=1;j<=p;j++)
            {
                if (mp[k][j]==INF) continue;
                if (mp[i][j]>mp[i][k]+mp[k][j])
                    mp[i][j]=mp[i][k]+mp[k][j];
            }
        }
    }
}

void ffd()      //分离集合
{
    cnt=0;
    memset(vis,false,sizeof(vis));
    for (int i=0;i<maxn;i++)
        g[i].clear();
    int x;
    for (int i=1;i<=p;i++)
    {
        x=find_father(i);
        if (!vis[x])
        {
            vis[x]=true;
            cnt++;
        }
        g[x].push_back(i);
    }
}

void solve()
{
    ffd();
    floyd();
    if (cnt==1) //如果只有一个集合就找出最短路中的最长的
    {
        int Max=-1,s,t;
        for (int i=1;i<=p;i++)
        {
            for (int j=1;j<=p;j++)
            {
                if (i!=j&&mp[i][j]!=INF&&Max<mp[i][j])
                {
                    Max=mp[i][j];
                    s=i;
                    t=j;
                }
            }
        }
        mp[s][s]=0;
        printf("%d\n",mp[s][t]);
        printf("%d",mp[1][s]+1);
        for (int i=2;i<=p;i++)
            printf(" %d",mp[i][s]+1);
        printf("\n");
        return ;
    }
    int flag=1;
    for (int i=1;i<=p;i++)
    {
        if (g[i].size()==0) continue;
        if (flag)   //找一个集合赋最小值1
        {
            flag=0;
            int ss=g[i][0];
            ans[ss]=1;
            for (int j=1;j<g[i].size();j++)
                ans[g[i][j]]=mp[ss][g[i][j]]+1;
        }
        else    //其他集合赋最大值50
        {
            int ss=g[i][0];
            ans[ss]=50;
            for (int j=1;j<g[i].size();j++)
                ans[g[i][j]]=50-mp[ss][g[i][j]];
        }
    }
    printf("49\n");
    printf("%d",ans[1]);
    for (int i=2;i<=p;i++)
        printf(" %d",ans[i]);
    printf("\n");
    return ;
}

int main()
{
    int i,j,a,b;
    while (~scanf("%d%d",&n,&p))
    {
        init();
        ok=true;
        memset(mp,INF,sizeof(mp));
        for (i=0;i<n;i++)
        {
            scanf("%d%d",&a,&b);
            mp[a][b]=mp[b][a]=1;
            if (!ok) continue;
            Union(a,b);
        }
        if (!ok)
        {
            printf("-1\n");
            continue;
        }
        solve();
    }
    return 0;
}
/*
12 11
1 2
1 3
3 4
2 4
8 9
8 10
10 11
6 8
7 11
4 5
5 7
5 6
*/