最小ツリー(二)(最小生成ツリーprim)
description n , A, B……, , , 。
input , n m ,(n,m < 100) m , ( A,B,C........., n 3, A,B,C, ) ( )。
output , , -1.
sample_input 3 3
A B 1
A C 2
B C 4
3 1
A B 2
sample_output 3
-1
AC
コード:#include<iostream>
#include<cstdio>
#include<string.h>
using namespace std;
#define MAX 99999
#define LEN 101
int dist[LEN];
int map[LEN][LEN];
bool isvisited[LEN];
int m;
void init()//
{
int i,j;
for(i=0; i<LEN; i++)
{
for(j=0; j<LEN; j++)
{
map[i][j]=MAX;
}
}
}
int prime(int n)
{
int i,j,min,pos,sum;
sum=0;
memset(isvisited,false,sizeof(isvisited));
for(i=1; i<=n; i++)
{
dist[i]=map[1][i];
}
isvisited[1]=true;
dist[1]=MAX;
for(i=1; i<n; i++)
{
min=MAX;
for(j=1; j<=n; j++)
{
if(!isvisited[j] && dist[j]<min)
{
min=dist[j];
pos=j;
}
}
if(min==MAX)// ,
{
return -1;
}
sum+=min;
isvisited[pos]=true;
for(j=1; j<=n; j++)
{
if(!isvisited[j] && dist[j]>map[pos][j])
{
dist[j]=map[pos][j];
}
}
}
return sum;
}
int main()
{
int n,m;
while(~scanf("%d%d",&m,&n))
{
init();
int i,a,b,w,ans;
char c,d;
if(n==0) break;
for(i=0; i<n; i++)
{
cin>>c>>d>>w;
a=c-'A'+1;
b=d-'A'+1;
if(map[a][b]>w)
{
map[a][b]=map[b][a]=w;
}
}
ans=prime(m);
cout<<ans<<endl;
}
return 0;
}
n , A, B……, , , 。
, n m ,(n,m < 100) m , ( A,B,C........., n 3, A,B,C, ) ( )。
output , , -1.
sample_input 3 3
A B 1
A C 2
B C 4
3 1
A B 2
sample_output 3
-1
AC
コード:#include<iostream>
#include<cstdio>
#include<string.h>
using namespace std;
#define MAX 99999
#define LEN 101
int dist[LEN];
int map[LEN][LEN];
bool isvisited[LEN];
int m;
void init()//
{
int i,j;
for(i=0; i<LEN; i++)
{
for(j=0; j<LEN; j++)
{
map[i][j]=MAX;
}
}
}
int prime(int n)
{
int i,j,min,pos,sum;
sum=0;
memset(isvisited,false,sizeof(isvisited));
for(i=1; i<=n; i++)
{
dist[i]=map[1][i];
}
isvisited[1]=true;
dist[1]=MAX;
for(i=1; i<n; i++)
{
min=MAX;
for(j=1; j<=n; j++)
{
if(!isvisited[j] && dist[j]<min)
{
min=dist[j];
pos=j;
}
}
if(min==MAX)// ,
{
return -1;
}
sum+=min;
isvisited[pos]=true;
for(j=1; j<=n; j++)
{
if(!isvisited[j] && dist[j]>map[pos][j])
{
dist[j]=map[pos][j];
}
}
}
return sum;
}
int main()
{
int n,m;
while(~scanf("%d%d",&m,&n))
{
init();
int i,a,b,w,ans;
char c,d;
if(n==0) break;
for(i=0; i<n; i++)
{
cin>>c>>d>>w;
a=c-'A'+1;
b=d-'A'+1;
if(map[a][b]>w)
{
map[a][b]=map[b][a]=w;
}
}
ans=prime(m);
cout<<ans<<endl;
}
return 0;
}
, , -1.
3 3
A B 1
A C 2
B C 4
3 1
A B 2
sample_output 3
-1
AC
コード:#include<iostream>
#include<cstdio>
#include<string.h>
using namespace std;
#define MAX 99999
#define LEN 101
int dist[LEN];
int map[LEN][LEN];
bool isvisited[LEN];
int m;
void init()//
{
int i,j;
for(i=0; i<LEN; i++)
{
for(j=0; j<LEN; j++)
{
map[i][j]=MAX;
}
}
}
int prime(int n)
{
int i,j,min,pos,sum;
sum=0;
memset(isvisited,false,sizeof(isvisited));
for(i=1; i<=n; i++)
{
dist[i]=map[1][i];
}
isvisited[1]=true;
dist[1]=MAX;
for(i=1; i<n; i++)
{
min=MAX;
for(j=1; j<=n; j++)
{
if(!isvisited[j] && dist[j]<min)
{
min=dist[j];
pos=j;
}
}
if(min==MAX)// ,
{
return -1;
}
sum+=min;
isvisited[pos]=true;
for(j=1; j<=n; j++)
{
if(!isvisited[j] && dist[j]>map[pos][j])
{
dist[j]=map[pos][j];
}
}
}
return sum;
}
int main()
{
int n,m;
while(~scanf("%d%d",&m,&n))
{
init();
int i,a,b,w,ans;
char c,d;
if(n==0) break;
for(i=0; i<n; i++)
{
cin>>c>>d>>w;
a=c-'A'+1;
b=d-'A'+1;
if(map[a][b]>w)
{
map[a][b]=map[b][a]=w;
}
}
ans=prime(m);
cout<<ans<<endl;
}
return 0;
}
3
-1
#include<iostream>
#include<cstdio>
#include<string.h>
using namespace std;
#define MAX 99999
#define LEN 101
int dist[LEN];
int map[LEN][LEN];
bool isvisited[LEN];
int m;
void init()//
{
int i,j;
for(i=0; i<LEN; i++)
{
for(j=0; j<LEN; j++)
{
map[i][j]=MAX;
}
}
}
int prime(int n)
{
int i,j,min,pos,sum;
sum=0;
memset(isvisited,false,sizeof(isvisited));
for(i=1; i<=n; i++)
{
dist[i]=map[1][i];
}
isvisited[1]=true;
dist[1]=MAX;
for(i=1; i<n; i++)
{
min=MAX;
for(j=1; j<=n; j++)
{
if(!isvisited[j] && dist[j]<min)
{
min=dist[j];
pos=j;
}
}
if(min==MAX)// ,
{
return -1;
}
sum+=min;
isvisited[pos]=true;
for(j=1; j<=n; j++)
{
if(!isvisited[j] && dist[j]>map[pos][j])
{
dist[j]=map[pos][j];
}
}
}
return sum;
}
int main()
{
int n,m;
while(~scanf("%d%d",&m,&n))
{
init();
int i,a,b,w,ans;
char c,d;
if(n==0) break;
for(i=0; i<n; i++)
{
cin>>c>>d>>w;
a=c-'A'+1;
b=d-'A'+1;
if(map[a][b]>w)
{
map[a][b]=map[b][a]=w;
}
}
ans=prime(m);
cout<<ans<<endl;
}
return 0;
}