知识清单

• 二分图
• 网络流

（我都不知道有什么用）

• 今天不能上网好气啊$qwq$

笔记

1. 二分：这个懒得说了，以前写过。

2. 二分图

   • 定义：一个图的结点可以分成两个集合，当且仅当它不会出现长度为奇数的环。
   • 算法：基于$dfs$即可，一般使用染色来判断是否成功（或符合题意）。

   • 例题：【洛谷】P1525 关押罪犯

     • 分析：二分枚举最大边的情况，失败了就让最大边大一点，成功了让最大边小一点再试试。然后二分图，如果一条边比现在枚举的最大边大，就一定要分开，即把相邻两个点染成不同的颜色。如果染色失败，则枚举的最大边情况失败，继续二分，如此反复。

     #include <iostream>
     #include <cstdio>
     #include <algorithm>
     #include <cstring>
     using namespace std;
     struct edge{
         int v,w,next;
     }Edge[100005];
     int n,m,col[20005],data[100005];
     int head[20005],cnt;
     int l,r,mid,Max;
     bool book[20005];
     inline void AddEdge(int u,int v,int w){//邻接链表存边
         cnt++;
         Edge[cnt].v=v;
         Edge[cnt].w=w;
         Edge[cnt].next=head[u];
         head[u]=cnt;
         return;
     }
     bool dfs(int u,int color){//基本上二分图染色都可以参照这个模板
         if (book[u]) return col[u]==color;
         book[u]=true;
         col[u]=color;
         bool flag=true;
         for (int i=head[u];i!=0&&flag;i=Edge[i].next){
             int v=Edge[i].v;
             if (Edge[i].w<=Max) continue;//如果比枚举的最大边Max小，可以不用管它，即把它暂时
             flag=dfs(v,1-color);//放在原来的联通块中
         }
         return flag;
     }
     inline bool Colored(){
         memset(book,false,sizeof (book));//不要忘了初始化
         memset(col,0,sizeof (col));
         Max=data[mid];
         for (int i=1;i<=n;i++){
             if (book[i]) continue;
             if (!dfs(i,0)) return false;
         }
         return true;
     }
     int main(){
         int u,v,w;
         scanf("%d%d",&n,&m);
         for (int i=1;i<=m;i++){
             scanf("%d%d%d",&u,&v,&w);
             data[i]=w;
             AddEdge(u,v,w);
             AddEdge(v,u,w);
         }
         sort (data+1,data+m+1);
         l=0;
         r=m;
         while (l<r){
             mid=(l+r)>>1;
             if (Colored()) r=mid;
             else l=mid+1;
         }
         printf ("%d\n",data[l]);
         return 0;
     }

   • 时间复杂度：$O(n+m)$，因为每个点都访问一次鸭~~

3. 二分图匹配（其实我没看懂）

   • 定义：在二分图边集上选一些边，是这些边两两不共顶点。总连接的点最多叫最大匹配，全部连接上就叫完美匹配（؏؏☝ᖗ乛◡乛ᖘ☝؏؏）。

   • 匈牙利算法：

     • 思想：

本文作者：Snowflake_Pink
本文链接：https://snowflake.pink/archives/26/
最后修改时间：2020-04-13 11:15:01
本站未注明转载的文章均为原创，并采用 CC BY-NC-SA 4.0 授权协议，转载请注明来源，谢谢！