图论 #1

Bryce1010 · 2020-04-03T14:53:21Z

倍增及其应用 _ 未知作者

Bryce1010 · 2020-04-03T15:15:54Z

二分图与匹配黄哲威

Bryce1010 · 2020-04-04T02:53:49Z

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

树的遍历

宽度优先

层次序遍历

在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

DFS序+数据结构

树链剖分

动态树

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

其他

总结

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

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

Bryce1010 · 2020-04-04T03:14:22Z

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

Bryce1010 · 2020-04-08T11:36:54Z

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

并查集

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

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 · 2020-04-09T09:13:41Z

图论复习 _ 未知作者

图的存储形式:

邻接矩阵
邻接链表

传递闭包

最小生成树

Kruskal 算法
适用于稀疏图
Prim算法
适用于稠密图

最短路的算法

Floyd算法非负有向图
Dijkstra算法非负有向图
Bellman-Ford算法/ SPFA算法实数, 不存在负环回路

二分图匹配

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

Bryce1010 · 2020-04-09T09:19:32Z

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

#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;
}

图的链表存储

vector<int>e[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遍历

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]

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));
}

CF475B 图的遍历
CF295B
CF1214D
NOIP 2009 最优贸易

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

CF666B World Tour
CF545E Paths and Trees

Bryce1010 · 2020-04-09T09:20:12Z

图论知识及其应用

Bryce1010 · 2020-04-09T09:20:45Z

树分治_黄哲威

Bryce1010 · 2020-04-09T09:21:07Z

树链剖分_蒋一瑶

Bryce1010 · 2020-04-09T09:21:24Z

树上倍增_黄哲威

Bryce1010 · 2020-04-09T09:21:44Z

图论_李煜东

图的遍历

深度优先遍历

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

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 · 2020-04-09T09:22:31Z

图论知识及其应用

Bryce1010 · 2020-04-09T09:22:54Z

图论专题生成树_唐文斌

Bryce1010 · 2020-04-09T09:23:09Z

网络流_未知作者

Bryce1010 · 2020-04-09T09:23:29Z

网络流_魏越闽

Bryce1010 · 2020-04-09T09:23:57Z

网络流_周津浩&黄着威

Bryce1010 · 2020-04-09T09:24:23Z

网络流建模周尚彦

Bryce1010 · 2020-04-09T09:24:42Z

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

Bryce1010 · 2020-04-09T09:25:19Z

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

图论 #1

图论 #1

Bryce1010 commented Apr 3, 2020 •

edited

Loading

Bryce1010 commented Apr 3, 2020 •

edited

Loading

Bryce1010 commented Apr 4, 2020 •

edited

Loading

Bryce1010 commented Apr 4, 2020 •

edited

Loading

Bryce1010 commented Apr 8, 2020 •

edited

Loading

Bryce1010 commented Apr 9, 2020 •

edited

Loading

Bryce1010 commented Apr 9, 2020 •

edited

Loading

Bryce1010 commented Apr 9, 2020

Bryce1010 commented Apr 9, 2020

Bryce1010 commented Apr 9, 2020

Bryce1010 commented Apr 9, 2020

Bryce1010 commented Apr 9, 2020 •

edited

Loading

Bryce1010 commented Apr 9, 2020

Bryce1010 commented Apr 9, 2020

Bryce1010 commented Apr 9, 2020

Bryce1010 commented Apr 9, 2020

Bryce1010 commented Apr 9, 2020

Bryce1010 commented Apr 9, 2020

Bryce1010 commented Apr 9, 2020 •

edited

Loading

Bryce1010 commented Apr 9, 2020

图论 #1

图论 #1

Comments

Bryce1010 commented Apr 3, 2020 • edited Loading

倍增及其应用 _ 未知作者

Bryce1010 commented Apr 3, 2020 • edited Loading

二分图与匹配 黄哲威

Bryce1010 commented Apr 4, 2020 • edited Loading

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

树的遍历

宽度优先

深度优先

树的存储

树问题的应用

树形动态规划

最近公共祖先

DFS序+数据结构

树链剖分

动态树

其他

总结

Bryce1010 commented Apr 4, 2020 • edited Loading

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

Bryce1010 commented Apr 8, 2020 • edited Loading

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

并查集

生成树

Kruskal

Prim 算法

拓扑排序

Bryce1010 commented Apr 9, 2020 • edited Loading

图论复习 _ 未知作者

传递闭包

最小生成树

最短路的算法

二分图匹配

Bryce1010 commented Apr 9, 2020 • edited Loading

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

最短路

Bryce1010 commented Apr 9, 2020

图论知识及其应用

Bryce1010 commented Apr 9, 2020

树分治_黄哲威

Bryce1010 commented Apr 9, 2020

树链剖分_蒋一瑶

Bryce1010 commented Apr 9, 2020

树上倍增_黄哲威

Bryce1010 commented Apr 9, 2020 • edited Loading

图论_李煜东

图的遍历

最短路问题

Floyd算法

Dijkstra 算法

Bellman-Ford算法

最小生成树

Kruskal

Prim

树上的倍增法

LCA

二分图

二分图匹配

最大匹配

最小点覆盖

Bryce1010 commented Apr 9, 2020

图论知识及其应用

Bryce1010 commented Apr 9, 2020

图论专题生成树_唐文斌

Bryce1010 commented Apr 9, 2020

网络流_未知作者

Bryce1010 commented Apr 9, 2020

网络流_魏越闽

Bryce1010 commented Apr 9, 2020

网络流_周津浩&黄着威

Bryce1010 commented Apr 9, 2020

网络流建模 周尚彦

Bryce1010 commented Apr 9, 2020 • edited Loading

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

Bryce1010 commented Apr 9, 2020

2-SAT问题_未知作者

Bryce1010 commented Apr 3, 2020 •

edited

Loading

Bryce1010 commented Apr 3, 2020 •

edited

Loading

二分图与匹配黄哲威

Bryce1010 commented Apr 4, 2020 •

edited

Loading

Bryce1010 commented Apr 4, 2020 •

edited

Loading

Bryce1010 commented Apr 8, 2020 •

edited

Loading

Bryce1010 commented Apr 9, 2020 •

edited

Loading

Bryce1010 commented Apr 9, 2020 •

edited

Loading

Bryce1010 commented Apr 9, 2020 •

edited

Loading

网络流建模周尚彦

Bryce1010 commented Apr 9, 2020 •

edited

Loading