题解：P5934 [清华集训 2012] 最小生成树
原题传送门
思路
我们先思考一下什么时候一条边会出现在最小生成树上，根据 kruskal 的实现过程，我们可以发现如果这条边的边权是连接它两端端点所在联通块中所有边中最小的，那么这条边一定会出现在最小生成树中，而最大生成树同理，我们可以发现如果这条边的边权是连接它两端端点所在联通块中所有边中最大的，那么这条边一定会出现在最大生成树中，现在的问题是如何保证这条边是最小或最大的。
其实很简单，只需要将连接这两个联通块之间比这条边小的边都删除就好了，这时我们就会想到最小割，这样我们就可以以最小的代价断开这两个连通块，那么实现思路就很明了了，首先把所有小于这条边边权的边提出来，建成一个图后以两个端点分别为汇点和源点跑最大流，然后把所有大于这条边边权的边提出来，建成一个图后以两个端点分别为汇点和源点跑最大流，将答案加起来即可。
代码
#include<bits/stdc++.h>
#define int long long
#define inf 0x7f7f7f7f
#define mod 1000000007
using namespace std;
const int maxn = 1e6 + 100;
inline int read() {
int x = 0 , f = 1;
char ch = getchar();
while (ch < '0' || ch > '9' ) {if (ch == '-') f = -1; ch = getchar();}
while (ch >= '0' && ch <= '9') { x = x * 10 + ch - 48; ch = getchar();}
return x * f;
}
inline void write(int x) {
if(x < 0) x = ~(x - 1) , putchar('-');
if(x > 9) write(x / 10);
putchar(x % 10 + '0');
}
inline void writeh(int x) {
write(x);
putchar('\n');
}
inline void writek(int x) {
write(x);
putchar(' ');
}
int n , m , u , v , w , head[maxn] , tot = 1 , dis[maxn] , cul[maxn] , l;
struct edge {
int to , next , w;
}e[maxn];
struct node {
int u , v , w;
}t[maxn];
inline void add(int u , int w , int v) {
e[++tot].to = v;
e[tot].w = w;
e[tot].next = head[u];
head[u] = tot;
}
inline void adde(int u , int v , int w) {
add(u , w , v);
add(v , 0 , u);
}
inline bool bfs(int s , int t) {
queue<int> q;
q.push(s);
memset(dis , -1 , sizeof(dis));
dis[s] = 0;
while(!q.empty()) {
int u = q.front();
q.pop();
for(int i = head[u]; i; i = e[i].next) {
int v = e[i].to;
if(dis[v] == -1 && e[i].w) {
dis[v] = dis[u] + 1;
q.push(v);
}
}
}
return dis[t] != -1;
}
inline int dfs(int u , int sum , int t) {
if(u == t) return sum;
int last = sum;
for(int i = cul[u]; i; i = e[i].next) {
cul[u] = i;
int v = e[i].to;
if(dis[v] == dis[u] + 1 && e[i].w) {
int w = dfs(v , min(last , e[i].w) , t);
e[i].w -= w;
e[i ^ 1].w += w;
last -= w;
if(!last) break;
}
}
return sum - last;
}
inline int maxflow(int s , int t) {
int ans = 0;
while(bfs(s , t)) {
memcpy(cul , head , sizeof(head));
ans += dfs(s , inf , t);
}
return ans;
}
signed main(){
n = read();
m = read();
for(int i = 1; i <= m; i++) {
u = read();
v = read();
w = read();
t[i] = {u , v , w};
}
u = read();
v = read();
l = read();
for(int i = 1; i <= m; i++) if(t[i].w > l) adde(t[i].u , t[i].v , 1) , adde(t[i].v , t[i].u , 1);
int sum = maxflow(u , v);
tot = 1;
memset(head , 0 , sizeof(head));
memset(e , 0 , sizeof(e));
for(int i = 1; i <= m; i++) if(t[i].w < l) adde(t[i].u , t[i].v , 1) , adde(t[i].v , t[i].u , 1);
sum += maxflow(u , v);
writeh(sum);
return !("wjl1100 qwq");
}