图论

[Bryce1010]

倍增及其应用 _ 未知作者

[Bryce1010]

二分图与匹配 黄哲威

[Bryce1010]

浅谈一些树形问题 -- 高胜寒

树的遍历

宽度优先

• 层次序遍历

  在bfs基础上, 添加一个list保存每层的结果

  vector<vector<int>> levelOrder(Node* root) {
  if(!root) return {};
  vector<vector<int>> ans;
  queue<Node*> que;
  que.push(root);
  while(!que.empty())
  {
  vector<int> v;
  for(int i=que.size();i;i--)
  {
  //压入当前层
  Node* curr=que.front();
  que.pop();
  v.push_back(curr->val);
  for(Node* it:curr->children)
  que.push(it);
  }
  ans.push_back(v);
  }
  return ans;
  }

深度优先

• 前序遍历
• 中序遍历

  
  class Solution {
  public:
  vector<int> ans;
  vector<int> inorderTraversal(TreeNode* root) {
      if(root != NULL) {
          inorderTraversal(root -> left);
          ans.push_back(root -> val);
          inorderTraversal(root -> right);
      }
      return ans;
  }
  };

- 后序遍历

### 树的存储
- 邻接表
- 有根树记录所有孩子
- 有根树记录父亲节点
- DFS 序

### 树问题的应用
#### 树形动态规划
- 将一棵树原问题转化为其子树上问题
- 为每一个子树计算其最优值
- 将最优值合并至有根树  

- [ ] SPOJ/MTREE

#### 最近公共祖先
5种写法
- 暴力算法
- 倍增算法
- dfs序算法
- targan算法
- 树链剖分算法
> 将一颗树剖成若干条链
> 每一个点到根都只经过log级别条链
> 对于每条链当做数列来做 

![image](https://user-images.githubusercontent.com/30361513/78781691-46234b80-79d3-11ea-89ac-683ffa2b0b9d.png)
- [ ] SPOJ/ QTREE2
- [ ] SPOJ OTOCI
- [ ] SPOJ COT
- [ ] SPOJ MINDIST  

#### DFS序+数据结构  

#### 树链剖分   

#### 动态树   
- 动态维护一种剖分
- 类别树链剖分
- 使用SPLAY维护动态树

#### 其他

### 总结
根据题意, 判断是哪一类树形问题, 具体问题具体分析
对于每一种类型的题目找出相应的解法

> 若需求路径上的问题, 优先考虑LCA法, 其次考虑dfs序, 最后树链剖分;
> 首选找出树与图所不同的地方, 将题目转化为一些其他模型的问题;

[Bryce1010]

浅析二分图匹配在信息学竞赛中的应用_王俊

[Bryce1010]

生成树和拓扑排序_黄哲威

并查集

int fa[maxn];
int getroot(int x){
    return x==fa[x]?x:getroot(fa(x));
}

void merge(int x,int y){
    int p=getroot(x),q=getroot(y);
    fa[p]=q;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;++i)
        fa[i]=i;
    return 0;
}

并查集优化- 路径压缩

int fa[maxn];
int getroot(int x){
    return x==fa[x]?x:fa[x]=getroot(fa(x));
}

void merge(int x,int y){
    int p=getroot(x),q=getroot(y);
    fa[p]=q;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;++i)
        fa[i]=i;
    return 0;
}

并查集优化- 按秩合并

深度更小的树指向深度更大的树

int fa[maxn],h[maxn]; int getroot(int x){ return x==fa[x]?x:getroot(fa(x)); }

void merge(int x,int y){ int p=getroot(x),q=getroot(y); if(h[p]>h[q])swap(p,q); fa[p]=q;h[q]++; } int main(){ cin>>n; for(int i=1;i<=n;++i) fa[i]=i; return 0; }

### 生成树  

#### Kruskal
```cpp
int n,m,ans;
struce edge{
    u,v,w;
}e[M];

bool cmp(edge a, edge b){
    return a.w<b.w;
}

int main(){
    cin>>n>>m;
    for(int i=1;i<=m;++i){
        cin>>e[i].u>>e[i].v>>e[i].w;
    }
    sort(e+1,e+m+1,cmp);
    for(int i=1;i<=m;++i){
        int p=getroot(e[i].u),q=getroot(e[i].v]);
        if(p!=q){
            fa[p]=q;
            ans+=e[i].w;
        }
    }
    return 0;
}

Prim 算法

拓扑排序

int top,q[N];

int main(){
    cin>>n>>m;
    for(int i=1;i<=m;++i){
        int u,v;
        cin>>u>>v;
        e[u].push_back(v);
        d[v]++;
    }
    for(int i=1;i<=n;++i)
        if(!d[i])
            q[++top]=i;
    while(top){
        int u=q[top];top--;
        for(int i=0;i<e[u].size();++i){
            int v=e[u][i];
            d[v]--;
            if(!d[v])
                q[++top]=v;
        }
    }    
    return 0;
}

• [ ] 团伙

[Bryce1010]

图论复习 _ 未知作者

图的存储形式:

• 邻接矩阵
• 邻接链表

传递闭包

最小生成树

• Kruskal 算法
  适用于稀疏图

• Prim算法
  适用于稠密图

  最短路的算法

• Floyd算法 非负有向图

• Dijkstra算法 非负 有向图

• Bellman-Ford算法/ SPFA算法 实数, 不存在负环回路

二分图匹配

• 二分图的最大匹配 (匈牙利算法)
• 图的最小覆盖问题

[Bryce1010]

图论入门与最短路 _ 黄哲威

#include<bits/stdc++.h>
using namespace std;
#define pa pair<int,int>
vector<pa>v;
int main(){
    for(int i=1;i<=10;++i)
        v.push_back(make_pair(rand(),i));
    sort(v.begin(),v.end());
    for(int i=0;i<v.size();++i)
        cout<<v[i].first<<' '<<v[i].second<<endl;
    return 0;
}

#include<bits/stdc++.h>
using namespace std;

priority_queue<int,vector<int>,greater<int> >q; //小根堆  
int main(){
    for(int i=1;i<=10;++i)
        q.push(rand());
    for(int i=1;i<=10;++i){
        cout<<q.top()<<endl;
        q.pop();
    }
    return 0;
}

• 图的链表存储

vectore[N];

int main(){ cin>>n>>m; for(int i=1;i<=m;++i){ int u,v; cin>>u>>v; e[u].push_back(v); e[v].push_back(u); } return 0; }

- 图的bfs遍历
```python
void bfs(int x){
    int head=0,tail=1;
    q[0]=x;vis[x]=1;
    while(head!=tail){
        int u=q[head];head++;
        for(int i=0;i<E[u].size();++i){
            int v=e[u][i];
            if(!vis[v]){
                vis[v]=1;
                dis[v]=dis[u]+1;
                q[tail++]=v;
            }
        }
    }
}

• 图的dfs

void dfs(int x){ vis[x]=1; for(int i=0;i<e[x].size();++i){ if(!vis[x][i]) dfs(e[x][i]); } }

### 最短路  
- Floyd算法 
F[k, i, j] 表示经过k个点, i到j的最短路;   
F[k, i ,j] = F[k-1, i, k] + F[k-1, k , j]  
通过省略一维空间: 
F[i,j] = F[i, k] + F[k , j]
```python
void floyd(){
    for(int k=1;k<=n;++k){
        for(int i=1;i<=n;++i){
            for(int j=1;j<=n;++j){
                dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
            }
        }
    }
}

• SPFA

  const int MAXN=1010;
  const int INF=0x3f3f3f3f;
  struct Edge{
  int v;
  int cost;
  Edge(int _v,int _cost):v(_v),cost(_cost){}
  };
  vector<Edge>E[MAXN];
  void addedge(int u,int v,int w){
  E[u].push_back(E(v,w));
  }
  bool vis[MAXN];//判断在队列标注
  int cnt[MAXN];//判断每个点入队列次数，以判断是否存在负环回路
  int dist[MAXN];
  bool SPFA(int start, int n){
  memset(vis,false,sizeof(vis));
  for(int i=1;i<=n;++i)dist[i]=INF;
  queue<int>que;
  while(!que.empty())que.pop();
  que.push(start);
  vis[start]=true;
  dist[start]=0;
  memset(cnt,0,sizeof(cnt));
  cnt[start]=1;
  while(!que.empty){
      int u=que.front();
      que.pop();
      if(vis[u])continue;
      vis[u]=false;
      for(int i=0;i<E[u].size();++i){
          int v=E[u][i].v;
          if(dist[u]+E[u][i].cost<dist[v]){
              dist[v]=dist[u]+E[u][i].cost;
              if(!vis[v]){
                  vis[v]=true;
                  que.push(v);
                  if(++cnt[v]>n)return false;
              }
          }
      }
  }
  return true;
  }

• Dijkstra

  const int INF=0x3f3f3f3f;
  const int MAXN=100010;
  struct qnode{
  int v;
  int c;
  qnode(int _v=0,int _c=0):v(_v),c(_c){}
  bool operator < (const qnode& r)const{
      return c>r.c;
  }
  };
  struct Edge{
  int v,cost;
  Edge(int _v=0,int _cost=0):v(_v),cost(_cost){}
  };
  vector<Edge>E[MAXN];
  bool vis[MAXN];
  int dist[MAXN];
  //点的编号从1开始
  void Dijkstra(int n,int start){
  memset(vis,false,sizeof(vis));
  for(int i=1;i<=n;++i)dis[i]=INF;
  priority_queue<qnode>que;
  while(!que.empty())que.pop();
  dis[start]=0;
  que.push(qnode(start,0));
  qnode tmp;
  while(!que.empty()){
      tmp=que.top();
      que.pop();
      int u=tmp.v;
      if(vis[u])continue;
      vis[u]=true;
      for(int i=0;i<E[u].size();++i){
          int v=E[tmp.v][i].v;
          int cost=E[u][i].cost;
          if(!vis[v]&&dist[u]+cost<dist[v]){
              dist[v[=dist[u]+cost;
              que.push(qnode(v,dist[v]));
          }
      }
  }
  }
  void addedge(int u,int v,int w){
  E[u].push_back(Edge(v,w));
  }

• [x] CF475B 图的遍历

• [ ] CF295B

• [ ] CF1214D

• [ ] NOIP 2009 最优贸易

  n个点, m条边的有向图, 有些边是单向边, 有些边是双向边, 每个点有物品的买入和卖出价格. 现在从1号点走到n号点, 途中只能买一次物品,并在这之后卖出, 问最多能赚多少钱?  

• [ ] CF666B World Tour

• [ ] CF545E Paths and Trees

[Bryce1010]

图论知识及其应用

[Bryce1010]

树分治_黄哲威

[Bryce1010]

树链剖分_蒋一瑶

[Bryce1010]

树上倍增_黄哲威

[Bryce1010]

图论_李煜东

图的遍历

• 深度优先遍历

  访问标记避免重复,时间戳

  const int maxn=1000;
  //采用链式前向星存储图
  bool vis[maxn]={0};
  void dfs(int s){
  vis[s]=true;
  //遍历当前点的所有邻接点
  for(int i=head[s];i!=-1;i=edge[i].next){
  dfs(edge[i].to);
  }
  }

• 广度优先遍历

  循环队列, 优先队列
  边权为01的图上双端队列

  void bfs(int s){
  int que[maxn];
  int iq=0;
  que[id++]=s;
  int i,k;
  //循环至队列元素为空
  for(i=0;i<iq;++i){
  vis[que[i]]=ture;
  for(k=head[que[i]];k!=-1;k=edge[k].next){
  if(!vis[edge[k].to])
  que[iq++]=edge[k].to;
  }
  }
  }

• 拓扑排序

  1）从有向图中选择一个入度为0的顶点并输出。 2）从网中删除该顶点，及其发出的全部边。 3）重复1）和2），直到所有的点都被输出。

  //输入数据时统计每个点的入度，并存入indegree数组。
  int queue[maxn];
  int iq=0;
  for(int i=1;i<=n;i++)
  {
  if(indegree[i]==0)
  {
  queue[iq++]=i;
  }
  }
  for(int i=0;i<iq;i++)
  {
  for(k=head[queue[i]];k!=-1;k=edge[k].next)
  {
  indegree[edge[k].to]--;
  if(indegree[edge[k].to]==0)
  {
  queue[iq++]=edge[k].to;
  }
  }
  }

最短路问题

• [ ] POJ 3613
• [ ] POJ1734

Floyd算法

可以经过标号<=k的点中转时, 从i到j的最短路
F[k,i,j]=min{ F[k-1,i,k]+F[k-1,k,j]} F[i,j]=min{F[k-1,i,k]+F[k-1,k,j]| O(n^3) k->i->j

Dijkstra 算法

普通: O(n^2)
堆优化: O(NlogN)~O(MlogN)

Bellman-Ford算法

BF算法: O(N^2) SPFA算法: 队列优化的BF算法; 稀疏图上O(kN), 稠密图上O(N^2) 可以应用于负权图

• [ ] POJ 3463
• [ ] POJ 3635
• [ ] POJ 2449 第K短路

最小生成树

Kruskal

O(MlogN) 利用并查集, 起初每个点构成一个集合 所有边按照边权从小到大排序, 一次扫描 如果当前扫描得到边连接连个不同的集合, 合并

Prim

O(N^2) 以任一点为基准点, 将节点分为两组:

• 在MST上到基准点的路径已经确定的点

• 尚未在MST中与基准点相连的点
  不断从第2组中选择与第一组距离最近的点加入第1组

• [ ] POJ 1639

• [ ] BZOJ 1977 次小生成树

树上的倍增法

LCA

• 倍增法
  静态, 在线, O(NlogN)-O(logN)

• ST维护欧拉序
  静态, 在线, O(NlgN)-O(1)

• Targan算法 静态, 离线, O(N+M+Q)

• Link-cut Tree (动态树)
  动态, 在线, O(N)- O(logN)

二分图

二分图匹配

最大匹配

增广路算法(匈牙利算法)

最小点覆盖

[Bryce1010]

图论知识及其应用

[Bryce1010]

图论专题生成树_唐文斌

[Bryce1010]

网络流_未知作者

[Bryce1010]

网络流_魏越闽

[Bryce1010]

网络流_周津浩&黄着威

[Bryce1010]

网络流建模 周尚彦

[Bryce1010]

线性规划与网络流_曹钦翔

[Bryce1010]

2-SAT问题_未知作者