邻接矩阵不会爆= =
by Kalista @ 2018-07-31 18:25:50
@[Kalista](/space/show?uid=47350) ！！边数最多20w,开二维数组不会爆么？？~~重要的是邻接表怎么写啊Orz~~
by 4kilometers @ 2018-07-31 18:28:41
不不不，您要开的是点间距离而不是边数，只需要处理重边就可以了，然后，我好像没有写过不带优化的Prim板子= =
by Kalista @ 2018-07-31 18:30:05
@[Kalista](/space/show?uid=47350) Orz 是不才脑抽了
by 4kilometers @ 2018-07-31 18:36:16
vector<int> g[] 了解下
by Ouaoan @ 2018-07-31 18:39:46
感觉单纯用链式前向星会很复杂= =
by Kalista @ 2018-07-31 18:42:14
@[渣儿](/space/show?uid=13117) 我只想知道邻接表怎么做。。vector会用的说~
by 4kilometers @ 2018-07-31 20:33:36
@[Kalista](/space/show?uid=47350) 我邻接矩阵好像爆了大佬。。开[5001][5001]爆了
by 4kilometers @ 2018-07-31 20:48:07
```cpp
// Prim MST adjacency matrix
#include<bits/stdc++.h>
using namespace std;
const int maxN = 500;
const int maxM = 200001;
const int maxint = 2147483647;
int n,m,dis[maxN],d[maxN][maxN],mst = 0;
bool vis[maxN] = {false};
void Prim (int);
int main()
{
cin >> n >> m;
for (int i = 1; i <= n; ++ i)
{
for (int j = 1; j <= m; ++ j)
d[i][j] = maxint;
dis[i] = maxint;
}
for (int i = 1; i <= m; ++ i)
{
int xi,yi,zi;
cin >> xi >> yi >> zi;
d[xi][yi] = d[yi][xi] = zi;
}
Prim(1);
cout << mst;
return 0;
}
void Prim (int v0)
{
int u;
dis[v0] = 0;
for(int i = 1; i <= n; ++ i)
{
for (int j = 1; j <= n; ++j)
{
int minn = 2147483647;
if ( dis[j] < minn && ! vis[j] ) { minn = dis[j]; u = j; }
}
vis[u] = true;
mst += dis[u];
for (int j = 1; j <= n; ++j )
{
if ( d[u][j] < dis[j] && ! vis[j] )
dis[j] = d[u][j];
}
}
}
```
。。。像这样
by 4kilometers @ 2018-07-31 21:00:52
邻接表还过了一个点
by 4kilometers @ 2018-07-31 21:04:06