icontofig | 发布于 2019-12-06 08:04:34 | 阅读量 401 | 费用流 网络流
发布于 2019-12-06 08:04:34 | 费用流 网络流


#include <bits/stdc++.h>
using namespace std;
const int maxn = 405;
const int INF = 1e9;
typedef long long ll;
ll a[maxn],b[maxn],c[maxn];
int p[maxn];
int d[maxn<<1],vis[maxn<<1];
deque<int>q;
int n;
struct edge{
    int to,next,cap,cost;
}e[maxn*maxn*2];
int S,T;
int h[maxn<<1];
int cnt = 0;
void add(int u,int v,int cap,int cost){
    e[cnt].to = v;e[cnt].cap = cap;e[cnt].cost = cost;
    e[cnt].next = h[u];h[u] = cnt++;
    return;
}
bool spfa(int s,int t){
    for(int i = s;i <= t;++i){
        d[i] = -INF;
        vis[i] = 0;
    }
    d[t] = 0;
    vis[t] = 1;
    q.push_back(t);
    while(!q.empty()){
        int now = q.front();
        q.pop_front();
        vis[now] = 0;
        for(int i = h[now];i != -1;i = e[i].next){
            int v = e[i].to;
            if(e[i^1].cap && d[v] < d[now] - e[i].cost){
                d[v] = d[now] - e[i].cost;
                if(!vis[v]){
                    vis[v] = 1;
                    if(!q.empty() && d[q.front()] < d[v])q.push_front(v);
                    else q.push_back(v);
                }
            }
        }
    }
    return (d[s] != -INF);
}
int cur[maxn<<1];
int ans = 0;
int dfs(int now,int a){
    if(a == 0 || now == T){
        vis[T] = 1;
        return a;
    }
    vis[now] = 1;
    int flow = 0,f;
    for(int &i = cur[now];i != -1;i = e[i].next){
        int v = e[i].to;
        if(e[i].cap > 0 && d[v] == d[now] - e[i].cost && !vis[v]){
            f = min(e[i].cap,a - flow);
            f = dfs(v,f);
            ans += f * e[i].cost;
            flow += f;
            e[i].cap -= f;
            e[i^1].cap += f;
            if(flow == a)break;
        }
    }
    return flow;
}
int flow(int s,int t){
    int flow = 0;
    ans = 0;
    while(spfa(s,t)){
        for(int i = s;i <= t;++i)cur[i] = h[i],vis[i] = 0;
        flow += dfs(s,INF);
    }
    return flow;
}



内容更新于: 2019-12-06 08:04:34
链接地址: http://blog.leanote.com/post/icontofig/%E8%B4%B9%E7%94%A8%E6%B5%81zkw%E8%B4%B9%E7%94%A8%E6%B5%81%EF%BC%88%E7%B1%BB%E4%BC%BCdi%EF%BC%89

上一篇: 并查集基础讲解

下一篇: 二分图最大匹配KM算法之BFS版本模板

401 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航