最大化-max
Description
有一张NN个点的无向图,要求给每个点分配一个标号,使得任意一条边两端的点的标号差(绝对值)不能超过给出的常数 DD ,要求在此基础上最大化标号的最大值减最小值.如果答案为 +\infin+∞,则输出 -1.
Input
第一行两个个数字 n,Dn,D
接下来 nn 行,每行 nn 个数字,第ii行jj列的数字等于11,表示存在一条从 ii 到 jj 的无向边。
Output
一行一个数字,表示答案
Sample Input 1
5 576
0 1 1 0 0
1 0 0 0 0
1 0 0 0 0
0 0 0 0 1
0 0 0 1 0
Sample Output 1
-1
Hint
2 \leq n \leq 50,0\leq D\leq 10002≤n≤50,0≤D≤1000
代码
#include<bits/stdc++.h>
#define fi first
#define se second
#define mid (l+r>>1)
#define endl '\n'
using namespace std;
typedef long long ll;
typedef pair<int, int>pii;
typedef vector<int>vi;
struct tri {int a, b, c;};
const int N = 1e5 + 10;
const int inf = 0x3f3f3f3f;
const ll linf = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9 + 7;
int n,d;
bool edg[100][100];
int father[100];
int ff(int a){return a==father[a]?a:father[a]=ff(father[a]);}
int bfs(int a)
{
queue<int>q;
int dep[100]{};
q.push(a);
dep[a]=1;
int ret=0;
while(!q.empty())
{
int u=q.front();q.pop();
ret=max(ret,dep[u]);
for(int i=1;i<=n;i++)if(edg[i][u]&&!dep[i])
{
q.push(i);
dep[i]=dep[u]+1;
}
}
return ret-1;
}
int main()
{
ios::sync_with_stdio(0), cin.tie(0);
// freopen("in.txt", "r", stdin);
cin>>n>>d;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
cin>>edg[i][j];
for(int i=1;i<=n;i++)
father[i]=i;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)if(edg[i][j])
{
int fa=ff(i),fb=ff(j);
if(fa!=fb)
{
father[fa]=fb;
}
}
}
for(int i=2;i<=n;i++)
{
if(ff(i)!=ff(1))
{
cout<<-1;
return 0;
}
}
int ans=0;
for(int i=1;i<=n;i++)
{
ans=max(ans,bfs(i));
}
cout<<ans*d;
return 0;
}