精华内容
下载资源
问答
  • G-SHORTEN! Google缩短多格式文本的网址 支持语言:English
  • Shorten Diameter

    2016-07-17 15:16:00
    Shorten Diameter Time limit : 2sec / Stack limit : 256MB / Memory limit : 256MB Score : 600 points Problem Statement Given an undirected tree, let the distance between vertices u and v be th...

    Shorten Diameter


    Time limit : 2sec / Stack limit : 256MB / Memory limit : 256MB

    Score : 600 points

    Problem Statement

    Given an undirected tree, let the distance between vertices u and v be the number of edges on the simple path from u to v. The diameter of a tree is the maximum among the distances between any two vertices. We will call a tree good if and only if its diameter is at most K.

    You are given an undirected tree with N vertices numbered 1 through N. For each i(1≦iN−1), there is an edge connecting vertices Ai and Bi.

    You want to remove zero or more vertices from the tree, so that the resulting tree is good. When a vertex is removed, all incident edges will also be removed. The resulting graph must be connected.

    Find the minimum number of vertices that you need to remove in order to produce a good tree.

    Constraints

    • 2≦N≦2000
    • 1≦KN−1
    • 1≦AiN,1≦BiN
    • The graph defined by Ai and Bi is a tree.

    Input

    The input is given from Standard Input in the following format:

    N K
    A1 B1
    A2 B2
    :
    AN−1 BN−1
    

    Output

    Print the minimum number of vertices that you need to remove in order to produce a good tree.


    Sample Input 1

    6 2
    1 2
    3 2
    4 2
    1 6
    5 6
    

    Sample Output 1

    2
    

    The tree is shown below. Removing vertices 5 and 6 will result in a good tree with the diameter of 2.

    ctree.png

    Sample Input 2

    6 5
    1 2
    3 2
    4 2
    1 6
    5 6
    

    Sample Output 2

    0
    

    Since the given tree is already good, you do not need to remove any vertex.

    分析:虽然没做出来,不过看了陈高远大牛的代码还是可以yy一下的。

    可以先求出任意两点间的距离(dfs),然后考虑最优情况是左右子树平衡的时候(有2种情况),遍历至最优情况即可

    代码:

    #include <iostream>
    #include <cstdio>
    #include <cstdlib>
    #include <cmath>
    #include <algorithm>
    #include <climits>
    #include <cstring>
    #include <string>
    #include <set>
    #include <map>
    #include <queue>
    #include <stack>
    #include <vector>
    #include <list>
    #include <ext/rope>
    #define rep(i,m,n) for(i=m;i<=n;i++)
    #define rsp(it,s) for(set<int>::iterator it=s.begin();it!=s.end();it++)
    #define vi vector<int>
    #define pii pair<int,int>
    #define mod 1000000007
    #define inf 0x3f3f3f3f
    #define pb push_back
    #define mp make_pair
    #define fi first
    #define se second
    #define ll long long
    #define pi acos(-1.0)
    const int maxn=2e3+10;
    const int dis[4][2]={{0,1},{-1,0},{0,-1},{1,0}};
    using namespace std;
    using namespace __gnu_cxx;
    ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);}
    ll qpow(ll p,ll q){ll f=1;while(q){if(q&1)f=f*p;p=p*p;q>>=1;}return f;}
    int n,m,a[maxn][maxn],mi,cnt;
    vi p[maxn];
    pii q[maxn];
    void dfs(int root,int pre,int now,int s)
    {
        a[root][now]=s;
        for(int x:p[now])
        {
            if(x!=pre)dfs(root,now,x,s+1);
        }
    }
    int main()
    {
        int i,j,k,t;
        mi=inf;
        scanf("%d%d",&n,&k);
        rep(i,1,n-1){
            scanf("%d%d",&j,&t);
            p[j].pb(t),p[t].pb(j);
            q[i].fi=j,q[i].se=t;
        }
        rep(i,1,n)dfs(i,-1,i,0);
        rep(i,1,n)
        {
            cnt=0;
            rep(j,1,n)
                if(2*a[i][j]>k)cnt++;
            mi=min(mi,cnt);
        }
        rep(i,1,n-1)
        {
            cnt=0;
            rep(j,1,n)
                if(2*min(a[j][q[i].fi],a[j][q[i].se])+1>k)
                    cnt++;
            mi=min(mi,cnt);
        }
        printf("%d\n",mi);
        //system ("pause");
        return 0;
    }

     

    转载于:https://www.cnblogs.com/dyzll/p/5678614.html

    展开全文
  • path-shorten-源码

    2021-05-06 10:03:02
    const pathShorten = require ( 'path-shorten' ) console . log ( pathShorten ( '/one/two/three/four/five.txt' ) ) console . log ( pathShorten ( 'C:\\Users\\mollie\\Documents\\\\some-project' ) ) console...
  • G-SHORTEN!-crx插件

    2021-04-03 22:08:28
    语言:English g-shorten! google缩短了多格式文本的URL
  • Shorten 是一个可以在 DIV 中自动缩短文本并且加上“show more”链接的 jQuery 插件。 标签:Shorten
  • shorten command line

    2020-11-13 17:37:25
     shorten command line 选项提供三种选项缩短类路径。  none:这是默认选项,idea不会缩短命令行。如果命令行超出了OS限制,这个想法将无法运行您的应用程序,但是工具提示将建议配置缩短器。  JAR manifest:...

     

    IntelliJ IDEA 

    如果类路径太长,或者有许多VM参数,程序就无法启动。原因是大多数操作系统都有命令行长度限制。在这种情况下,IntelliJIDEA将试图缩短类路径。

      shorten command line 选项提供三种选项缩短类路径。

      none:这是默认选项,idea不会缩短命令行。如果命令行超出了OS限制,这个想法将无法运行您的应用程序,但是工具提示将建议配置缩短器。

      JAR manifest:idea 通过临时的classpath.jar传递长的类路径。原始类路径在MANIFEST.MF中定义为classpath.jar中的类路径属性。

      classpath file:idea 将一个长类路径写入文本文件中。

    展开全文
  • 在你阅读的任何文章中提取关键点。...多亏了Shorten and Translate,您还可以专注于后期编辑,释义和用外语引用您选择的文本。这使“缩短和翻译”成为翻译人员,营销人员和内容营销经理的理想工具。 支持语言:English
  • 缩短网址 缩短网址 我尝试使用 Spring + Mybatis 创建 Shorten_Url 服务。 默认编码为 base64。
  • 前端开源库-path-shorten

    2019-08-30 02:21:40
    前端开源库-path-shorten路径缩短、检测和缩短、操作路径
  • shorten command line报错

    2021-04-06 09:49:40
    解决方法:在点进去设置configuration之后,在shorten command line中选择最后一个选项:classfile

    解决方法:在点进去设置configuration之后,在shorten command line中选择最后一个选项:classfile

    展开全文
  • Shorten.REST URL缩短API Chrome扩展程序-无需登录帐户即可轻松缩短和管理简短的品牌URL。 轻松搜索,更新和管理您现有的短URL。 在short.fyi和您自己的品牌域名之间进行选择(允许多个域名!)。 自定义URI(别名/...
  • 很多人都知道去Edit configuration 找Shorten comand line,但有时候单元测试的配置中找不到 Shorten comand line,不是没有而是被隐藏了,默认没有显示出来,而application 的Edit configuration 中会显示出来 ...

    很多人都知道去Edit configuration 找Shorten comand line,但有时候单元测试的配置中找不到
    Shorten comand line,不是没有而是被隐藏了,默认没有显示出来,而application 的Edit configuration 中会显示出来
    在这里插入图片描述
    在这里插入图片描述
    这样展示出后重新设置,就可以顺利启动了

    展开全文
  • <div><p>Can you shorten the publication cycle of the map updates activities to one week? The community is mapping health centers, pharmacies, supermarkets, and we would like to see the new data faster...
  • NIST SPHERE shorten音频解码工程,从unix移植过来,删去不必要的库,增加windows下面的库函数,在win32/64下跑的vs2010工程
  • Command line is too long.Shorten command line for Application or also for Spring Boot default configuration. 二、报错原因 springboot项目启动命令过长 三、解决办法 点击项目启动配置项 -> short.....
  • $ npm install --save emojify-shorten 用法 const emojify = require ( 'emojify-shorten' ) emojify ( 'www.google.com' ) . then ( console . log ) /* [ 'http://emojify.tk/c', 'http://:skier:.cf/c', '...
  • 开源项目-kshvmdn-shorten.zip,一个带有GitHub页面的个人网址缩短器
  • HDU 6917 Shorten the array

    2021-05-27 20:22:46
    题目链接 ... She thinks the array is too long, so she wants to shorten the array. She decides to shorten the array via the following operation: every time she will choose an index i(1≤i<
  • $ npm install react-shorten-url 或纱线: $ yarn add react-shorten-url 入门 ShortenUrlProvider 配置参数值 姓名 类型 默认 描述 accessToken 细绳 比特访问令牌 选项 BitlyConfig {} 额外的按位配置 ...
  • shorten 通过GitHub Pages的个人URL缩短器
  • IDEA : shorten command line

    千次阅读 2020-09-22 11:06:17
    【官方文档】:IntelliJ IDEA 2017.3 EAP:... shorten command line 选项提供三种选项缩短类路径。  none:这是默认选项,idea不会缩短命令行。如果命令行超出了OS限制,这个想法将无法运行您的应用程序,但是工具提
  • Shorten 是一个由koa.js提供支持的io.js URL 缩短koa.js ,带有一个 JSON “dataase”。 安装 您需要安装io.js >= 1.0.0 。 请参阅进行安装。 $ git clone https://github.com/juhohei/shorten.git $ cd shorten $ ...
  • 语言:English 提取您阅读的任何文章中的要点,并立即对其进行翻译! 从您阅读的任何文章中提取要点,并立即对其进行翻译!...多亏了Shorten and Translate,您还可以专注于后期编辑,释义和用外语引用您选
  • 问题如图: Error running 'SpringBootMainApplication': ... Shorten command line for SpringBootMainApplication or also for Application default configuration.   解决方案: 修改项目下 .idea\w...
  • Bit.ly url 缩短类 类的基本使用 <...$ short_url = Bitly :: init ()-> bitly_shorten ( urldecode ( $ url )); if ( isset ( $ short_url [ 'url' ])) echo $ short_url [ 'url' ]; exit; ?>
  • Error running ‘SrmPurchaseCooperationOPApplication’: Command line is too long. Shorten command line for 一定要使用classpathfile,
  • #go-shorten 用 Go 编写的 URL 缩短器。 遵循来自的标准算法(双射函数) GoLang 中的一个学习项目。 2014 年 9 月 ~ 灵巧

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 6,240
精华内容 2,496
关键字:

Shorten