最小树_Phoenix0z的博客-程序员秘密

技术标签： 书籍学习  数据结构   

#include<iostream>
#include<string>
using namespace std;
const int Max=20;
const int Mlen=9999;

struct zp{
int k;
int value;
};

struct ma{
    int h1;
    int h2;
    int v;
};

zp mar[Max][Max];
string*str;
int n,len;

void create(){
    for(int i=0;i<Max;i++)
        for(int j=0;j<Max;j++){
            mar[i][j].k=-1;
            mar[i][j].value=-1;
        }
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++){
            mar[i][j].k=0;
            mar[i][j].value=0;
        }
    str=new string[n];
    for(int i=0;i<n;i++){
        cin>>str[i];
    }
    cin>>len;
    for(int i=0;i<len;i++){
        string s1,s2;
        int num;
        cin>>s1>>s2>>num;
        int z1,z2;
        for(int i=0;i<n;i++){
            if(str[i]==s1)
                z1=i;
            if(str[i]==s2)
                z2=i;
        }
        mar[z1][z2].k=1;
        mar[z1][z2].value=num;
        mar[z2][z1].k=1;
        mar[z2][z1].value=num;
    }
     for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cout<<mar[i][j].k;
            if(mar[i][j].k==1){
                cout<<"("<<mar[i][j].value<<")";
            }else{
            cout<<"   ";
            }
            //mar[i][j].value;
        }
        cout<<endl;
    }
}
void prim(){
    int ans=0;
    string u;
    cin>>u;
    cout<<"prim:"<<endl;
    int z;
    for(int i=0;i<n;i++){
        if(str[i]==u){
            z=i;
        }
    }
    ma*line=new ma[len];
    for(int i=0;i<len;i++){
        if(i!=z&&mar[z][i].k==1){
            line[i]={ z,i,mar[z][i].value};
        }else{
            line[i]={ -1,i,Mlen};
        }
    }
    line[z].v=0;
    ma key;
    int m=n-1;

    while(m--){
        int Min=Mlen;
        for(int i=0;i<len;i++){
            if(line[i].v!=0&&line[i].v<Min){
                key=line[i];
                Min=key.v;
            }
        }
        cout<<str[key.h1]<<" "<<str[key.h2]<<" "<<key.v<<endl;
        z=key.h2;
        line[z].v=0;
        for(int j=0;j<len;j++){
            if(mar[z][j].k==1&&line[j].v!=0){
                if(mar[z][j].value<line[j].v){
                    line[j].h1=z;
                    line[j].v=mar[z][j].value;
                }
            }
        }
/*
0   1(6)1(1)1(5)0   0
0   0   1(5)0   1(3)0
0   0   0   1(5)1(6)1(4)
0   0   0   0   0   1(2)
0   0   0   0   0   1(6)
0   0   0   0   0   0
*/
    }
}

void change(int visit[], int a, int b){//将两个顶点及与他们相通的顶点改成同样的值表示
                                              //他们相通
    for(int i= 0; i< n; i++)
      if(visit[i]== a)
        visit[i]= b;

}
void kruskal(){
    int*visit=new int[n];
    for(int i=0;i<n;i++){
        visit[i]=i;
    }
    cout<<"kruskal:"<<endl;
    int Min=Mlen;
    ma*line=new ma[n];
    for(int i=0;i<n;i++){
        line[i]={-1,-1,Mlen};
    }
    ma kk;
    for(int p=0;p<n;p++){

        for(int i=0;i<n;i++)
            for(int j=0;j<n;j++){
                    if(visit[i]==1&&visist[j]==1)
                //判断该边是否可能成环
                int ww=0;
                for(int w=0;w<p;w++){
                    if(line[w].h1==i||line[w].h2==i)
                        ww++;
                    if(line[w].h1==j||line[w].h2==j)
                        ww++;
                }
                if(ww>=2)
                    continue;
                if(mar[i][j].value>0&&mar[i][j].value<Min)
                    Min=mar[i][j].value;
                    //cout<<Min<<" ";
                    kk.h1=i;
                    kk.h2=j;
                    kk.v=Min;
                    //kk={i,j,mar[i][j].value};
        }

        cout<<str[kk.h1]<<" "<<str[kk.h2]<<" "<<kk.v<<endl;
        visit[kk.h1]=1;
        visit[kk.h2]=1;
        mar[kk.h1][kk.h2].value=0;
        mar[kk.h2][kk.h1].value=0;
        line[p]=kk;
    }
}
int main(){
    cin>>n;
    create();
    prim();
    kruskal();
    return 0;
}

#include<iostream>
using namespace std;
const int Max=100;
const int Mlen=1000;
int n;
int q;

struct ma {
	int h1;
	int h2;
	int v;
};
int mar[Max][Max];
int*visit;

void create(){
    cin>>n;
    for(int i=0;i<Max;i++){
        for(int j=0;j<Max;j++){
            mar[i][j]=-1;
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>mar[i][j];
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cout<<mar[i][j];
            cout<<"   ";
        }
        cout<<endl;
    }
    visit= new int[n];
	for (int i = 0; i<n; i++) {
		visit[i] = -1;
	}
    cin>>q;
    for(int i=0;i<q;i++){
        int m1,m2;
        cin>>m1>>m2;
        int t1=m1-1;
        int t2=m2-1;
        mar[t1][t2]=0;
        mar[t2][t1]=0;
        if (visit[t1] != -1 && visit[t2] == -1) {
			visit[t2] = visit[t1];
		}
		if (visit[t2] != -1 && visit[t1] == -1) {
			visit[t1] = visit[t2];
		}
		if (visit[t2] == -1 && visit[t1] == -1) {
			visit[t1] = t1;
			visit[t2] = t1;
		}
		if (visit[t1] != -1 && visit[t2] != -1) {
			int mm = visit[t2];
			for (int f = 0; f<n; f++) {
				if (visit[f] == mm) {
					visit[f] = visit[t1];
				}
			}
		}

    }
    for (int i = 0; i<n; i++) {
		cout<<visit[i]<<" ";
	}
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cout<<mar[i][j];
            cout<<"   ";
        }
        cout<<endl;
    }
}


void kruskal() {
    int ans=0;

	int Min;
	ma kk;
	while(true) {//路径数目不一定等于点数减一
		Min = Mlen;
		for (int i = 0; i<n; i++) {
			for (int j = 0; j<n; j++) {
				if (visit[i] != -1 && visit[j] != -1) {
					if (visit[i] == visit[j]) {
						continue;
					}
				}
				if (mar[i][j]>0 && mar[i][j]<Min) {
					Min = mar[i][j];
					kk.h1 = i;
					kk.h2 = j;
					kk.v = Min;
				}
			}
		}
		int t1 = kk.h1;
		int t2 = kk.h2;
		ans+=kk.v;

		if (visit[t1] != -1 && visit[t2] == -1) {
			visit[t2] = visit[t1];
		}
		if (visit[t2] != -1 && visit[t1] == -1) {
			visit[t1] = visit[t2];
		}
		if (visit[t2] == -1 && visit[t1] == -1) {
			visit[t1] = t1;
			visit[t2] = t1;
		}
		if (visit[t1] != -1 && visit[t2] != -1) {
			int mm = visit[t2];
			for (int f = 0; f<n; f++) {
				if (visit[f] == mm) {
					visit[f] = visit[t1];
				}
			}
		}
		mar[kk.h1][kk.h2] = 0;
		mar[kk.h2][kk.h1] = 0;
		int zzz=0;
		for(int i=0;i<n;i++){
            if(visit[i]==-1){
                zzz=1;
            }
		}
		if(zzz==0){
            break;
		}


	}
	cout<<ans<<endl;

}
int main(){
    create();
    kruskal();
    return 0;
}
/*
4
0 990 1000 5
990 0 179 0
1000 179 0 26
5 0 26 0
2
1 2
4 3

4
0 990 692 5
990 0 5 0
692 5 0 26
5 0 26 0
2
1 2
4 3

4
0 990 692 5
990 0 179 0
692 179 0 26
5 0 26 0
3
1 2
2 3
1 4

3
0 990 692
990 0 179
692 179 0
2
1 2
1 3
*/

还剩一个问题：最小生成树的权值之和如何提前输出

#include<iostream>
#include<string>
using namespace std;
const int Max=20;
const int Mlen=9999;

struct zp{
int k;
int value;
};

struct ma{
    int h1;
    int h2;
    int v;
};

zp mar[Max][Max];
string*str;
int n,len;

void create(){
    for(int i=0;i<Max;i++)
        for(int j=0;j<Max;j++){
            mar[i][j].k=-1;
            mar[i][j].value=-1;
        }
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++){
            mar[i][j].k=0;
            mar[i][j].value=0;
        }
    str=new string[n];
    for(int i=0;i<n;i++){
        cin>>str[i];
    }
    cin>>len;
    for(int i=0;i<len;i++){
        string s1,s2;
        int num;
        cin>>s1>>s2>>num;
        int z1,z2;
        for(int i=0;i<n;i++){
            if(str[i]==s1)
                z1=i;
            if(str[i]==s2)
                z2=i;
        }
        mar[z1][z2].k=1;
        mar[z1][z2].value=num;
        mar[z2][z1].k=1;
        mar[z2][z1].value=num;
    }
     for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cout<<mar[i][j].k;
            if(mar[i][j].k==1){
                cout<<"("<<mar[i][j].value<<")";
            }else{
            cout<<"   ";
            }
            //mar[i][j].value;
        }
        cout<<endl;
    }
}
void prim(){
    int ans=0;
    string u;
    cin>>u;
    cout<<"prim:"<<endl;
    int z;
    for(int i=0;i<n;i++){
        if(str[i]==u){
            z=i;
        }
    }
    ma*line=new ma[len];
    for(int i=0;i<len;i++){
        if(i!=z&&mar[z][i].k==1){
            line[i]={ z,i,mar[z][i].value};
        }else{
            line[i]={ -1,i,Mlen};
        }
    }
    line[z].v=0;
    ma key;
    int m=n-1;

    while(m--){
        int Min=Mlen;
        for(int i=0;i<len;i++){
            if(line[i].v!=0&&line[i].v<Min){
                key=line[i];
                Min=key.v;
            }
        }
        cout<<str[key.h1]<<" "<<str[key.h2]<<" "<<key.v<<endl;
        z=key.h2;
        line[z].v=0;
        for(int j=0;j<len;j++){
            if(mar[z][j].k==1&&line[j].v!=0){
                if(mar[z][j].value<line[j].v){
                    line[j].h1=z;
                    line[j].v=mar[z][j].value;
                }
            }
        }
    }
}

void kruskal(){
    int*visit=new int[n];
    for(int i=0;i<n;i++){
        visit[i]=-1;
    }
    cout<<"kruskal:"<<endl;
    int Min;
    ma*line=new ma[n];
    for(int i=0;i<n;i++){
        line[i]={-1,-1,Mlen};
    }
    ma kk;
    for(int p=0;p<n-1;p++){
        Min=Mlen;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(visit[i]!=-1&&visit[j]!=-1){
                    if(visit[i]==visit[j]){
                        continue;
                    }
                }
                //判断该边是否可能成环
                if(mar[i][j].value>0&&mar[i][j].value<Min){
                    Min=mar[i][j].value;
                    //cout<<Min<<" ";
                    kk.h1=i;
                    kk.h2=j;
                    kk.v=Min;
                    //kk={i,j,mar[i][j].value};
                }
            }
        }
        int t1 =kk.h1;
        int t2 =kk.h2;
        cout<<str[t1]<<" "<<str[t2]<<" "<<kk.v<<endl;

        if(visit[t1]!=-1&&visit[t2]==-1){
            visit[t2]=visit[t1];
        }
        if(visit[t2]!=-1&&visit[t1]==-1){
            visit[t1]=visit[t2];
        }
        if(visit[t2]==-1&&visit[t1]==-1){
            visit[t1]=t1;
            visit[t2]=t1;
        }
        if(visit[t1]!=-1&&visit[t2]!=-1){
            int mm=visit[t2];
            for(int f=0;f<n;f++){
                if(visit[f]==mm){
                    visit[f]=visit[t1];
                }
            }
        }
        mar[kk.h1][kk.h2].value=0;
        mar[kk.h2][kk.h1].value=0;
        line[p]=kk;
    }
}
int main(){
    cin>>n;
    create();
    prim();
    kruskal();
    return 0;
}

搞定：

#include<iostream>
#include<string>
using namespace std;
const int Max=20;
const int Mlen=9999;

struct zp{
int k;
int value;
};

struct ma{
    int h1;
    int h2;
    int v;
};

zp mar[Max][Max];
string*str;
int n,len;
string u;

void create(){
    for(int i=0;i<Max;i++)
        for(int j=0;j<Max;j++){
            mar[i][j].k=-1;
            mar[i][j].value=-1;
        }
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++){
            mar[i][j].k=0;
            mar[i][j].value=0;
        }
    str=new string[n];
    for(int i=0;i<n;i++){
        cin>>str[i];
    }
    cin>>len;
    for(int i=0;i<len;i++){
        string s1,s2;
        int num;
        cin>>s1>>s2>>num;
        int z1,z2;
        for(int i=0;i<n;i++){
            if(str[i]==s1)
                z1=i;
            if(str[i]==s2)
                z2=i;
        }
        mar[z1][z2].k=1;
        mar[z1][z2].value=num;
        mar[z2][z1].k=1;
        mar[z2][z1].value=num;
    }
}
void ans(){
    int ans=0;
    cin>>u;
    int z;
    for(int i=0;i<n;i++){
        if(str[i]==u){
            z=i;
        }
    }
    ma*line=new ma[len];
    for(int i=0;i<len;i++){
        if(i!=z&&mar[z][i].k==1){
            line[i]={ z,i,mar[z][i].value};
        }else{
            line[i]={ -1,i,Mlen};
        }
    }
    line[z].v=0;
    ma key;
    int m=n-1;

    while(m--){
        int Min=Mlen;
        for(int i=0;i<len;i++){
            if(line[i].v!=0&&line[i].v<Min){
                key=line[i];
                Min=key.v;
            }
        }
        ans+=key.v;
        //cout<<str[key.h1]<<" "<<str[key.h2]<<" "<<key.v<<endl;
        z=key.h2;
        line[z].v=0;
        for(int j=0;j<len;j++){
            if(mar[z][j].k==1&&line[j].v!=0){
                if(mar[z][j].value<line[j].v){
                    line[j].h1=z;
                    line[j].v=mar[z][j].value;
                }
            }
        }
    }
    cout<<ans<<endl;
}

void prim(){
    int ans=0;
   // string u;
    //cin>>u;
    cout<<"prim:"<<endl;
    int z;
    for(int i=0;i<n;i++){
        if(str[i]==u){
            z=i;
        }
    }
    ma*line=new ma[len];
    for(int i=0;i<len;i++){
        if(i!=z&&mar[z][i].k==1){
            line[i]={ z,i,mar[z][i].value};
        }else{
            line[i]={ -1,i,Mlen};
        }
    }
    line[z].v=0;
    ma key;
    int m=n-1;

    while(m--){
        int Min=Mlen;
        for(int i=0;i<len;i++){
            if(line[i].v!=0&&line[i].v<Min){
                key=line[i];
                Min=key.v;
            }
        }
        cout<<str[key.h1]<<" "<<str[key.h2]<<" "<<key.v<<endl;
        z=key.h2;
        line[z].v=0;
        for(int j=0;j<len;j++){
            if(mar[z][j].k==1&&line[j].v!=0){
                if(mar[z][j].value<line[j].v){
                    line[j].h1=z;
                    line[j].v=mar[z][j].value;
                }
            }
        }
    }
}

void kruskal(){
    int*visit=new int[n];
    for(int i=0;i<n;i++){
        visit[i]=-1;
    }
    cout<<"kruskal:"<<endl;
    int Min;
    ma*line=new ma[n];
    for(int i=0;i<n;i++){
        line[i]={-1,-1,Mlen};
    }
    ma kk;
    for(int p=0;p<n-1;p++){
        Min=Mlen;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(visit[i]!=-1&&visit[j]!=-1){
                    if(visit[i]==visit[j]){
                        continue;
                    }
                }
                //判断该边是否可能成环
                if(mar[i][j].value>0&&mar[i][j].value<Min){
                    Min=mar[i][j].value;
                    //cout<<Min<<" ";
                    kk.h1=i;
                    kk.h2=j;
                    kk.v=Min;
                    //kk={i,j,mar[i][j].value};
                }
            }
        }
        int t1 =kk.h1;
        int t2 =kk.h2;
        cout<<str[t1]<<" "<<str[t2]<<" "<<kk.v<<endl;

        if(visit[t1]!=-1&&visit[t2]==-1){
            visit[t2]=visit[t1];
        }
        if(visit[t2]!=-1&&visit[t1]==-1){
            visit[t1]=visit[t2];
        }
        if(visit[t2]==-1&&visit[t1]==-1){
            visit[t1]=t1;
            visit[t2]=t1;
        }
        if(visit[t1]!=-1&&visit[t2]!=-1){
            int mm=visit[t2];
            for(int f=0;f<n;f++){
                if(visit[f]==mm){
                    visit[f]=visit[t1];
                }
            }
        }
        mar[kk.h1][kk.h2].value=0;
        mar[kk.h2][kk.h1].value=0;
        line[p]=kk;
    }
}
int main(){
    cin>>n;
    create();
    ans();
    prim();
    kruskal();
    return 0;
}

正确，最终版：

#include<iostream>
#include<string>
using namespace std;
const int Max=20;
const int Mlen=9999;

struct zp{
int k;
int value;
};

struct ma{
    int h1;
    int h2;
    int v;
};

zp mar[Max][Max];
string*str;
int n,len;
string u;

void create(){
    for(int i=0;i<Max;i++)
        for(int j=0;j<Max;j++){
            mar[i][j].k=-1;
            mar[i][j].value=-1;
        }
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++){
            mar[i][j].k=0;
            mar[i][j].value=0;
        }
    str=new string[n];
    for(int i=0;i<n;i++){
        cin>>str[i];
    }
    cin>>len;
    for(int i=0;i<len;i++){
        string s1,s2;
        int num;
        cin>>s1>>s2>>num;
        int z1,z2;
        for(int i=0;i<n;i++){
            if(str[i]==s1)
                z1=i;
            if(str[i]==s2)
                z2=i;
        }
        mar[z1][z2].k=1;
        mar[z1][z2].value=num;
        mar[z2][z1].k=1;
        mar[z2][z1].value=num;
    }
}
void ans(){
    int ans=0;
    cin>>u;
    int z;
    for(int i=0;i<n;i++){
        if(str[i]==u){
            z=i;
        }
    }
    ma*line=new ma[len];
    for(int i=0;i<len;i++){
        if(i!=z&&mar[z][i].k==1){
            line[i]={ z,i,mar[z][i].value};
        }else{
            line[i]={ -1,i,Mlen};
        }
    }
    line[z].v=0;
    ma key;
    int m=n-1;

    while(m--){
        int Min=Mlen;
        for(int i=0;i<len;i++){
            if(line[i].v!=0&&line[i].v<Min){
                key=line[i];
                Min=key.v;
            }
        }
        ans+=key.v;
        z=key.h2;
        line[z].v=0;
        for(int j=0;j<len;j++){
            if(mar[z][j].k==1&&line[j].v!=0){
                if(mar[z][j].value<line[j].v){
                    line[j].h1=z;
                    line[j].v=mar[z][j].value;
                }
            }
        }
    }
    cout<<ans<<endl;
}

void prim(){
    int ans=0;
   // string u;
    //cin>>u;
    cout<<"prim:"<<endl;
    int z;
    for(int i=0;i<n;i++){
        if(str[i]==u){
            z=i;
        }
    }
    ma*line=new ma[len];
    for(int i=0;i<len;i++){
        if(i!=z&&mar[z][i].k==1){
            line[i]={ z,i,mar[z][i].value};
        }else{
            line[i]={ -1,i,Mlen};
        }
    }
    line[z].v=0;
    ma key;
    int m=n-1;

    while(m--){
        int Min=Mlen;
        for(int i=0;i<len;i++){
            if(line[i].v!=0&&line[i].v<Min){
                key=line[i];
                Min=key.v;
            }
        }
        cout<<str[key.h1]<<" "<<str[key.h2]<<" "<<key.v<<endl;
        z=key.h2;
        line[z].v=0;
        for(int j=0;j<len;j++){
            if(mar[z][j].k==1&&line[j].v!=0){
                if(mar[z][j].value<line[j].v){
                    line[j].h1=z;
                    line[j].v=mar[z][j].value;
                }
            }
        }
    }
}

void kruskal(){
    int*visit=new int[n];
    for(int i=0;i<n;i++){
        visit[i]=-1;
    }
    cout<<"kruskal:"<<endl;
    int Min;
    ma*line=new ma[n];
    for(int i=0;i<n;i++){
        line[i]={-1,-1,Mlen};
    }
    ma kk;
    for(int p=0;p<n-1;p++){
        Min=Mlen;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(visit[i]!=-1&&visit[j]!=-1){
                    if(visit[i]==visit[j]){
                        continue;
                    }
                }
                if(mar[i][j].value>0&&mar[i][j].value<Min){
                    Min=mar[i][j].value;
                    kk.h1=i;
                    kk.h2=j;
                    kk.v=Min;
                }
            }
        }
        int t1 =kk.h1;
        int t2 =kk.h2;
        cout<<str[t1]<<" "<<str[t2]<<" "<<kk.v<<endl;

        if(visit[t1]!=-1&&visit[t2]==-1){
            visit[t2]=visit[t1];
        }
        if(visit[t2]!=-1&&visit[t1]==-1){
            visit[t1]=visit[t2];
        }
        if(visit[t2]==-1&&visit[t1]==-1){
            visit[t1]=t1;
            visit[t2]=t1;
        }
        if(visit[t1]!=-1&&visit[t2]!=-1){
            int mm=visit[t2];
            for(int f=0;f<n;f++){
                if(visit[f]==mm){
                    visit[f]=visit[t1];
                }
            }
        }
        mar[kk.h1][kk.h2].value=0;
        mar[kk.h2][kk.h1].value=0;
        line[p]=kk;
    }
}
int main(){
    cin>>n;
    create();
    ans();
    prim();
    kruskal();
    return 0;
}

第二题，还不错

#include<iostream>
#include<queue>
#include<cmath>
using namespace std;
const int Maxn=100;
int mar[Maxn][Maxn];



struct ma{
int k=0;//错误： ISO C ++禁止非const静态成员'k'的类内初始化
int x;
int y;
};

double ans(int x1,int y1,int x2,int y2){
    double b;
    b=sqrt(pow(x1-x2,2)+pow(y1-y2,2));
    return b;
}

void BFS(int m, int n, int Ma[Maxn][Maxn], bool*visit,int*findt) {
	queue<int>q;
	q.push(m);
	while (!q.empty()) {
		int v = q.front();
		if (visit[v] != true) {
			cout << v << " ";
			findt[v]=1;
			visit[v] = true;
		}
		q.pop();
		for (int i = 0; i < n; i++) {
			if (Ma[v][i] == 1 && visit[i] != true) {
				visit[i] = true;
				cout << i << " ";
				findt[i]=1;
				q.push(i);
			}
		}
	}
}

int main(){
    int n,d;
    cin>>n>>d;
    ma*st=new ma[n];
    for(int i=0;i<n;i++){
        cin>>st[i].x>>st[i].y;
    }
    char k;

    for(int i=0;i<Maxn;i++){
        for(int j=0;j<Maxn;j++){
            mar[i][j]=-1;
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            mar[i][j]=0;
        }
    }

    while(cin>>k){
        if(k=='O'){
            int num;
            cin>>num;
            int z=num-1;
            st[z].k=1;
            for(int i=0;i<n;i++){
                if(i==z)
                    continue;
                if(st[i].k==1){
                    double an=ans(st[z].x,st[z].y,st[i].x,st[i].y);
                    if(an<=d){
                        mar[z][i]=1;
                        mar[i][z]=1;
                    }
                }
            }
        }
        if(k=='S'){
            int u1,u2;
            cin>>u1>>u2;
            int t1,t2;
            t1=u1-1;
            t2=u2-1;
            bool*visit = new bool[n];
            int*findt=new int[n];
            for (int i = 0; i < n; i++) {
                visit[i] = false;
                findt[i]=-0;
            }
            BFS(t1,n,mar,visit,findt);
            cout<<endl;
            if(findt[t2]==1){
                cout<<"SUCCESS"<<endl;
            }else{
            cout<<"FAIL"<<endl;
            }
        }
    }

    return 0;

}

这次没有问题了，非静态不要在结构体内初始化

#include<iostream>
#include<queue>
#include<cmath>
using namespace std;
const int Maxn=100;
int mar[Maxn][Maxn];


struct ma{
int k;
int x;
int y;
};

double ans(int x1,int y1,int x2,int y2){
    double b;
    b=sqrt(pow(x1-x2,2)+pow(y1-y2,2));
    return b;
}

void BFS(int m, int n, int Ma[Maxn][Maxn], bool*visit,int*findt) {
	queue<int>q;
	q.push(m);
	while (!q.empty()) {
		int v = q.front();
		if (visit[v] != true) {
			findt[v]=1;
			visit[v] = true;
		}
		q.pop();
		for (int i = 0; i < n; i++) {
			if (Ma[v][i] == 1 && visit[i] != true) {
				visit[i] = true;
				findt[i]=1;
				q.push(i);
			}
		}
	}
}

int main(){
    int n,d;
    cin>>n>>d;
    ma*st=new ma[n];
    for(int i=0;i<n;i++){
        st[i].k=0;
        cin>>st[i].x>>st[i].y;
    }
    char k;

    for(int i=0;i<Maxn;i++){
        for(int j=0;j<Maxn;j++){
            mar[i][j]=-1;
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            mar[i][j]=0;
        }
    }

    while(cin>>k){
        if(k=='O'){
            int num;
            cin>>num;
            int z=num-1;
            st[z].k=1;
            for(int i=0;i<n;i++){
                if(i==z)
                    continue;
                if(st[i].k==1){
                    double an=ans(st[z].x,st[z].y,st[i].x,st[i].y);
                    if(an<=d){
                        mar[z][i]=1;
                        mar[i][z]=1;
                    }
                }
            }
        }
        if(k=='S'){
            int u1,u2;
            cin>>u1>>u2;
            int t1,t2;
            t1=u1-1;
            t2=u2-1;
            bool*visit = new bool[n];
            int*findt=new int[n];
            for (int i = 0; i < n; i++) {
                visit[i] = false;
                findt[i]=-0;
            }
            BFS(t1,n,mar,visit,findt);
            if(findt[t2]==1){
                cout<<"SUCCESS"<<endl;
            }else{
            cout<<"FAIL"<<endl;
            }
        }
    }

    return 0;

}

第三题感觉没什么问题，但就是过不了，错误50%

#include<iostream>
using namespace std;
const int Max=100;
const int Mlen=1000;
int n;
int q;

struct zp{
int k;
int value;
};
struct ma {
	int h1;
	int h2;
	int v;
};
zp mar[Max][Max];

void create(){
    cin>>n;
    for(int i=0;i<Max;i++){
        for(int j=0;j<Max;j++){
            mar[i][j].k=-1;
            mar[i][j].value=-1;
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>mar[i][j].value;
            mar[i][j].k=0;
        }
    }

    cin>>q;
    for(int i=0;i<q;i++){
        int m1,m2;
        cin>>m1>>m2;
        int t1=m1-1;
        int t2=m2-1;
        mar[t1][t2].k=1;
        mar[t2][t1].k=1;
    }
}
void kruskal() {
    int ans=0;
	int*visit = new int[n];
	for (int i = 0; i<n; i++) {
		visit[i] = -1;
	}
	int Min;
	ma*line = new ma[n];
	for (int i = 0; i<n; i++) {
		line[i] = { -1,-1,Mlen };
	}
	ma kk;
	for (int p = 0; p<n -q- 1; p++) {
		Min = Mlen;
		for (int i = 0; i<n; i++) {
			for (int j = 0; j<n; j++) {
				if (visit[i] != -1 && visit[j] != -1) {
					if (visit[i] == visit[j]) {
						continue;
					}
				}
				if (mar[i][j].value>0 && mar[i][j].value<Min) {
					Min = mar[i][j].value;
					kk.h1 = i;
					kk.h2 = j;
					kk.v = Min;
				}
			}
		}
		int t1 = kk.h1;
		int t2 = kk.h2;
		ans+=kk.v;

		if (visit[t1] != -1 && visit[t2] == -1) {
			visit[t2] = visit[t1];
		}
		if (visit[t2] != -1 && visit[t1] == -1) {
			visit[t1] = visit[t2];
		}
		if (visit[t2] == -1 && visit[t1] == -1) {
			visit[t1] = t1;
			visit[t2] = t1;
		}
		if (visit[t1] != -1 && visit[t2] != -1) {
			int mm = visit[t2];
			for (int f = 0; f<n; f++) {
				if (visit[f] == mm) {
					visit[f] = visit[t1];
				}
			}
		}
		mar[kk.h1][kk.h2].value = 0;
		mar[kk.h2][kk.h1].value = 0;
		line[p] = kk;
	}
	cout<<ans<<endl;
}
int main(){
    create();
    kruskal();
    return 0;
}
/*
4
0 990 692 5
990 0 179 0
692 179 0 26
5 0 26 0
1
1 2

4
0 990 692 5
990 0 179 0
692 179 0 26
5 0 26 0
2
1 2
2 3

4
0 990 692 5
990 0 179 0
692 179 0 26
5 0 26 0
3
1 2
2 3
1 4
*/

0%

不知道哪里错了

#include<iostream>
using namespace std;
const int Max=100;
const int Mlen=1000;
int n;
int q;

struct ma {
	int h1;
	int h2;
	int v;
};
int mar[Max][Max];
int*visit;

void create(){
    cin>>n;
    for(int i=0;i<Max;i++){
        for(int j=0;j<Max;j++){
            mar[i][j]=-1;
        }
    }
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            cin>>mar[i][j];
        }
    }
    visit= new int[n];
	for (int i = 0; i<n; i++) {
		visit[i] = -1;
	}
    cin>>q;
    for(int i=0;i<q;i++){
        int m1,m2;
        cin>>m1>>m2;
        int t1=m1-1;
        int t2=m2-1;
        mar[t1][t2]=0;
        mar[t2][t1]=0;
        if (visit[t1] != -1 && visit[t2] == -1) {
			visit[t2] = visit[t1];
		}
		if (visit[t2] != -1 && visit[t1] == -1) {
			visit[t1] = visit[t2];
		}
		if (visit[t2] == -1 && visit[t1] == -1) {
			visit[t1] = t1;
			visit[t2] = t1;
		}
		if (visit[t1] != -1 && visit[t2] != -1) {
			int mm = visit[t2];
			for (int f = 0; f<n; f++) {
				if (visit[f] == mm) {
					visit[f] = visit[t1];
				}
			}
		}
    }
}


void kruskal() {
    int ans=0;

	int Min;
	ma kk;
	for (int p = 0; p<n -q- 1; p++) {
		Min = Mlen;
		for (int i = 0; i<n; i++) {
			for (int j = 0; j<n; j++) {
				if (visit[i] != -1 && visit[j] != -1) {
					if (visit[i] == visit[j]) {
						continue;
					}
				}
				if (mar[i][j]>0 && mar[i][j]<Min) {
					Min = mar[i][j];
					kk.h1 = i;
					kk.h2 = j;
					kk.v = Min;
				}
			}
		}
		int t1 = kk.h1;
		int t2 = kk.h2;
		ans+=kk.v;

		if (visit[t1] != -1 && visit[t2] == -1) {
			visit[t2] = visit[t1];
		}
		if (visit[t2] != -1 && visit[t1] == -1) {
			visit[t1] = visit[t2];
		}
		if (visit[t2] == -1 && visit[t1] == -1) {
			visit[t1] = t1;
			visit[t2] = t1;
		}
		if (visit[t1] != -1 && visit[t2] != -1) {
			int mm = visit[t2];
			for (int f = 0; f<n; f++) {
				if (visit[f] == mm) {
					visit[f] = visit[t1];
				}
			}
		}
		mar[kk.h1][kk.h2] = 0;
		mar[kk.h2][kk.h1] = 0;
	}
	cout<<ans<<endl;
}
int main(){
    create();
    kruskal();
    return 0;
}
/*
4
0 990 1000 5
990 0 179 0
1000 179 0 26
5 0 26 0
2
1 2
4 3

4
0 990 692 5
990 0 5 0
692 5 0 26
5 0 26 0
2
1 2
4 3

4
0 990 692 5
990 0 179 0
692 179 0 26
5 0 26 0
3
1 2
2 3
1 4

3
0 990 692
990 0 179
692 179 0
2
1 2
1 3
*/

错误：Run-Time Check Failure #3 - The variable 'kk' is being used without being initialized.

 

 

#include<iostream>
using namespace std;
const int Max = 100;
const int Mlen = 1000;
int n;
int q;

struct ma {
	int h1;
	int h2;
	int v;
};
int mar[Max][Max];
int*visit;

void create() {
	cin >> n;
	for (int i = 0; i<Max; i++) {
		for (int j = 0; j<Max; j++) {
			mar[i][j] = -1;
		}
	}
	for (int i = 0; i<n; i++) {
		for (int j = 0; j<n; j++) {
			cin >> mar[i][j];
		}
	}
	visit = new int[n];
	for (int i = 0; i<n; i++) {
		visit[i] = -1;
	}
	cin >> q;
	for (int i = 0; i<q; i++) {
		int m1, m2;
		cin >> m1 >> m2;
		int t1 = m1 - 1;
		int t2 = m2 - 1;
		mar[t1][t2] = 0;
		mar[t2][t1] = 0;
		if (visit[t1] != -1 && visit[t2] == -1) {
			visit[t2] = visit[t1];
		}
		if (visit[t2] != -1 && visit[t1] == -1) {
			visit[t1] = visit[t2];
		}
		if (visit[t2] == -1 && visit[t1] == -1) {
			visit[t1] = t1;
			visit[t2] = t1;
		}
		if (visit[t1] != -1 && visit[t2] != -1) {
			int mm = visit[t2];
			for (int f = 0; f<n; f++) {
				if (visit[f] == mm) {
					visit[f] = visit[t1];
				}
			}
		}

	}
}


void kruskal() {
	int ans = 0;

	int Min;
	ma kk;
	int zz = 0;
	for (int i = 0; i<n; i++) {
		if (visit[i] == -1) {
			zz = 1;
		}
	}
	while (zz) {
		Min = Mlen;
		for (int i = 0; i<n; i++) {
			for (int j = 0; j<n; j++) {
				if (visit[i] != -1 && visit[j] != -1) {
					if (visit[i] == visit[j]) {
						continue;
					}
				}
				if (mar[i][j]>0 && mar[i][j]<Min) {
					Min = mar[i][j];
					kk.h1 = i;
					kk.h2 = j;
					kk.v = Min;
				}
			}
		}
		int t1 = kk.h1;
		int t2 = kk.h2;
		ans += kk.v;

		if (visit[t1] != -1 && visit[t2] == -1) {
			visit[t2] = visit[t1];
		}
		if (visit[t2] != -1 && visit[t1] == -1) {
			visit[t1] = visit[t2];
		}
		if (visit[t2] == -1 && visit[t1] == -1) {
			visit[t1] = t1;
			visit[t2] = t1;
		}
		if (visit[t1] != -1 && visit[t2] != -1) {
			int mm = visit[t2];
			for (int f = 0; f<n; f++) {
				if (visit[f] == mm) {
					visit[f] = visit[t1];
				}
			}
		}
		mar[kk.h1][kk.h2] = 0;
		mar[kk.h2][kk.h1] = 0;
		int zzz = 0;
		for (int i = 0; i<n; i++) {
			if (visit[i] == -1) {
				zzz = 1;
			}
		}
		if (zzz == 0) {
			break;
		}
	}
	cout << ans << endl;

}
int main() {
	create();
	kruskal();
	return 0;
}

还是不过？？？？？？？什么问题啊怎么这么迷
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/Perce_Issac/article/details/84001904

智能推荐

前端开发之JS-bind函数的用法_前端bind_OrangeMonsterMM的博客-程序员秘密

bind函数的作用bind函数一般用来改变上下文环境，返回一个调用的函数。一般上下文环境指的就是this指向的环境，例如setTimeout中的this一般指向window；如下图所示，使用方法：funcname.bind( obj)(); 可以改变this指向柯里化函数柯里化：指的是当bind返回的函数用在new的情况下（构造函数），所指定的this不起作用。实现一个bind...

JAVA中的延时队列DelayQueue_Elivs的博客-程序员秘密

定义延时队列的元素import java.util.concurrent.Delayed;import java.util.concurrent.TimeUnit;public class DelayedItem&lt;T&gt; implements Delayed { /** * 到期时间，单位ms */ private long activeTime; private T data; public DelayedItem(long activeTime, T dat

激光雷达和相机的联合标定（Camera-LiDAR Calibration）之but_calibration_camera_velodyne_W_Tortoise的博客-程序员秘密

前言在前两篇博客中介绍的标定工具,只是 autoware 和 apollo 中的一部分，如果只做激光雷达和相机的标定工作，工作量有点大。 今天介绍的but_calibration_camera_velodyne相对轻量级。 论文： [1] Velas, Spanel, Materna, Herout: Calibration of RGB Camera with Velodyne LiD...

通过新浪天气api查询天气_wephper的博客-程序员秘密

通过新浪天气api,查询天气,获取天气信息api,获取天气api,ios获取天气信息api,百度地图api获取天气,获取天气信息api接口,天气预报获取api接口,未来三天全国天气预报,未来三天全国天气,未来三天天气预报

RuntimeError: CUDA error: CUBLAS_STATUS_INTERNAL_ERROR when calling `cublasCreate(handle)`_你的宣妹的博客-程序员秘密

RuntimeError: CUDA error: CUBLAS_STATUS_INTERNAL_ERROR when calling cublasCreate(handle)``出现这个问题可能有很多原因，如果版本检查pytorch和CUDA匹配的话，一定检查一下你的网络结构设置的正不正确，有没有初始化参数写错、tensor大小不相容的错误，亲测有效，我的网络初始化需要一个参数改变最后隐藏层的数目，因为忘记设置，数据大小和网络不匹配，就会报这个错！...

vant移动端实现tab锚点定位和tab随滚动条自动切换_vant 侧边栏 页面上下滑动_小智玩前端的博客-程序员秘密

我们先实现锚点定位，锚点定位需要借助方法，这个方法会把当前元素的顶部定位到所在有滚动条的父元素的顶部，从而实现锚点定位的功能：注：上面不一定要使用a标签来点击定位，其他标签的点击也是可以的，这里用是因为a标签自带点击的手势图标；实现锚点定位并不难，只需要用方法，接下来要实现滚动条滚动到哪个元素的顶部，tab就对应切换；下面先了解几个方法的区别：，，clientHeight：带有滚动条盒子的高度scrollHeight：带有滚动条盒子里面的滚动内容的高度scrollTop：滚动内容被卷入的高度

随便推点

程序员都在疯转的表情包_黑马程序员官方的博客-程序员秘密

程序员被BUG逼入魔的幻想当一个刚毕业的程序员新手说在我的代码里发现了一个 bug 时程序员的样子程序员的蜗居程序员高手是这样消灭 bug 的当软件公司只有她一个是女程序员时，女程序员的...

【C应用】红外遥控小车程序分析（上）——四轮马达方向控制程序分析_counter_1ms什么意思_米杰的声音的博客-程序员秘密

前言：基于STM32主控，通过操作红外线遥控器控制小车方向运动

PyQT5 中的QTableWidget 信号_pyqt5 cellchanged(int,int)[email protected]*的博客-程序员秘密

QTableView类属性showGrid是否显示网格 gridStyle绘制网格的样式NoPen没有网格SolidLine简单的线条DashLine破折号DotLine点DashDotLine交替的点和破折号DashDotDotLine一个破折号，两个点，一个破折号，两个点CustomDashLine使用定义的自定义模式sortingEnabled是否启用排序...

HUNAU—exercise3_动态规划_程序员的冷浪漫的博客-程序员秘密

HDU 1231  最大连续子序列求最长连续子序列的和#include#include#include#include#includeusing namespace std;#define M 10002#define INF 1<<29int a[M],n;void solve(){ int sum=0,big=-INF; int j=0,first

Oracle 中的 TO_DATE 和 TO_CHAR 函数_oracle sysdate tochar_hemingwang0902的博客-程序员秘密

oracle 中 TO_DATE 函数的时间格式，以 2008-09-10 23:45:56 为例 格式 说明 显示值 备注  Year(年): yytwo digits(两位年)08 yyythree digits(三位年)008 

mac 键盘失灵_MacBook Pro键盘失灵解决方案_weixin_39691055的博客-程序员秘密

我的笔记本键盘是上午上班第一次打开时还可以使用，中间不知道怎么了就突然失灵了，只有电源键有用，触控板都反应了。，网上百度到两种方案，第二个成功解决了问题。第一个方法，重置一下NVRAM：首先关机，然后在按开机键后立即同时按下option+command+P+R，听到3-4边启动声音后松手(按好几十秒钟那，自己找个了个地方，因为声音不小，办公区都可以听到。。)，进入系统，看看键盘和触控板是不是恢复正...

推荐文章

热门文章

相关标签