2019.4.21高中部集训
浏览 1019 | 评论 0 | 字数 2219
Snowflake_Pink
2019年04月21日
  • 知识清单

    • 二分图
    • 网络流

    (我都不知道有什么用)


    • 今天不能上网好气啊$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 授权协议,转载请注明来源,谢谢!
    评论
    评论会由可爱的 AI 来审核鸭~
    textsms
    支持 Markdown 语法
    email
    link
    评论列表
    暂无评论