洛谷 P4843 清理雪道

题目描述

滑雪场坐落在FJ省西北部的若干座山上。

从空中鸟瞰，滑雪场可以看作一个有向无环图，每条弧代表一个斜坡（即雪道），弧的方向代表斜坡下降的方向。

你的团队负责每周定时清理雪道。你们拥有一架直升飞机，每次飞行可以从总部带一个人降落到滑雪场的某个地点，然后再飞回总部。从降落的地点出发，这个人可以顺着斜坡向下滑行，并清理他所经过的雪道。

由于每次飞行的耗费是固定的，为了最小化耗费，你想知道如何用最少的飞行次数才能完成清理雪道的任务。

输入输出格式

输入格式：

输入文件的第一行包含一个整数n (2 <= n <= 100) – 代表滑雪场的地点的数量。

接下来的n行，描述1~n号地点出发的斜坡，第i行的第一个数为mi (0 <= mi < n) ，后面共有mi个整数，由空格隔开，每个整数aij互不相同，代表从地点i下降到地点aij的斜坡。每个地点至少有一个斜坡与之相连。

输出格式：

输出文件的第一行是一个整数k – 直升飞机的最少飞行次数。

输入输出样例

输入样例#1：复制

输出样例#1：复制

打一打上下界网络流，其实就是个下界最小流。

显然，一条边至少被经过一次，就是流量至少为1，然后可以从每一个点出发，每一个点终止，就源点连所有点连1，所有点连汇点连1就行了。

注意上下界最小流要先求出可行流再反向增广。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#define LL long long
using namespace std;
const int maxn = 2e2 + 5;
const int maxm = 5e4 + 5;
const LL inf = 0x3f3f3f3f3f3f3f3f;
const int iinf = 0x3f3f3f3f;
struct edge {
    int v, w, next;
} e[maxm];
int head[maxn], cnt;
void adde(const int &u, const int &v, const int &w) {
    e[cnt] = (edge) {v, w, head[u]};
    head[u] = cnt++;
    e[cnt] = (edge) {u, 0, head[v]};
    head[v] = cnt++;
}

int layer[maxn], iter[maxn], SS, TT, n, m, S, T, u, v, w;

void ADDE(const int &u, const int &v, const int &l, const int &r) {
    //cerr << u << "------" << l << "," << r << "----->" << v << endl;
    adde(SS, v, l);
    adde(u, TT, l);
    adde(u, v, r - l);
}

bool bfs(int s, int t) {
    queue<int > q;
    memcpy(iter, head, sizeof(head));
    memset(layer, 0, sizeof(layer));
    layer[s] = 1, q.push(s);
    while(!q.empty()) {
        int u = q.front(); q.pop();
        for(register int i = head[u]; ~i; i = e[i].next) {
            int v = e[i].v;
            if(!e[i].w || layer[v]) continue;
            layer[v] = layer[u] + 1;
            q.push(v);
        }
    }
    return layer[t];
}

LL dfs(int u, int t, LL mn) {
    LL ret = 0, tmp;
    if(u == t) 
        return mn;
    for(register int &i = iter[u]; ~i; i = e[i].next) {
        int v = e[i].v;
        if(!e[i].w || layer[v] != layer[u] + 1) continue;
        tmp = dfs(v, t, min((LL)e[i].w, mn - ret));
        e[i].w -= tmp, e[i ^ 1].w += tmp, ret += tmp;
        if(ret == mn) return ret;
    }
    return ret;
}

LL Dinic(int s, int t) {
    LL ans = 0;
    while(bfs(s, t))
        ans += dfs(s, t, inf);
    return ans;
}

int L[maxn], R[maxn], id[maxn], od[maxn], icnt;
LL solve() {
    LL res = Dinic(SS, TT);
    res = e[cnt - 1].w;
    for(register int i = head[SS]; ~i; i = e[i].next)
        e[i].w = e[i ^ 1].w = 0;
    for(register int i = head[TT]; ~i; i = e[i].next)
        e[i].w = e[i ^ 1].w = 0;
    e[cnt - 1].w = e[cnt - 2].w = 0;
    return res - Dinic(T, S);
}

int main() {
    memset(head, -1, sizeof(head));
    scanf("%d", &n);
    for(register int i = 1; i <= n; ++i)
        L[i] = ++icnt, R[i] = ++icnt;
    S = ++icnt, T = ++icnt, SS = ++icnt, TT = ++icnt;
    for(register int i = 1; i <= n; ++i) {
        scanf("%d", &u);
        for(register int j = 1; j <= u; ++j)
            scanf("%d", &v), ADDE(i, v, 1, iinf);
    }
    for(register int i = 1; i <= n; ++i)
        ADDE(S, i, 0, iinf), ADDE(i, T, 0, iinf);
    adde(T, S, iinf);
    printf("%lld", solve());
    return 0;
}

Rockdu's Blog