这个题不是最小生成树吗?
by Bbaka @ 2019-10-16 12:21:49
@[IQZ_](/space/show?uid=138440) ~~不、、不懂qwq~~
感觉自己用的是贪心???
就一直找最小的来
by YVZH @ 2019-10-16 12:27:06
@[英华张子翀鸭](/space/show?uid=96266) 我看看吧
by Bbaka @ 2019-10-16 12:27:39
谢谢!!
by YVZH @ 2019-10-16 12:31:51
![](http://imgsrc.baidu.com/forum/pic/item/2bd8d935970a304e79434a3cdfc8a786cb175cd8.jpg)
by YVZH @ 2019-10-16 12:33:32
@[英华张子翀鸭](/space/show?uid=96266) 把t数组初始化为一个极大值你就可以通过样例并获得40分的好成绩
by Bbaka @ 2019-10-16 12:37:39
得,你好像初始化了...
by Bbaka @ 2019-10-16 12:39:40
啊啊刚刚不在
如果加一个输出
```#include<bits/stdc++.h>
using namespace std;
int n,t[110][110],ans=1000000;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>t[i][j];
}
}//读入
for(int di=1;di<=n;di++){
int cd=0,syb[110];
bool dis[110];
for(int ii=0;ii<110;ii++){
syb[ii]=0;
dis[ii]=true;
}
dis[di]=false;
syb[1]=di;
t[di][0]=100001;
for(int i=2;i<=n;i++){
int mn;
for(int j=1;j<=n;j++){
if(dis[j]){
if(t[syb[i-1]][syb[i]]>t[syb[i-1]][j]){
mn=t[syb[i-1]][j];
syb[i]=j;
}
}
}//j为下一个要选的
cd+=mn;
cout<<"aa"<<mn<<endl;
dis[syb[i]]=false;
}//i为选第i步
ans=min(ans,cd);
}//di为第一个选的
cout<<ans<<endl;
return 0;
}
```
样例跑出来是这样的:
```4
0 4 9 21
4 0 8 17
9 8 0 16
21 17 16 0
aa4
aa4
aa4
aa4
aa9
aa9
aa8
aa4
aa21
aa16
aa8
aa4
12
```
by YVZH @ 2019-10-16 12:47:04
@[IQZ_](/space/show?uid=138440)
QAQ
by YVZH @ 2019-10-16 12:47:24
# 大改AC结帖
```
#include<bits/stdc++.h>
using namespace std;
int t[105][105],vis[105],minn[105],ans,n;
int main(){
cin>>n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin>>t[i][j];
}
}//读入
int k=1;
vis[1]=1;
memset(minn,0x7f,sizeof(minn));
minn[1]=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(!vis[j]&&t[k][j]<minn[j]){
minn[j]=t[k][j];
}
}
int min=1000000;
for(int j=1;j<=n;j++){
if(!vis[j]&&min>minn[j]){
min=minn[j];
k=j;
}
}
vis[k]=1;
}//di为第一个选的
for(int i=1;i<=n;i++){
ans+=minn[i];
}
cout<<ans<<endl;
return 0;
}
```
by YVZH @ 2019-10-25 19:30:14