膜拜大佬@[石榴](/space/show?uid=38442)
by mengbierr @ 2017-06-26 14:53:38
送您两个模板。
```cpp
// Prim
#include <bits/stdc++.h>
#include<ext/pb_ds/priority_queue.hpp>
using namespace __gnu_pbds;
using namespace std;
char Buf[1 << 25], *buf = Buf;
int GetInt()
{
int in = 0, f = 1;
while(!isdigit(*buf)) f = *buf++ == '-' ? -1 : 1;
while(isdigit(*buf)) in = in * 10 + *buf++ - '0';
return in * f;
}
#define RUP(i, a, b) for (int i = (a), i##_end_ = (b); i < i##_end_; ++i)
#define REP(i, a, b) for (int i = (a), i##_end_ = (b); i > i##_end_; --i)
const int MAXN = 5005;
const int MAXM = 200005;
struct Node{
struct Edge{
Node* to;
int dis;
Edge* next;
}*edge;
Node() : edge(0){}
void Push(Node* to, int dis){
edge = new (Edge){to, dis, edge};
}
}node[MAXM];
struct Cmp{
bool operator () (Node::Edge* a, Node::Edge* b){
return a->dis > b->dis;
}
};
int n;
void Init()
{
int a, b, c, m;
#ifdef Kongse_qi
freopen("test.in", "r", stdin);
#endif
fread(Buf, 1, sizeof Buf, stdin);
n = GetInt(), m = GetInt();
while(m--)
{
a = GetInt(), b = GetInt(), c = GetInt();
node[a].Push(node + b, c);
node[b].Push(node + a, c);
}
return ;
}
void Prim()
{
int sum = 0, tot = 0;
__gnu_pbds::priority_queue<Node::Edge*, Cmp> pq;
bool exist[MAXN] = {0}; exist[1] = 1;
for(Node::Edge* e = node[1].edge; e; e = e->next)
{
pq.push(e);
}
while(!pq.empty() && ++tot < n)
{
Node::Edge *cur = pq.top();
while(exist[cur->to - node] && !pq.empty())
{
pq.pop(), cur = pq.top();
}
if(pq.empty()) break;
exist[cur->to - node] = 1;
sum += cur->dis;
for(Node::Edge* e = cur->to->edge; e; e = e->next)
{
if(!exist[e->to - node]) pq.push(e);
}
}
printf("%d\n", sum);
return ;
}
int main()
{
Init();
Prim();
return 0;
}
```
第二个
```cpp
/*
About: Prim
From: luogu
Auther: kongse_qi
Date: 2017.05.25
*/
#include <cstdio>
#include <vector>
#include <cstring>
#include <cstdlib>
#include <ctype.h>
#include <queue>
#include <stdarg.h>
const int maxn = 5005;
const int maxm = 200005;
#define RUP(i, a, b) for (int i = (a), i##_end_ = (b); i < i##_end_; ++i)
namespace IO{
static int in, f;
static char *X, *Buffer;
void Get_All()
{
fseek(stdin, 0, SEEK_END);
int file_lenth = ftell(stdin);
rewind(stdin);
X = Buffer = (char*)malloc(file_lenth);
fread(Buffer, 1, file_lenth, stdin);
return ;
}
#ifdef NEGATIVE
int Get_Int()
{
in = 0;
f = 1;
while(!isdigit(*X))
{
if(*X++ == '-') f = -1;
}
while(isdigit(*X))
{
in = in * 10 + *X++ - '0';
}
return in * f;
}
#else
int Get_Int()
{
in = 0;
while(!isdigit(*X)) ++X;
while(isdigit(*X))
{
in = in * 10 + *X++ - '0';
}
return in;
}
#endif
void Input(int num, ...)
{
va_list valist;
int* tmp;
va_start(valist, num);
RUP(i, 0, num)
{
tmp = va_arg(valist, int*);
*tmp = Get_Int();
}
va_end(valist);
return ;
}
}
using namespace IO;
struct Node{
struct Edge{
Node* to;
int dis;
Edge* next;
Edge(Node* t, int d, Edge* n):
to(t), dis(d), next(n){}
}*edge;
Node() : edge(0){}
void Push(Node* to, int dis)
{
edge = new Edge(to, dis, edge);
}
}node[maxm];
struct Cmp{
bool operator () (Node::Edge *x, Node::Edge *y)
{
return x->dis > y->dis;
}
};
int n, m, tot;
std::priority_queue<Node::Edge*, std::vector<Node::Edge*>, Cmp> pq;
bool wh[maxn];
void Read()
{
int a, b, c;
Input(2, &n, &m);
while(m--)
{
Input(3, &a, &b, &c);
node[a].Push(node + b, c);
node[b].Push(node + a, c);
}
return ;
}
void Prim()
{
int tot, sum = 0;
tot = wh[1] = 1;
for(Node::Edge *e = node[1].edge; e; e = e->next)
{
pq.push(e);
}
while(!pq.empty() && tot < n)
{
Node::Edge *cur = pq.top();
while(wh[cur->to - node] && !pq.empty())
{
pq.pop(); cur = pq.top();
}
if(pq.empty()) break;
sum += cur->dis;
++tot;
wh[cur->to - node] = 1;
for(Node::Edge *e = cur->to->edge; e; e = e->next)
{
if(!wh[e->to - node])
{
pq.push(e);
}
}
}
if(tot < n) printf("orz");
else printf("%d\n", sum);
return ;
}
int main()
{
freopen("test.in", "r", stdin);
Get_All();
Read();
Prim();
return 0;
}
```
by SeKong @ 2017-06-26 16:43:32
突然发现两个似乎是一样的...那再加一个Kruskal吧。。
```cpp
// Kruskal
#include <bits/stdc++.h>
#define RUP(i, a, b) for (int i = (a), i##_end_ = (b); i < i##_end_; ++i)
char Buf[1 << 25], *buf = Buf;
int GetInt()
{
int in = 0, f = 1;
while(!isdigit(*buf)) f = *buf++ == '-' ? -1 : 1;
while(isdigit(*buf)) in = in * 10 + *buf++ - '0';
return in * f;
}
const int MAXN = 5005;
const int MAXM = 200005;
struct Edge{
int st, en, weight;
friend bool operator < (const Edge& x, const Edge& y){
return x.weight < y.weight;
}
}edge[MAXM];
int n, m;
int Fa[MAXN], Lev[MAXN];
int Find_Fa(int cur) {return cur == Fa[cur] ? cur : Fa[cur] = Find_Fa(Fa[cur]);}
bool Join(int x, int y)
{
int u = Find_Fa(x);
int v = Find_Fa(y);
if(u == v) return false;
if(Lev[u] > Lev[v]) Fa[v] = u;
else
{
Fa[u] = v;
if(Lev[u] == Lev[v]) ++Lev[v];
}
return true;
}
void Init()
{
#ifdef Kongse_qi
freopen("test.in", "r", stdin);
#endif
int a, b, c;
Edge* tot = edge;
fread(Buf, 1, sizeof Buf, stdin);
n = GetInt(), m = GetInt();
RUP(i, 0, m)
{
a = GetInt(), b = GetInt(), c = GetInt();
*tot++ = (Edge){a, b, c};
}
std::sort(edge, edge + m);
RUP(i, 1, n + 1)
{
Fa[i] = i;
}
return ;
}
void Kruskal()
{
int sum = 0, tot = 1;
RUP(i, 0, m)
{
Edge& e = edge[i];
if(Join(e.st, e.en))
{
++tot;
sum += e.weight;
if(tot == n) break;
}
}
printf("%d\n", sum);
return ;
}
int main()
{
Init();
Kruskal();
return 0;
}
```
by SeKong @ 2017-06-26 16:45:06
```cpp
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
struct node
{
int from;
int to;
int w;
}a[200002];
int fa[5005];
int find(int x)
{
return fa[x]==x?x:fa[x]=find(fa[x]);
}
int cmp(node x,node y)
{
return x.w<y.w;
}
int main()
{
int n,m,ans=0,tot=0;
cin>>n>>m;
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&a[i].from,&a[i].to,&a[i].w);
}
sort(a+1,a+m+1,cmp);
for(int i=1;i<=n;i++)
{
fa[i]=i;
}
for(int i=1;i<=m;i++)
{
int fx=find(fa[a[i].from]),fy=find(fa[a[i].to]);
if(fx!=fy)
{
ans+=a[i].w;
fa[fx]=fy;
tot++;
if(tot==n-1)
{
printf("%d",ans);
return 0;
}
}
}
printf("orz");
// cout<<ans<<" "<<tot;
return 0;
}
```
by mengbierr @ 2017-06-26 17:12:14