toj 最小生成树集萃

1924 jungle road

#include<iostream>

#include<cstring>

using namespace std;

int path[30][30];

int cost[30];

int flag[30];

int prim(int n)

{

int sum=0;

int i,j,min,v;

v=0;

flag[v]=1;

for(i=0;i<n-1;i++)

{

for(j=0;j<n;j++)

if(!flag[j]&&path[v][j]<cost[j])

cost[j]=path[v][j];

min=1<<30;

for(j=0;j<n;j++)

if(!flag[j]&&cost[j]<min)

{

min=cost[j];

v=j;

}

flag[v]=1;

sum+=min;

}

return sum ;

}

int main()

{

int n,i,j,v,min,m,c;

char ch;

while(scanf("%d",&n)!=EOF&&n)

{

memset(path,0x1f,sizeof(path));

memset(cost,0x1f,sizeof(cost));

memset(flag,0,sizeof(flag));

for(i=0;i<n;i++)

path[i][i]=0;

for(i=0;i<n-1;i++)

{

getchar();

scanf("%c",&ch);

scanf("%d",&m);

for(j=0;j<m;j++)

{

getchar();

scanf("%c",&ch);

scanf("%d",&c);

path[i][ch-'A']=path[ch-'A'][i]=c;

}

printf("%d\n",prim(n));

}

return 0;

}

1348 freckles

#include<iostream>

#include<iomanip>

#include<cmath>

using namespace std;

int x[501];

int y[501];

struct node

{

int s,e;

int d;

bool operator<(const node& a)const

{

return d<a.d;

}

}edges[130000];

int father[505];

int n,m;

int find(int i)

{

if(father[i]==i)

return i;

else

return father[i]=find(father[i]);

}

void unin(int i,int j)

{

int a=find(i);

int b=find(j);

father[a]=b;

}

int f(int k)

{

int i,j;

j=0;

for(i=0;i<k&&j<m-n;i++)

if(find(father[edges[i].s])!=find(father[edges[i].e]))

{

unin(edges[i].s,edges[i].e);

j++;

if(j==m-n)

return edges[i].d;

}

int main()

{

int i,j,k,cas_num;

scanf("%d",&cas_num);

while(cas_num--)

{

scanf("%d%d",&n,&m);

for(i=0;i<m;i++)

father[i]=i;

k=0;

for(i=0;i<m;i++)

{

cin>>x[i]>>y[i];

for(j=0;j<i;j++)

{

edges[k].s=j;

edges[k].e=i;

edges[k].d=(x[j]-x[i])*(x[j]-x[i])+(y[j]-y[i])*(y[j]-y[i]);

k++;

}

sort(edges,edges+k);

cout<<fixed<<setprecision(2)<<sqrt(f(k)*1.0)<<endl;

}

return 0;

}

1830. Tangled in Cables

#include<iostream>

#include<map>

#include<algorithm>

#include<string>

using namespace std;

struct node

{

int s,e;

double d;

bool operator<(const node& a)const

{

return d<a.d;

}

}edges[60000];

int father[505];

int find(int i)

{

if(father[i]==i)

return i;

else

return father[i]=find(father[i]);

}

void unin(int i,int j)

{

int a=find(i);

int b=find(j);

father[a]=b;

}

void f(double total,int n,int m)

{

int i,j;

double sum=0;

j=0;

for(i=0;i<m&&j<n-1&&sum<total;i++)

if(find(father[edges[i].s])!=find(father[edges[i].e]))

{

unin(edges[i].s,edges[i].e);

sum+=edges[i].d;

j++;

}

if(j==n-1)

printf("Need %.1lf miles of cable\n",sum);

else

printf("Not enough cable\n");

}

int main()

{

map<string,int>mm;

int i,n,m;

double cost,total;

double ans;

string s1,s2;

char ch1[21],ch2[21];

while(cin>>total)

{

scanf("%d",&n);

for(i=0;i<n;i++)

father[i]=i;

for(i=0;i<n;i++)

{

scanf("%s",ch1);

s1=ch1;

mm[s1]=i;

}

scanf("%d",&m);

for(i=0;i<m;i++)

{

scanf("%s %s",ch1,ch2);

scanf("%lf",&cost);

s1=ch1;

s2=ch2;

edges[i].s=mm[s1];

edges[i].e=mm[s2];

edges[i].d=cost;

}

sort(edges,edges+m);

f(total,n,m);

}

return 0;

}

2288. Highways

#include<iostream>

#include<algorithm>

using namespace std;

int x[760],y[760];

int father[760];

int find(int i)

{

if(father[i]==i)

return i;

else

return father[i]=find(father[i]);

}

void unin(int i,int j)

{

int a=find(i);

int b=find(j);

father[a]=b;

}

struct node

{

int s,e;

int d;

bool operator <(const node& a)const

{

if(d!=a.d)

return d<a.d;

else

return s<a.s;

}

}edges[300000];

void kruscal(int n,int k)

{

int j=0;

for(int i=0;i<k&&j<n-1;i++)

if(find(edges[i].s)!=find(edges[i].e))

{

unin(edges[i].s,edges[i].e);

printf("%d %d\n",edges[i].s,edges[i].e);

j++;

}

int main()

{

int n,m,i,j,k,a,b;

while(scanf("%d",&n)!=EOF)

{

for(i=0;i<=n;i++)

father[i]=i;

k=0;

for(i=1;i<=n;i++)

{

scanf("%d%d",&x[i],&y[i]);

for(j=1;j<i;j++)

{

edges[k].s=j;

edges[k].e=i;

edges[k].d=(x[j]-x[i])*(x[j]-x[i])+(y[j]-y[i])*(y[j]-y[i]);

k++;

}

sort(edges,edges+k);

scanf("%d",&m);

for(i=0;i<m;i++)

{

scanf("%d%d",&a,&b);

unin(a,b);

}

kruscal(n,k);

}

return 0;

}

—TOJ 2172

#include<iostream>

#include<map>

#include<algorithm>

#include<string>

using namespace std;

struct node

{

int s,e;

int d;

bool operator<(const node& a)const

{

return d<a.d;

}

}edges[60000];

int father[5005];

int n,t;

int find(int i)

{

if(father[i]==i)

return i;

else

return father[i]=find(father[i]);

}

void unin(int i,int j)

{

int a=find(i);

int b=find(j);

father[a]=b;

}

int f(int k,int n)

{

int i,j,sum;

j=sum=0;

for(i=0;i<k&&j<n-1;i++)

if(find(father[edges[i].s])!=find(father[edges[i].e]))

{

unin(edges[i].s,edges[i].e);

sum+=edges[i].d;

j++;

}

return sum;

}

int main()

{

map<string,int>m;

int i,j,cost,k;

int ans;

string s1,s2;

char ch1[11],ch2[11];

while(scanf("%d%d",&n,&t)!=EOF)

{

j=0;

k=t;

for(i=0;i<=n;i++)

father[i]=i;

for(i=0;i<t;i++)

{

getchar();

scanf("%s %s",&ch1,&ch2);

scanf("%d",&cost);

s1=ch1;

s2=ch2;

map<string,int>::iterator it;

it=m.find(s1);

if(it==m.end())

{

m[s1]=j;

edges[k].s=0;

edges[k].e=j++;

edges[k].d=10;

k++;

}

it=m.find(s2);

if(it==m.end())

{

m[s2]=j;

edges[k].s=0;

edges[k].e=j++;

edges[k].d=10;

k++;

}

edges[i].s=m[s1];

edges[i].e=m[s2];

edges[i].d=cost;

}

ans=(n-j+1)*10;

sort(edges,edges+k);

ans+=f(k,j);

printf("The total cost is %d Yuan %d Jiao.\n",ans/10,ans%10);

}

return 0;

}

posted on 2010-05-13 12:00 YUANZX 阅读(271) 评论(0) 编辑收藏引用

只有注册用户登录后才能发表评论。




网站导航: 博客园 IT新闻 BlogJava 知识库博问管理

toj 最小生成树集萃

导航

统计

常用链接

留言簿

随笔档案

搜索

最新评论

阅读排行榜

评论排行榜