[ACM] POJ1125 解题报告

老田用的弗洛伊德 我觉得我的快一点..不知道叫啥算法 无招胜有招了 (墨镜)
每个人身上两种属性 传到他需要的时间(int time)以及他是否往下传播(bool set)
unit向他的contact传播 => contact.time=unit.settime

[contact](传播到此contact所需时间)+unit.time

1.开始选择的人start, start.set=true
2.扫描所有的unit, 如果set==true则对他的每一个contact判断, 若contact.time>unit.time+unit.setting(contact), 则用这个较快的time赋值,并且contact.set=true, 下一轮用新的time传播给这个contact的contact们
3.重复2知道所有unit.set==false为止
4.判断是否有unit没有触及到

#include <cstdio>

 typedef struct unit {
     int num;
     int contact[99];
     int settime[99];
     bool set;
     int time;
 } Unit;

 typedef struct aa {
     int start;
     int time;
 } Result;

void calc();
int search();

Unit a[101];
Result x,result;
int n;

int main() {
    int i,j,start;
    scanf("%d",&n);
    while(n) {
        for(i=1;i<=n;i++) {
            scanf("%d",&a[i].num);
            for(j=0;j<a[i].num;j++)
                scanf("%d%d",&a[i].contact[j],&a[i].settime[j]);
        }
        result.start=-1;
        for(start=1;start<=n;start++) {
            for(i=1;i<=n;i++) {
                a[i].set=false;
                a[i].time=-1;
            }
            a[start].set=true;
            a[start].time=0;
            i=0;
            while(i<n+1) {
                calc();
                for(i=1;i<=n;i++)
                    if(a[i].set==true)
                        break;
            }
            x.time=search();
            x.start=start;
            for(i=1;i<=n;i++)
                if(a[i].time==-1) {
                    x.start=-1;
                    break;
                }
            if(x.start==-1)
                continue;
            if(x.time<result.time||result.start==-1)
                result=x;
        }
        if(result.start==-1)
            if(n==0)
                printf("0 0\n");
            else
                printf("disjoint\n");
        else
            printf("%d %d\n",result.start,result.time);
        scanf("%d",&n);
    }
    return 0;
}

void calc() {
    int i,j,spreadtime;
    for(i=1;i<=n;i++)
        if(a[i].set) {
            for(j=0;j<a[i].num;j++) {
                spreadtime=a[i].time+a[i].settime[j];
                if(a[a[i].contact[j]].time>spreadtime||a[a[i].contact[j]].time==-1) {
                    a[a[i].contact[j]].time=spreadtime;
                    a[a[i].contact[j]].set=true;
                }
            }
            a[i].set=false;
        }
}

int search() {
    int max,i;
    max=a[1].time;
    for(i=2;i<=n;i++)
        if(a[i].time>max)
            max=a[i].time;
    return max;
}

 

Leave a Reply

Your email address will not be published. Required fields are marked *