请选择 进入手机版 | 继续访问电脑版

全国大学生算法设计与编程挑战赛 (秋季赛)——正式赛 | H: 最

[复制链接]
期待幸福 发表于 2020-12-31 18:09:49 | 显示全部楼层 |阅读模式 打印 上一主题 下一主题
最大化-max

Description

 
有一张NN个点的无向图,要求给每个点分配一个标号,使得任意一条边两端的点的标号差(绝对值)不能凌驾给出的常数 DD ,要求在此根本上最大化标号的最大值减最小值.如果答案为 +\infin+∞,则输出 -1.
Input
 
第一行两个个数字 n,Dn,D
接下来 nn 行,每行 nn 个数字,第ii行jj列的数字便是11,表现存在一条从 ii 到 jj 的无向边。
Output
 
一行一个数字,表现答案
Sample Input 1 
  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
复制代码
Sample Output 1
  1. -1
复制代码
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
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则


专注素材教程免费分享
全国免费热线电话

18768367769

周一至周日9:00-23:00

反馈建议

27428564@qq.com 在线QQ咨询

扫描二维码关注我们

Powered by Discuz! X3.4© 2001-2013 Comsenz Inc.( 蜀ICP备2021001884号-1 )