ACM 544 Heavy Cargo
作法:最大運輸量問題
NPSC的水之都(想法)+丁丁共和國(技巧)
/*********************************************************/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int map[201][200][2]={0};
int n,m,time=0;
main()
{
while(scanf("%d %d",&n,&m)==2&&n!=0)
{
int a,b,c,data,maptop[1001]={0},top=0;
char xx[101],yy[101],name[201][50]={0};
for(a=0;a<m;a++)
{
scanf("%s %s %d",&xx,&yy,&data);
int a,b,c,m=strlen(xx),flagx,flagy,x[50]={0},y[50]={0};
for(a=0;a<m;a++) x[a]=xx[a];
for(b=0;b<top;b++)
{
for(a=0;a<50;a++)
if(x[a]!=name[b][a]) break;
if(a==50) {flagx=b;break;}
}
if(b==top)
{
for(a=0;a<m;a++)
name[top][a]=x[a];
flagx=top;top++;
}
m=strlen(yy);
for(a=0;a<m;a++) y[a]=yy[a];
for(b=0;b<top;b++)
{
for(a=0;a<50;a++)
if(y[a]!=name[b][a]) break;
if(a==50) {flagy=b;break;}
}
if(b==top)
{
for(a=0;a<m;a++)
name[top][a]=y[a];
flagy=top;top++;
}
map[flagx][maptop[flagx]][0]=flagy;
map[flagx][maptop[flagx]][1]=data;
maptop[flagx]++;
map[flagy][maptop[flagy]][0]=flagx;
map[flagy][maptop[flagy]][1]=data;
maptop[flagy]++;
}
scanf("%s %s",&xx,&yy);
int m=strlen(xx),flagx,flagy,x[50]={0},y[50]={0};
for(a=0;a<m;a++) x[a]=xx[a];
for(b=0;b<top;b++)
{
for(a=0;a<50;a++)
if(x[a]!=name[b][a]) break;
if(a==50) {flagx=b;break;}
}
m=strlen(yy);
for(a=0;a<m;a++) y[a]=yy[a];
for(b=0;b<top;b++)
{
for(a=0;a<50;a++)
if(y[a]!=name[b][a]) break;
if(a==50) {flagy=b;break;}
}
int flag[201]={0},way[201]={0},find=0;
flag[flagx]=1;way[flagx]=2147483647;
for(a=0;a<n;a++)
for(b=0;b<n;b++)
for(c=0;c<maptop[b];c++)
if(flag[map[b][c][0]]==1)
{
int temp=(way[map[b][c][0]]>map[b][c][1])?map[b][c][1]:way[map[b][c][0]];
way[b]=(temp>way[b])?temp:way[b];
flag[b]=1;
}
printf("Scenario #%d\n%d tons\n",++time,way[flagy]);
}
return 0;
}
但是我這題和水之都解了
丁丁共和國卻不知如何下手
看來要再思考了....
丁丁共和國我是採用遞迴的DFS搜尋 2009-06-03 22:28:01