Tag-最小割

Icontofig 's Blog // 我们的征程是星辰大海！Away From OI，Come to ICPC（查看友链请点About Me）

代码

```#include <iostream>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <queue>
using namespace std;
int get_num(){
int num = 0;
char c;
bool flag = false;
while((c = getchar()) == ' ' || c == '\r' || c == '\n');
if(c == '-')
flag = true;
else num = c - '0';
while(isdigit(c = getchar()))
num = num * 10 + c - '0';
return (flag ? -1 : 1) * num;
}
const int maxn = 1e4+5;
int T;
typedef long long ll;
const ll INF = 1e15;
struct Flow{
struct edge{
int to,next;
ll cap;
}e[maxn<<2];
int h[maxn];
int cur[maxn];
int cnt;
void init(){
cnt = 0;
memset(h,-1,sizeof(h));
```

代码

```#include <bits/stdc++.h>
using namespace std;
int get_num(){
int num = 0;
char c;
bool flag = false;
while((c = getchar()) == ' ' || c == '\r' || c == '\n');
if(c == '-')
flag = true;
else num = c - '0';
while(isdigit(c = getchar()))
num = (num<<3) + (num<<1) + c - '0';
return (flag ? -1 : 1) * num;
}
int S,T;
const int maxn = 55;
const int maxm = 1005;
const int INF = 1e9;
struct Flow{
int h[maxn],cur[maxn];
struct edge{
int to,next,cap;
}e[maxm<<1];
int cnt;
e[cnt].to = v;e[cnt].next = h[u];e[cnt].cap = c;
h[u] = cnt++;
return;
}
int d[maxn];
bool BFS(int s,int t){
queue<int>q;
for(int i = s;i <= t;++i){
d[i] = INF;
}
d[s] = 0;
q.push(s);
while(!q.empty()){
int now = q.front();
q.pop();
for(int i = h[now];i != -1;i = e[i].next){
int v = e[i].t```

题解：

Kruskal算法是一种贪心算法，每次选择边权最小的一条边，检测一下两个端点是否都在一个并查集里，如果不是就加上这一条边，代表最小生成树选择这一条边。

代码：

```#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <algorithm>
#include <queue>
using namespace std;
const int maxn = 2e4+5;
const int maxm = 2e5+5;
struct edge{
int fr,to,next,cap;
}e[maxm<<3];
int cnt = 0;
int h[maxn];
int cur[maxn],d[maxn];
const int INF = 1e9;
struct edge2{
int fr,to,dis;
}e2[maxm];
int n,m;
/*
bool cmp(edge2 a,edge2 b){
return a.dis < b.dis;
}//其实不用排序
*/