http://acm.timus.ru/problem.aspx?space=1&num=1888
先分成幾個(gè)連通塊?? 然后枚舉每個(gè)點(diǎn)為起點(diǎn)? 計(jì)算它所在的連通塊以它為起點(diǎn)得到的差?（可能不存在）然后更新此連通塊的最大差
如果某個(gè)連通塊的最大差 不存在 則無解
如果每個(gè)連通塊的最大差都存在 則需要分兩種情況
如果只有一個(gè)連通塊? 則這個(gè)連通塊的最大差就是最終的最大差
如果有多個(gè)連通塊? 則最大差就是49? 因?yàn)槊總€(gè)聯(lián)通塊的起點(diǎn)不確定
代碼：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<map>
#include<vector>
#include<stack>
#include<set>
#include<map>
#include<queue>
#include<algorithm>
#include<cmath>
#define LL long long
#define sint short int
//#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
const int N=105;
const int INF=0x3f3f3f3f;
int head[N],I;
struct node
{
int j,next;
}side[N*N];
int d[N];//等級(jí)
int v[N];//屬于第幾個(gè)聯(lián)通圖
int M[N],s[N],m;//m,有幾個(gè)聯(lián)通圖 s[]第幾個(gè)聯(lián)通圖最好以第幾個(gè)點(diǎn)為起點(diǎn) M[]最大差距
void add(int i,int j)
{
side[I].j=j;
side[I].next=head[i];
head[i]=I++;
}
void dfs(int x,int k)
{
v[x]=k;
for(int t=head[x];t!=-1;t=side[t].next)
{
int j=side[t].j;
if(v[j]==-1)
{
dfs(j,k);
}
}
}
int bfs(int x1,int st)
{
queue<int>qt;
qt.push(x1);
d[x1]=st;
int k=0;
while(!qt.empty())
{
int x=qt.front();
qt.pop();
k=max(k,d[x]);
for(int t=head[x];t!=-1;t=side[t].next)
{
int j=side[t].j;
if(v[j]!=v[x])
continue;
if(d[j]!=0&&abs(d[j]-d[x])!=1)
return -1;
if(d[j]!=0&&abs(d[j]-d[x])==1)
continue;
d[j]=d[x]+1;
qt.push(j);
}
}
return (k-st);
}
int main()
{
//freopen("data.in","r",stdin);
int n,p;
while(cin>>n>>p)
{
memset(head,-1,sizeof(head));
I=0;
while(n--)
{
int l,r;
cin>>l>>r;
add(l,r);
add(r,l);
}
memset(v,-1,sizeof(v));
m=0;
for(int i=1;i<=p;++i)
if(v[i]==-1)
dfs(i,m++);
memset(M,-1,sizeof(M));
memset(s,-1,sizeof(s));
for(int i=1;i<=p;++i)
{
memset(d,0,sizeof(d));
int k=bfs(i,1);
if(k!=-1)
{
int l=v[i];
if(k>M[l])
{M[l]=k;s[l]=i;}
}
}
bool flag=true;
for(int i=0;i<m;++i)
if(M[i]==-1)
flag=false;
if(flag==false)
{cout<<"-1"<<endl;continue;}
memset(d,0,sizeof(d));
if(m==1)
{
cout<<M[0]<<endl;
bfs(s[0],1);
}else
{
cout<<"49"<<endl;
bfs(s[0],1);
for(int i=1;i<m;++i)
bfs(s[i],50-M[i]);
}
for(int i=1;i<=p;++i)
cout<<d[i]<<" ";
cout<<endl;
}
return 0;
}
更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號(hào)聯(lián)系： 360901061
您的支持是博主寫作最大的動(dòng)力，如果您喜歡我的文章，感覺我的文章對(duì)您有幫助，請(qǐng)用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點(diǎn)擊下面給點(diǎn)支持吧，站長非常感激您！手機(jī)微信長按不能支付解決辦法：請(qǐng)將微信支付二維碼保存到相冊(cè)，切換到微信，然后點(diǎn)擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對(duì)您有幫助就好】元
