网络流
Dinic算法
P3376 【模板】网络最大流
算法思想
1、先用bfs对图进行分层，如果图不连通则结束
2、用dfs寻找增广路，对于一个节点来说，只找比他深度多一的增广路，找到就返回流量，正向边加，反向边减。
3、使用当前弧优化
代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxm=1e5+5,INF=1e18,maxn=205;
int n,m,s,t,u,v,w;
struct node{
int v,nxt,to;
}edge[maxm];
int head[maxn];
int dep[maxn],whi[maxn];
queue<int>q;
int cnt=1;
void add_edge(int u,int v,int w){
cnt++;
edge[cnt].v=w;
edge[cnt].to=v;
edge[cnt].nxt=head[u];
head[u]=cnt;
return ;
}
int bfs(){
for(int i=1;i<=n;i++)dep[i]=-1;
while(!q.empty())q.pop();
dep[s]=1;
whi[s]=head[s];
q.push(s);
while(!q.empty()){
int now=q.front();q.pop();
for(int i=head[now];i;i=edge[i].nxt){
int next=edge[i].to;
if(edge[i].v>0&&dep[next]==-1){
q.push(next);
whi[next]=head[next];
dep[next]=dep[now]+1;
if(next==t)return 1;
}
}
}
return 0;
}
int dfs(int now,int flow){
if(now==t)return flow;
int ans=0;
for(int i=whi[now];i&&flow;i=edge[i].nxt){
int next=edge[i].to;
whi[now]=i;
if(edge[i].v>0&&dep[next]==dep[now]+1){
int now_flow=dfs(next,min(flow,edge[i].v));
if(!now_flow)dep[next]=-1;
edge[i].v-=now_flow;
edge[i^1].v+=now_flow;
ans+=now_flow;
flow-=now_flow;
}
}
return ans;
}
void dinic(){
int max_flow=0;
while(bfs())
max_flow+=dfs(s,INF);
cout<<max_flow<<endl;
return ;
}
signed main(){
scanf("%lld%lld%lld%lld",&n,&m,&s,&t);
for(int i=1;i<=m;i++){
scanf("%lld%lld%lld",&u,&v,&w);
add_edge(u,v,w);
add_edge(v,u,0);
}
dinic();
return 0;
}
二分图
二分图的判定
P1525 [NOIP2010 提高组] 关押罪犯
其实对于二分图判定的做法还是比较好想的，（因为我太蒻想不到并查集还要有边权）也易于实现
由于本题要求把罪犯划分到两个监狱中（我理解为划分到两个不同的集合中）那么我不禁想到图论的二分图
首先，抛来一个二分图的定义：
如果一张无向图的n个节点(n>=2)可以分为A,B两个集合，
且满足A ∩ B = ∅ ，而且在同一集合内的点之间都没有边相连，那么这张无向图被称为二分图，其中A和B分别叫做二分图的左部和右部
那么对于本题，我们就是要把所有人分为两个部分，其间不出现矛盾，显然很符合二分图的要求
别太高兴，问题来了：如何判定这个“矛盾图”是不是二分图
二分图判定定理：
一张无向图是二分图：
当且仅当图中不存在奇环（奇环是指长度为奇数的环）
既然有了判定定理，我们就可以使用染色法进行二分图判定
染色法基本实现如下：
1.大多数情况基于dfs（深度优先搜索）
2.我们尝试用黑和白两种颜色标记图中的点，当一个节点被标记了，那么所有与它相连的点应全部标记为相反的颜色
如果在标记过程中出现冲突，那么算法结束，证明本图中存在奇环，即本图不为二分图；反之，如果算法正常结束，那么证明本图是二分图
代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=2*1e4+5,maxm=1e5+5;
int mid,vis[maxn],n,m;
bool ans;
struct node{
int x,y,v;
}a[maxm];
struct edge{
int to,v;
};
vector<edge>d[maxn];
bool cmp(node x,node y){
return x.v>y.v;
}
bool check(int now,int c){
// cout<<now<<" "<<c<<endl;
vis[now]=c;
for(int i=0;i<d[now].size();i++){
if(d[now][i].v<a[mid].v)continue;
int Next=d[now][i].to;
if(vis[Next]==vis[now])return false;
if(!vis[Next]&&!check(Next,-c))return false;
}
return true;
}
bool solve(){
memset(vis,0,sizeof vis);
for(int i=1;i<=n;i++){
if(!vis[i]){
if(!check(i,1))return false;
}
}
return true;
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++){
cin>>a[i].x>>a[i].y>>a[i].v;
d[a[i].x].push_back({a[i].y,a[i].v});
d[a[i].y].push_back({a[i].x,a[i].v});
}
sort(a+1,a+m+1,cmp);
int l=0,r=m+1;
while(l+1<r){
ans=true;
mid=(l+r)/2;
if(solve())l=mid;
else r=mid;
}
cout<<a[l+1].v;
return 0;
}
二分图的最大匹配
P3386 【模板】二分图最大匹配
常用的二分图匹配算法是匈牙利算法，其正确性基于 hall 定理，本质是不断寻找增广路来扩大匹配数。但是其正确性证明比较复杂，在此略去。
匈牙利算法的过程是，枚举每一个左部点 u ，然后枚举该左部点连出的边，对于一个出点 v，如果它没有被先前的左部点匹配，那么直接将 u 匹配 v，否则尝试让 v 的“原配”左部点去匹配其他右部点，如果“原配”匹配到了其他点，那么将 u 匹配 v，否则 u 失配。
尝试让“原配”寻找其他匹配的过程可以递归进行。需要注意的是，在一轮递归中，每个右部点只能被访问一次。
算法的时间复杂度为$ O(n \times e + m)$，其中 n是左部点个数，e是图的边数，m是右部点个数。
不难发现其实交换左右部点后的最大匹配数是一样的，而对于 \(m < n\)，有 \(m \times e + n < n \times e + m\)。所以有一个小 trick 是当右部点的个数比左部点多的时候，交换左右部能有更高的效率。
实际上，在dfs里面，x表示的是左部点，i表示的是右部点，而match[i]记录的是右部点匹配的是哪一个左部点，vis记录右部点是否访问过，我们使用邻接矩阵存图
代码
#include<bits/stdc++.h>
using namespace std;
const int maxn=505;
int n,m,vis[maxn],match[maxn],d[maxn][maxn],e,x,y,ans;
int dfs(int x){
for(int i=1;i<=m;i++){
if(d[x][i]&&!vis[i]){
vis[i]=1;
if(!match[i]||dfs(match[i])){
match[i]=x;
return 1;
}
}
}
return 0;
}
int main(){
cin>>n>>m>>e;
for(int i=1;i<=e;i++){
cin>>x>>y;
d[x][y]=1;
}
for(int i=1;i<=n;i++){
memset(vis,0,sizeof vis);
ans+=dfs(i);
}
cout<<ans;
return 0;
}
二分图的其他性质
最大独立集：
独立集是指图 G 中两两互不相邻的顶点构成的集合。
最小点覆盖：
如果说一条边的任意一个顶点被选中那么这条边也被选中，简而言之就是我们希望用尽可能少的点去使所有的边都被选中
最大独立集点数加最大匹配数等于总点数：
在无向图中，总点数 = 最大独立集+最小点覆盖：
反证法证明： 用V表示点集，V1表示一个点覆盖集。
设V2=V-V1。假设V2不是独立集，那么V2中的存在两个点U,V有一条边，
因为点覆盖集要包含每条边的其中一个点，
那么V1不是点覆盖集，矛盾。
所以 ，点覆盖集和独立集是互补。
所以，总点数 = 最大独立集+最小点覆盖。
最大匹配边数等于最小点覆盖
由上显然