1232
#include<iostream>
using namespace std;
struct arr{
long x,y,c;
}a[100000];
int n,m,p[1001];
long find(long x){
if(x!=p[x]) p[x]=find(p[x]);
return p[x];
}
int main()
{
while(1){
scanf("%d",&n);
if(!n) break;
scanf("%d",&m);
for(long i=0;i<m;++i){
scanf("%d %d",&a[i].x,&a[i].y);
a[i].c=1;
}
for(long i=1;i<=n;++i) p[i]=i;
long x,y,k=0;
for(long i=0;i<m;++i){
x=find(a[i].x);
y=find(a[i].y);
if(x!=y){
k++;
if(k==n-1) break;
p[y]=x;
}
}
printf("%d\n",(n-1)-k);
}
return 0;
}
1233
var n,i,j,m,min,p,valuet:longint;
seleceted:array[1..4950]of 0..1;
value:array[1..4950]of longint;
e:array[1..4950,1..2]of longint;
t:array[1..4950]of 0..1;
begin
while not eof do
begin
read(n);
if n=0 then break;
m:=n*(n-1) div 2;
for i:=1 to m do
read(e[i,1],e[i,2],value[i]);
fillchar(seleceted,sizeof(seleceted),0);
fillchar(t,sizeof(t),0);
valuet:=0;
for i:=1 to n-1 do
begin
min:=maxint;
for j:=1 to m do
if seleceted[j]=0 then
if ((t[e[j,1]]=0)xor(t[e[j,2]]=0))or(i=1)then
if value[j]<min then
begin
min:=value[j];p:=j;
end;
seleceted[p]:=1;
t[e[p,1]]:=1;t[e[p,2]]:=1;
valuet:=valuet+min;
end;
writeln(valuet);
end;
end.
1863
#include<cstdio>
#include<cstdlib>
using namespace std;
struct arr{
long x,y,c;
};
long n,m,MIN,p[111];
arr a[10010];
void Qsort(long s,long t){
long i=s,j=t,mid=a[(s+t)/2].c;
arr tmp;
while(i<=j){
while(a[i].c<mid) ++i;
while(a[j].c>mid) --j;
if(i<=j){
tmp=a[i];
a[i]=a[j];
a[j]=tmp;
++i; --j;
}
}
if(i<t) Qsort(i,t);
if(s<j) Qsort(s,j);
}
long find(long x){
if(x!=p[x]) p[x]=find(p[x]);
return p[x];
}
int main()
{
while(1){
scanf("%d %d",&m,&n);
if(m==0) break;
for(long i=1;i<=m;++i)
scanf("%d %d %d",&a[i].x,&a[i].y,&a[i].c);
Qsort(1,m);
long k=0,x,y; MIN=0;
for(long i=1;i<=n;++i) p[i]=i;
for(long i=1;i<=m;++i){
x=find(a[i].x);
y=find(a[i].y);
if(x!=y){
MIN+=a[i].c;
k++;
if(k==n-1) break;
p[y]=x;
}
}
if(k==n-1&&MIN) printf("%d\n",MIN);
else printf("?\n");
}
return 0;
}
1874
#include<cstdio>
#include<cstring>
long n,m,l[2000],lw[2000][1000],cost[2000][1000];
void SPFA(long s,long nn){
long long d[n];
long list[50000],h,t,x,y;
bool hash[n+1];
for(long i=0;i<n;++i){
d[i]=0xFFFFFFF;
hash[i]=1;
}
d[s]=0; h=t=1; hash[s]=0;
list[1]=s;
while(h<=t){
x=list[h];
for(long i=1;i<=l[x];++i){
y=lw[x][i];
if(d[y]>d[x]+cost[x][i]){
d[y]=d[x]+cost[x][i];
if(hash[y]){
t++;
list[t]=y;
hash[y]=0;
}
}
}
h++;
hash[x]=1;
}
if(d[nn]==0xFFFFFFF) printf("-1\n");
else printf("%d\n",d[nn]);
}
int main()
{
while(scanf("%d %d",&n,&m)!=EOF){
for(long i=0;i<n;++i) l[i]=0;
long x,y,c;
for(long i=0;i<m;++i){
scanf("%d %d %d",&x,&y,&c);
l[x]++;
lw[x][l[x]]=y;
cost[x][l[x]]=c;
l[y]++;
lw[y][l[y]]=x;
cost[y][l[y]]=c;
}
scanf("%d %d",&x,&y);
SPFA(x,y);
}
}
1875
#include<iostream>
#include<cmath>
#include<cstdlib>
using namespace std;
struct arr{
long x,y;
double c;
}a[40000];
long t,n,m,x[201],y[201],p[201];
int cmp(const void* no1,const void* no2){
arr *nox=(arr*)no1,*noy=(arr*)no2;
if(nox->c>noy->c) return 1;
else return -1;
}
long find(long x){
if(x!=p[x]) p[x]=find(p[x]);
return p[x];
}
int main()
{
scanf("%d",&t);
while(t){
scanf("%d",&n);
m=0;
for(long i=1;i<=n;++i){
scanf("%d %d",&x[i],&y[i]);
for(long j=1;j<i;++j){
double c=(x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]);
c=sqrt(c);
if(c<10.0||c>1000.0) continue;
a[++m].x=i; a[m].y=j; a[m].c=c;
}
}
qsort(a+1,m,sizeof(arr),cmp);
long xx,yy,k=0;
double ans=0.0;
for(long i=1;i<=n;++i) p[i]=i;
for(long i=1;i<=m;++i){
xx=find(a[i].x);
yy=find(a[i].y);
if(xx!=yy){
ans+=a[i].c;
k++;
if(k==n-1) break;
p[yy]=xx;
}
}
if(k!=n-1) printf("oh!\n");
else printf("%0.1lf\n",ans*100.0);
--t;
}
return 0;
}
1879
#include<cstdio>
#include<cstdlib>
int n,m,cost[101][101],MIN;
void prim(){
long dis[101],bo[101];
for(long i=1;i<=n;++i){
dis[i]=cost[1][i];
bo[i]=1;
}
bo[1]=0;
for(long i=1;i<n;i++){
long min=0xFFFFFFF,minj;
for(long j=1;j<=n;++j)
if(bo[j]&&dis[j]<min){
min=dis[j]; minj=j;
}
MIN+=min;
bo[minj]=0;
for(long j=1;j<=n;++j)
if(bo[j]&&dis[j]>cost[minj][j])
dis[j]=cost[minj][j];
}
}
int main()
{
while(scanf("%d",&n)!=EOF){
if(!n) break;
m=n*(n-1)/2;
for(long i=1;i<=n;++i)
for(long j=1;j<=n;++j) cost[i][j]=0xFFFFFFF;
for(long i=1;i<=m;++i){
long x,y,c,z;
scanf("%d %d %d %d",&x,&y,&c,&z);
if(z) cost[x][y]=cost[y][x]=0;
else cost[x][y]=cost[y][x]=c;
}
MIN=0;
prim();
printf("%d\n",MIN);
}
return 0;
}
posted on 2009-07-02 18:35
xfstart07 阅读(312)
评论(0) 编辑 收藏 引用