首页 > 其他 > 详细

hdu5422

时间:2015-08-31 06:31:53      阅读:206      评论:0      收藏:0      [点我收藏+]

链接:点击打开链接

题意:给出一个图,每条边都为1,使1到n走的路径为最短的同时再添加一条边,问有多少种添加的情况

代码:

#include <iostream>

using namespace std;

int main(){             //因为再添加一条边所以最短路一定为1
    int n,m,a,b,sign;   //因此问题变为求出添加的种数,因为最
    while(cin>>n>>m){   //只需判断图中1到n的路径是否为1即可,
        sign=0;         //如果不是则值能连接1到n,否则从n个点中
        while(m--){     //取出2个点,因此种类为C(n,2);
            cin>>a>>b;
            if((a==1&&b==n)||(b==1&&a==n))
            sign=1;     //判断1与n是否相连
        }
        n=n*(n-1)/2;
        if(sign)
        cout<<"1 "<<n<<endl;
        else
        cout<<"1 1"<<endl;
    }
    return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

hdu5422

原文:http://blog.csdn.net/stay_accept/article/details/48124497

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!