[ACM] POJ1135解题报告

138 Replies

Did you know that you can use domino bones for other things besides playing Dominoes? Take a number of dominoes and build a row by standing them on end with only a small distance in between. If you do it right, you can tip the first domino and cause all others to fall down in succession (this is where the phrase “domino effect” comes from).

啥都不用说了..原来我想出来的算法 在五十年前已经被一名叫做的Dijkstra同学提出来了.. 恨啊 晚生半个世纪
Dijkstra’s algorithm传送门
http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm
右边图示很销魂

前面都差不多就是当结果是between a  and b时需要技巧，我是在所有dominoes都倒下后将所有连接的节点进行计算，多米诺卡在ab之间的时间等于(a.time+b.time+ab之间时间)/2，当b是由a推倒时，这个数值就等于b的时间，不可能超过最长时间，因而无需额外考虑，方便啊！

[c]#include <cstdio>
#include <cstring>
#define MAXNUM 500

typedef struct card{
int time;
int l[MAXNUM+1];
bool touched,out;
} Card;

int n,p,p1=-1,p2;
float time;
Card a[MAXNUM+1];

void dij();
void between();

int main() {
int c,b,l,m;
int i,N=1;
Card ini; //used to initialize
memset(ini.l,-1,sizeof(int)*(MAXNUM+1));
ini.time=0;
ini.touched=false;
ini.out=false;
scanf("%d%d",&n,&m);
while(n!=0) {
for(i=1;i<=MAXNUM;i++)
a[i]=ini;
p1=-1;
time=0;

for(i=0;i<m;i++) {
scanf("%d%d%d",&c,&b,&l);
a[c].l[b]=a[b].l[c]=l;
}
a[1].touched=true;
for(i=1;i<=n;i++)
dij();
between();
printf("System #%d\nThe last domino falls after %.1f seconds, ",N,time);
if(p1!=-1)
printf("between key dominoes %d and %d.\n\n",p1,p2);
else
printf("at key domino %d.\n\n",p);
N++;
scanf("%d%d",&n,&m);
}
return 0;
}

void dij() {
int i,j,reachtime;
p=-1;
for(i=1;i<=n;i++) {
if(!a[i].touched||a[i].out)
continue;
if(p==-1||a[p].time>a[i].time)
p=i;
}
for(i=1;i<=n;i++) {
if(a[p].l[i]==-1||a[i].out)
continue;
reachtime=a[p].time+a[p].l[i];
if(!a[i].touched||a[i].time>reachtime) {
a[i].time=reachtime;
a[i].touched=true;
}
}
a[p].out=true;
time=a[p].time;
}

void between() {
int i,j;
float t;
for(i=1;i<=n;i++)
for(j=i;j<=n;j++) {
if(a[i].l[j]==-1||(t=(float)(a[i].time+a[j].time+a[i].l[j])/2)<=time)
continue;
p1=i;
p2=j;
time=t;
}
}[/c]

138 thoughts on “[ACM] POJ1135解题报告”

Leave a Reply

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