[USACO93]Drainage Ditches排水渠

解题报告

题目见SYZOJ 网络流初步。 恩,经历千辛万苦,重构代码无数遍之后,终于把第一发dinic完成了。现在的手速,再写dinic只用7分钟。。。。。

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
const int MX = 305;
const int INF = 100000007;
int dis[MX], head[MX];
int tot, s, t, m, n;
class edge {
public:
    int fr, to, le, ne;
}e[MX * MX];
void addedge(int a, int b, int v) {//邻接表加边,不解释了
    tot++;
    e[tot].fr = a;
    e[tot].to = b;
    e[tot].le = v;
    e[tot].ne = head[a];
    head[a] = tot;
    tot++;//添加反向边
    e[tot].fr = b;
    e[tot].to = a;
    e[tot].ne = head[b];
    head[b] = tot;
}
bool bfs() {//每次进行广搜搜查找,对残量网络进行分层。
    queue  q;
    int now, to;
    memset(dis, 0, sizeof(dis));
    dis[s] = 1;
    q.push(s);
    while (!q.empty()) {
        now = q.front();
        q.pop();
        for (int i = head[now]; i; i = e[i].ne) {
            to = e[i].to;
            if (((!dis[to]) || dis[to] == dis[now] + 1) && e[i].le) {
                dis[to] = dis[now] + 1;
                q.push(to);
            }
        }
    }
    return dis[t];
}
int dfs(int now, int min_flow) {//深搜查找最大流
    int to, now_flow;
    if (now == t) {
        return min_flow;
    }
    for (int i = head[now]; i; i = e[i].ne) {
        to = e[i].to;
        if (dis[to] != dis[now] + 1) continue;//优化,如果下一条边不是下一层,直接跳过
        if (e[i].le <= 0) continue;//如果这一条边已经没有余量,跳过
        now_flow = dfs(to, min(min_flow, e[i].le));
        if (!now_flow) continue;
        e[i].le -= now_flow;
        if (i % 2) e[i + 1].le += now_flow;//反向边处理
        else e[i - 1].le += now_flow;
        return now_flow;
    }
    return 0;
}
int dinic() {
    int ans = 0;
    int tmp;
    while (bfs()) {
        //cout << "flag\n";
        while (tmp = dfs(s, INF)) ans += tmp;
    }
    return ans;
}
int main() {
    int a, b, v;
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d%d%d", &a, &b, &v);
        addedge(a, b, v);
    }
    s = 1;
    t = m;
    printf("%d\n", dinic());
    return 0;
}

 

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

这个站点使用 Akismet 来减少垃圾评论。了解你的评论数据如何被处理