# BZOJ 2561 最小生成树（最小割模型）

## 题解：

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;
}//其实不用排序
*/
e[cnt].fr = u;e[cnt].to = v;e[cnt].cap = c;
e[cnt].next = h[u];h[u] = cnt++;
e[cnt].fr = v;e[cnt].to = u;e[cnt].cap = 0;
e[cnt].next = h[v];h[v] = cnt++;
return;
}
bool BFS(int s,int t){
queue<int>q;
for(int i = 1;i <= n;++i){
d[i] = -1;
}
q.push(s);
d[s] = 0;
while(!q.empty()){
int now = q.front();
q.pop();
for(int i = h[now];i != -1;i = e[i].next){
int v = e[i].to;
if(d[v] == -1 && e[i].cap > 0){
d[v] = d[now]+1;
q.push(v);
}
}
}
if(d[t] != -1)return true;
return false;
}
int DFS(int x,int a,int t){
if(x == t || a == 0)return a;
int flow = 0,f;
for(int &i = cur[x];i != -1;i = e[i].next){
int v = e[i].to;
if(d[v] == d[x] + 1 && e[i].cap > 0){
f = min(a - flow,e[i].cap);
f = DFS(v,f,t);
flow += f;
e[i].cap -= f;
e[i^1].cap += f;
}
}
return flow;
}
int dinic(int s,int t){
int flow = 0;
while(BFS(s,t)){
for(int i = 1;i <= n;++i)cur[i] = h[i];
flow += DFS(s,INF,t);
}
return flow;
}
int u,v,l;
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin >> n >> m;
for(int i = 1;i <= m;++i){
cin >> e2[i].fr >> e2[i].to >> e2[i].dis;
}
int j = 0;
memset(h,-1,sizeof(h));
cnt = 0;
int ans = 0;
cin >> u >> v >> l;
for(int i = 1;i <= m;++i){
if(e2[i].dis < l){
}
}
ans += dinic(u,v);
memset(h,-1,sizeof(h));
cnt = 0;
for(int i = 1;i <= m;++i){
if(e2[i].dis > l){