2019.4.21高中部集训

知识清单

  • 二分图
  • 网络流

(我都不知道有什么用)


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

笔记

  1. 二分图

    • 定义:一个图的结点可以分成两个集合,当且仅当它不会出现长度为奇数的环。

    • 算法:基于$dfs$即可,一般使用染色来判断是否成功(或符合题意)。

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

      • 分析:二分枚举最大边的情况,失败了就让最大边大一点,成功了让最大边小一点再试试。然后二分图,如果一条边比现在枚举的最大边大,就一定要分开,即把相邻两个点染成不同的颜色。如果染色失败,则枚举的最大边情况失败,继续二分,如此反复。
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      33
      34
      35
      36
      37
      38
      39
      40
      41
      42
      43
      44
      45
      46
      47
      48
      49
      50
      51
      52
      53
      54
      55
      56
      57
      58
      59
      60
      61
      62
      #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;
      }
Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×