最大化-max
Description
有一张NN个点的无向图,要求给每个点分配一个标号,使得任意一条边两端的点的标号差(绝对值)不能凌驾给出的常数 DD ,要求在此根本上最大化标号的最大值减最小值.如果答案为 +\infin+∞,则输出 -1.
Input
第一行两个个数字 n,Dn,D
接下来 nn 行，每行 nn 个数字，第ii行jj列的数字便是11，表现存在一条从 ii 到 jj 的无向边。
Output
一行一个数字，表现答案
Sample Input 1
- 5 5760 1 1 0 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 1 0
Hint
2 \leq n \leq 50,0\leq D\leq 10002≤n≤50,0≤D≤1000
代码
[code]#include#define fi first#define se second#define mid (l+r>>1)#define endl '\n'using namespace std;typedef long long ll;typedef pairpii;typedef vectorvi;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){ queueq; 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); for(int i=1;i>n>>d; for(int i=1;iedg[j]; for(int i=1;i |
