为什么没人用 vector

AC_love @ 2023-09-26 20:15:32

by _zzzzzzy_ @ 2023-09-26 20:33:48

@AC_love 差不多吧，我平时用vector，网络流用链式前向星，用的很混乱

by DELA @ 2023-09-26 20:35:14

为啥不能当前弧？

by DELA @ 2023-09-26 20:35:38

不同的存图方式有啥区别吗

by SnowTrace @ 2023-09-26 20:36:01

@AC_love

我写的Dinic存图方式比较奇怪，我觉得可以叫vector式前向星（我当时学网络流的时候也习惯用vector，然后就搞出了一个比较奇怪的写法

#include<bits/stdc++.h>
using namespace std;
const int inf = 2000000005;
vector<int>p[200005];
struct edge{
    int fl,to;
}e[200005];
int n,m,s,t,head = 1;
int cur[200005],dis[200005];
void add(int a,int b,int c){
    e[++head].to = b,e[head].fl = c;
    p[a].push_back(head);
    e[++head].to = a,e[head].fl = 0;
    p[b].push_back(head);return;
}
bool bfs(){
    memset(cur,0,sizeof(cur));
    memset(dis,63,sizeof(dis));
    queue<int>q;
    q.push(s);dis[s] = 0;
    //cout << s << endl;
    while(!q.empty()){
        int now = q.front();q.pop();
        //cout << now << endl;
        for(int i =0;i<p[now].size();i++){
            int to = e[p[now][i]].to,fl = e[p[now][i]].fl;
        //  cout << " " << to << endl;
            if(!fl)continue;
            if(dis[now]+1<dis[to]){
                dis[to] = dis[now]+1;
                q.push(to);
            }
        }
    }return (dis[t]<=2*n);
}int dfs(int now,int f){
    if(now == t or !f)return f;
    int res = 0;
    for(int i = cur[now];i<p[now].size();i++){
        cur[now] = i;
        int to = e[p[now][i]].to,fl = e[p[now][i]].fl,nw = 0;
        if(!fl or dis[now]+1!=dis[to])continue;
        if(nw = dfs(to,min(f,fl))){
            res+=nw,f-=nw;
            e[p[now][i]].fl-=nw,e[p[now][i]^1].fl+=nw;
            if(!f)break;
        }
    }return res;
}int Dinic(){
    int ans = 0;
    while(bfs()){
    //  cout << 1 << endl;
        ans+=dfs(s,inf);
    }return ans;
}
signed main(){
    cin >> n >> m >> s >> t;
    for(int i = 1;i<=m;i++){
        int a,b,c;cin >>a >> b >> c;
        add(a,b,c);
    }cout << Dinic() << endl;

    return 0;
}

by james1BadCreeper @ 2023-09-26 20:36:33

vector<edge> edges; 
vector<int> G[maxn]; 

void addedge(int u, int v, int w) {
    edegs.emplace_back(u, v, w); 
    G[u].emplace_back(edges.size() - 1); 
}

这样的话就直接用 edges[G[u][i] ^ 1] 来取反向边就行了。

by AC_love @ 2023-09-26 20:36:37

@liangbowen 但是网上确实几乎没有用 vector 做网络流题目的，这也给很多用 vector 更熟练的人带来了一些局限性，我觉得这个东西应该有讲解的必要

by AC_love @ 2023-09-26 20:37:26

@james1BadCreeper 谔谔，波神伟大，无需多言！

by AC_love @ 2023-09-26 20:38:51

@Phantom2009 好强，但是我看到链前就发晕，感觉每次用链前的时候都要反应一会儿才能想起来这玩意的底层逻辑才能写得出来代码，跟我用 vector 时候的熟练度差太多了

by SnowTrace @ 2023-09-26 20:39:50

@AC_love 但你看到我本质上是遍历一个vector，其实就是往vector里面塞个下标，然后再用这个下标访问一些其他的信息

by liangbowen @ 2023-09-26 20:42:08

你真正理解网络流在干什么的话，处理反向边不是轻而易举的事情吗 /yiw