首页 > 其他分享 >图论板子

图论板子

时间:2024-09-07 11:51:54浏览次数:9  
标签:图论 int ++ st vis push 板子 size

Prim

typedef pair <int, int> P;
int prim() {
    int ans = 0, cnt = 0;
    priority_queue <P, vector<P>, greater<P> > q;
    fill(d + 1, d + n + 1, INF);
    d[1] = 0;
    q.push(P(d[1], 1));
    while(!q.empty() && cnt < n) {
        int y = q.top().second;
        q.pop();
        if(vis[y]) continue;
        vis[y] = 1;
        cnt++;
        ans += d[y];
        for(int i = 0; i < v[y].size(); i++) {
            int t = v[y][i].t, w = v[y][i].w;
            if(w < d[t]) {
                d[t] = w;
                q.push(P(d[t], t));
            }
        }
    }
    if(cnt < n) ans = -1;
    return ans;
}

tarjan(缩点)

int dfn[M], low[M], z;
int col[M], c;
int st[M], it;
bool vis[M];
void tarjan(int i) {
    z++;
    dfn[i] = low[i] = z;
    it++;
    st[it] = i;
    vis[i] = 1;
    for(int j = 0; j < v[i].size(); j++) {
        int t = v[i][j];
        if(!dfn[t]) {
            tarjan(t);
            low[i] = min(low[i], low[t]);
        } else if(vis[t]) {
            low[i] = min(low[i], dfn[t]);
        }
    }
    if(low[i] == dfn[i]) {
        c++;
        while(st[it] != i) {
            col[st[it]] = cc;
            vis[st[it]] = 0;
            it--;
        }
        col[i] = c;
        vis[i] = 0;
        it--;
    }
}

Dinic

void add(int f, int t, int w) {
    v[f].push_back({t, w, (int)v[t].size()});
    v[t].push_back({f, 0, (int)v[f].size() - 1});
}
void bfs() {
    for(int i = st; i <= ed; i++) l[i] = -1;
    queue <int> q;
    l[st] = 0;
    q.push(st);
    while(!q.empty()) {
        int x = q.front();
        q.pop();
        for(int i = 0; i < v[x].size(); i++) {
            int t = v[x][i].t, w = v[x][i].w;
            if(w > 0 && l[t] < 0) {
                l[t] = l[x] + 1;
                q.push(t);
            }
        }
    }
}
int dinic(int i, int fl) {
    if(i == ed) return fl;
    for(; it[i] < v[i].size(); it[i]++) {
        int t = v[i][it[i]].t, w = v[i][it[i]].w, r = v[i][it[i]].r;
        if(w > 0 && l[t] > l[i]) {
            int d = dinic(t, min(fl, w));
            if(d > 0) {
                v[i][it[i]].w -= d;
                v[t][r].w += d;
                return d;
            }
        }
    }
    return 0;
}
int main() {
    //...
    int flow = 0;
    for(;;) {
        bfs();
        if(l[ed] < 0) break;
        for(int i = st; i <= ed; i++) {
            it[i] = 0;
        }
        for(;;) {
            int f = dinic(st, MAX);
            if(f <= 0) break;
            flow += f;
        }
    }
    return 0;
}

min_cost_flow (Primal-Dual)

void add(int f, int t, int w, int c) {
    v[f].push_back({t, w, c, (int)v[t].size()});
    v[t].push_back({f, 0, -c, (int)v[f].size() - 1});
}
int h[N], d[N], pre[N], id[N];
bool vis[N];
void spfa() {
    queue<int> q;
    fill(h, h + ed + 1, INF);
    h[st] = 0, vis[st] = 1;
    q.push(st);
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        vis[x] = 0;
        for(int i = 0; i < v[x].size(); i++) {
            int t = v[x][i].t, w = v[x][i].w, c = v[x][i].c;
            if(w > 0 && h[t] > h[x] + c) {
                h[t] = h[x] + c;
                if(!vis[t]) {
                    vis[t] = 1;
                    q.push(t);
                }
            }
        }
    }
}
void dijkstra() {
    fill(d + 1, d + ed + 1, INF);
    d[st] = 0;
    priority_queue <P, vector<P>, greater<P> > q;
    q.push(P(d[st], st));
    while(!q.empty()) {
        int x = q.top().first, y = q.top().second;
        q.pop();
        if(d[y] < x) continue;
        for(int i = 0; i < v[y].size(); i++) {
            int t = v[y][i].t, w = v[y][i].w, c = v[y][i].c;
            if(w > 0 && d[t] > d[y] + c + h[y] - h[t]) {
                d[t] = d[y] + c + h[y] - h[t];
                pre[t] = y;
                id[t] = i;
                q.push(P(d[t], t));
            }
        }
    }
}
int ans, flow;
void mcf() {
    while(flow > 0) {
        dijkstra();
        for(int i = st; i <= ed; i++) {
            h[i] += d[i];
        }
        int f = flow;
        for(int i = ed; i != st; i = pre[i]) {
            f = min(f, v[pre[i]][id[i]].w);
        }
        flow -= f;
        ans += f * h[ed];
        for(int i = ed; i != st; i = pre[i]) {
            edge &e = v[pre[i]][id[i]];
            e.w -= f;
            v[i][e.r].w += f;
        }
    }
    // 最小费用最大流:d[i] == INF返回
}

标签:图论,int,++,st,vis,push,板子,size
From: https://www.cnblogs.com/meowqwq/p/18401486

相关文章

  • 代码随想录day 53 || 图论4
    字符串接龙varqueue*list.ListvarvisitMapmap[string]boolfuncmain(){ varcountint fmt.Scanf("%d",&count) varstartStr,endStrstring fmt.Scanf("%s%s",&startStr,&endStr) varstrList=make([]string,count) fo......
  • 第十二章 图论 Part3
    目录任务Kama101.孤岛的总面积思路Kama102.沉没孤岛思路Kama103.水流问题思路Kama104.建造最大岛屿思路心得任务Kama101.孤岛的总面积给定一个由1(陆地)和0(水)组成的矩阵,岛屿指的是由水平或垂直方向上相邻的陆地单元格组成的区域,且完全被水域单元格包围。孤岛是那些位于矩......
  • 代码随想录day52 || 图论3
    岛屿最大的孤岛面积packagemainimport"fmt"vardirPath=[4][2]int{{0,-1},{1,0},{0,1},{-1,0}}varvisited[][]boolvarflagboolvarresintfuncmain(){ varx,yint fmt.Scanf("%d%d",&x,&y) //x行y列初始化临界矩阵 vargra......
  • 第十一章 图论 Part2
    目录任务200.岛屿数量思路695.岛屿的最大面积思路任务200.岛屿数量给你一个由'1'(陆地)和'0'(水)组成的的二维网格,请你计算网格中岛屿的数量。岛屿总是被水包围,并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。此外,你可以假设该网格的四条边均被水包围。思......
  • 代码随想录day52 || 图论搜索 岛屿数量,岛屿的最大面积
    图遍历dfs深度优先搜索bfs广度优先搜索200岛屿数量(dfs)vardirPath=[][]int{{0,-1},{1,0},{0,1},{-1,0}}//上,右,下,左varvisited[][]boolfuncnumIslands(grid[][]byte)int{ //dfs深度优先遍历,对于每一个节点,按照上下左右四个固定顺序遍历,然后到下......
  • 搜索与图论
    这部分内容要用到树的数据结构,我们有以下几种方式来存储节点邻接表邻接表就是用类似链表的结构来存储数据,先创建一个数组h,每一个位置都有一个表头。然后e数组和ne数组分别表示节点的值是多少,节点的下一个节点的编号是多少,这种方式一般用在稠密图中,也就是节点数跟边数相差很大。......
  • 图论连通性相关
    并查集普通并查集:路径压缩写法:structUnion_Find_Set{ intf[N]; inlinevoidinit(){ for(inti=1;i<=n;++i) f[i]=i; } inlineintfind(intx){ if(x!=f[x])f[x]=find(f[x]); returnf[x]; } inlinevoidmerge(inta,intb){ intx......
  • 代码随想录训练营 Day50打卡 图论part01 理论基础 98. 所有可达路径
    代码随想录训练营Day50打卡图论part01一、理论基础DFS(深度优先搜索)和BFS(广度优先搜索)在图搜索中的核心区别主要体现在搜索策略上:1、搜索方向:DFS:深度优先,一条路走到黑。DFS从起点开始,选择一个方向深入到底,遇到死胡同再回溯,换一个方向继续探索。这种方式适合解决路径......
  • [Python图论]在用图nx.shortest_path求解最短路径时,节点之间有多条边edge,会如何处理?
    问:在使用图求最短路径时,如果节点之间有多条路径,shortest_route=nx.shortest_path(G,source=start_node,target=end_node,weight='length')会如何处理,会自动选择最短那条吗?#输出图G各节点之间有多少条边edge,并给出其长度Edgesbetween103928and25508583:共2条Edge......
  • 第十一章 图论 Part1
    任务797.所有可能的路径给你一个有n个节点的有向无环图(DAG),请你找出所有从节点0到节点n-1的路径并输出(不要求按特定顺序)graph[i]是一个从节点i可以访问的所有节点的列表(即从节点i到节点graph[i][j]存在一条有向边)。思路题目所给的图的表示是邻接表,题意就是找到......