#include <bits/stdc++.h> typedef long long ll; using namespace std; const int N = 1e4 + 50; const int M = 2e5 + 50; const int INF = 1e9; int n, m, S, T; int head[N], tot…

最大权闭合子图 定义：有一个有向图，每一个点都有一个权值（可以为正或负或 $0$），选择一个权值和最大的子图，使得每个点的后继都在子图里面，这个子图就叫最大权闭合子图。 解法： 这个问题可以转化为最小割问题，用网络流解决。 从源点 $S$ 向每个正权点连一条容量为权值的边，每个负权点向汇点 $T$ 连一条容量为权值的绝对值的边，有向图原来的边容量全…

二分图最大匹配 匈牙利算法 #include <bits/stdc++.h> using namespace std; const int N = 1005; int n, m, k; int tot, head[N]; struct Edge { int nex, to; }e[N * N]; void add(int a,int b…

二分图最大权完美匹配：KM算法 KM算法只适用于一定存在完美匹配的情形。 洛谷P6577 【模板】二分图最大权完美匹配 题目描述 给定一张二分图，左右部均有 $n$ 个点，共有 $m$ 条带权边，且保证有完美匹配。 求一种完美匹配的方案，使得最终匹配边的边权之和最大。 输入格式 第一行两个整数 $n,m$；第 $2\sim m+1$ 行，每行三个整…

问题 P3381 【模板】最小费用最大流 题目描述 给出一个网络图，以及其源点和汇点，每条边已知其最大流量和单位流量费用，求出其网络最大流和在最大流情况下的最小费用。 输入格式 第一行包含四个正整数 $N,M,S,T$，分别表示点的个数、有向边的个数、源点序号、汇点序号。 接下来 $M$ 行每行包含四个正整数 $u_i,v_i,w_i,f_i$，表…