网络流(最大流)&STL技巧

1.网络流(最大流) 重点

网络流概念

类似水流问题.

用途

最大流,最小割,费用流算法。

最大流算法

模拟过程,单单模拟的缺陷,还有EK算法的实现过程。

EK算法

复杂度:$O(VE^2)$.

核心:

找增广路,然后再更新网络图,然后同时可以反悔。

代码实现:

$bfs$找增广路然后再使用EK的精髓过程.

#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
#define maxn 1000039
int nex[maxn],to[maxn],s[maxn],last[maxn],top = 1;
void add(int u,int v,int w){
    nex[++top] = last[u];
    to[top] = v;
    s[top] = w;
    last[u] = top;
}
int v[maxn];
struct Edges{
    int las,edge;
}p[maxn];
bool bfs(int S,int T){
    memset(v,0,sizeof(v));
    memset(p,-1,sizeof(p));
    queue<int>q;
    v[S] = 1;
    q.push(S);
    while(!q.empty()){
        int now = q.front();
        for(int i=last[now];i;i=nex[i]){
            int To = to[i];
            if(v[To]||s[i] <= 0)continue;
            p[To].las = now;
            p[To].edge = i;
            if(To == T)return 1;
            q.push(To);
            v[To] = 1;
        }
        q.pop();
    }
    return 0;
}
int EK(int S,int T){
    long long ans = 0;
    while(bfs(S,T)){
        int minn = 0x7fffffff;
        for(int i=T;i!=S;i=p[i].las){
            minn = min(minn,s[p[i].edge]); 
        }
        ans += minn;
        for(int i=T;i!=S;i=p[i].las){
            s[p[i].edge] -= minn;
            s[p[i].edge ^ 1] += minn;
        }
    }
    return ans;
}
int main(){
    int n,m,s,t;
    scanf(%d%d%d%d,&n,&m,&s,&t);
    for(int i=1;i<=m;i++){
        int u,v,w;
        scanf(%d%d%d,&u,&v,&w);
        add(u,v,w);
        add(v,u,0);//建反向边. 
    }
    printf(%lld,EK(s,t));
    return 0;
}

要注意建立反向边!

应用拓展

最小费用流。 最小割。 $Dinic$算法求最大流.

2.STL技巧 没有太大用处的东西

STL 优化技巧

添加$unordered$会更快一些。 比如某些题目2333.

例题:

寻找连续最长数列。

题目描述

给定一个整数数列,寻找数列中最长连续的长度 如100 22 44 200 33 11 则其中能到的的最长连续序列为1 2 3 4

输入格式:

第一行为n 接下来第二行为n个数字

输出格式:

最长连续长度

样例输入:

6
100 2 4 200 3 1

样例输出:

4

数据范围:

n $\leq$ 1000000,每个数字为$int$以内整数.

代码:
#include<cstdio>
#include<vector>
#include<tr1/unordered_set>
using namespace std;
using namespace tr1;
vector<int>num;
int main(){
    int n;
    scanf(%d,&n);
    for(register int i=0;i<n;i++){
        int tmp;
        scanf(%d,&tmp);
        num.push_back(tmp);
    }
    unordered_set<int> t1(num.begin(),num.end());
    register int ans = 0;
    for(register int i=0;i<n;i++){
        if(t1.count(num[i]-1)==0){
            int x = num[i] + 1;
            while(t1.count(x))x++;
            ans = max(ans, x-num[i]);
        }
    }
    printf(%d,ans);
    return 0;
}
暂无评论

发送评论 编辑评论

上一篇
下一篇