[ACM] POJ1125 解题报告

113 Replies

老田用的弗洛伊德 我觉得我的快一点..不知道叫啥算法 无招胜有招了 (墨镜)
每个人身上两种属性 传到他需要的时间(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没有触及到

[cpp]#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;
}

[/cpp]

113 thoughts on “[ACM] POJ1125 解题报告”

Leave a Reply

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