【POJ1125】Stockbroker Grapevine(动态规划,floyd)

Categories: 数据结构和算法
Tags: ,
Comments: No Comments
Published on: 2011 年 04 月 26 日

题意:股票Broker们需要在他们的客户中传播谣言,但是每个Broker只能传给他自己的顾客们。给出Broker们和他们所
拥有的顾客,求能让谣言传播从第一个人开始到最后一个客户的最短时间。使用Floyd算法。
输入样例是有多少经纪人,随后是每行第一个数是相应编号的经纪人联系的人,然后之后每对数表示联系的人的编号和联系需要花的时间。

#include <iostream>  
#include <cstring>  
using namespace std;  
#define datalen 101  
short relations[datalen][datalen];  
short n,m,i,j,k,temp,mymax,mymin;  
void Floyd()  
{  
    for (i=1;i<=n;i++)  
        relations[i][i]=0;  
    for (k=1;k<=n;k++)  
    {  
        for (i=1;i<=n;i++)  
        {  
            if(i==k) continue;  
            for (j=1;j<=n;j++)  
            {  
                if(j==k || j==i) continue;  
                if(relations[i][j]>(relations[i][k]+relations[k][j]))  
                relations[i][j]=relations[i][k]+relations[k][j];  
            }  
        }  
    }  
}  
int main(){  
    //freopen("1.txt","r",stdin);  
    while(cin>>n)  
    {  
        if(n==0) break;  
        memset(relations,0x7f,sizeof(relations));  
        for (i=1;i<=n;i++){  
            cin>>m;  
            for (j=1;j<=m;j++){  
                cin>>temp;  
                cin>>relations[i][temp];  
                /*此处如果cin>>temp>>relations[i][temp];会出错。 
                原因貌似是因为函数参数传值是从最右边的一个参数开始计算的。 
                这样的话这里的输入转化成函数形式: 
                operator>>(operator>>(cin,temp),relations[i][temp]); 
                他会先输入relations[i][temp]的值,如果temp赋值则不会报错, 
                但我们会发现这temp并不是我们期待的值,否则这里会报错。 
                大家看到这里的可以自己写个简单的函数进行测试。 
                */  
            }  
        }  
        Floyd();  
        mymin=1000;  
        for (i=1;i<=n;i++){  
            mymax=0;  
            for (j=1;j<=n;j++){  
                if(i!=j && relations[i][j]>mymax)  
                    mymax=relations[i][j];  
            }  
            if(mymax<mymin){  
                temp=i;  
                mymin=mymax;  
            }  
        }  
        if(mymin<1000)cout<<temp<<" "<<mymin<<endl;  
        else cout<<"disjoint"<<endl;  
    }  
}  

我猜你可能也喜欢:

No Comments - Leave a comment

Leave a comment

电子邮件地址不会被公开。 必填项已用*标注

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>


Welcome , today is 星期二, 2017 年 10 月 24 日