bryce1010-ACM-Template 图论

倍增及其应用 _ 未知作者

Apr 03 '20 14:04 Bryce1010

二分图与匹配黄哲威

Apr 03 '20 15:04 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

DFS序+数据结构

树链剖分

动态树

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

其他

总结

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

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

Apr 04 '20 02:04 Bryce1010

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

Apr 04 '20 03:04 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

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

[ ] 团伙

Apr 08 '20 11:04 Bryce1010

图论复习 _ 未知作者

图的存储形式:

邻接矩阵
邻接链表

传递闭包

最小生成树

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

最短路的算法

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

二分图匹配

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

Apr 09 '20 09:04 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;
}

图的链表存储


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

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

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

[ ] CF666B World Tour
[ ] CF545E Paths and Trees

Apr 09 '20 09:04 Bryce1010

图论知识及其应用

Apr 09 '20 09:04 Bryce1010

树分治_黄哲威

Apr 09 '20 09:04 Bryce1010

树链剖分_蒋一瑶

Apr 09 '20 09:04 Bryce1010

树上倍增_黄哲威

Apr 09 '20 09:04 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)

二分图

二分图匹配

最大匹配

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

最小点覆盖

Apr 09 '20 09:04 Bryce1010

图论知识及其应用

Apr 09 '20 09:04 Bryce1010

图论专题生成树_唐文斌

Apr 09 '20 09:04 Bryce1010

网络流_未知作者

Apr 09 '20 09:04 Bryce1010

网络流_魏越闽

Apr 09 '20 09:04 Bryce1010

网络流_周津浩&黄着威

Apr 09 '20 09:04 Bryce1010

网络流建模周尚彦

Apr 09 '20 09:04 Bryce1010

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

Apr 09 '20 09:04 Bryce1010

2-SAT问题_未知作者

Apr 09 '20 09:04 Bryce1010

bryce1010-ACM-Template bryce1010-ACM-Template copied to clipboard

图论

倍增及其应用 _ 未知作者

二分图与匹配 黄哲威

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

树的遍历

宽度优先

深度优先

树的存储

树问题的应用

树形动态规划

最近公共祖先

DFS序+数据结构

树链剖分

动态树

其他

总结

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

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

并查集

生成树

Kruskal

Prim 算法

拓扑排序

图论复习 _ 未知作者

传递闭包

最小生成树

最短路的算法

二分图匹配

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

最短路

图论知识及其应用

树分治_黄哲威

树链剖分_蒋一瑶

树上倍增_黄哲威

图论_李煜东

图的遍历

最短路问题

Floyd算法

Dijkstra 算法

Bellman-Ford算法

最小生成树

Kruskal

Prim

树上的倍增法

LCA

二分图

二分图匹配

最大匹配

最小点覆盖

图论知识及其应用

图论专题生成树_唐文斌

网络流_未知作者

网络流_魏越闽

网络流_周津浩&黄着威

网络流建模 周尚彦

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

2-SAT问题_未知作者

bryce1010-ACM-Template
bryce1010-ACM-Template copied to clipboard

二分图与匹配黄哲威

网络流建模周尚彦