洛谷 P4843 清理雪道
? 解题记录 ? ? 洛谷 ? ? 网络流 ? ? 上下界网络流 ?    2018-12-05 23:08:48    341    0    0

题目描述

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

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

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

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

输入输出格式

输入格式:

 

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

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

 

输出格式:

 

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

 

输入输出样例

输入样例#1: 复制
8
1 3
1 7
2 4 5
1 8
1 8
0
2 6 5
0
输出样例#1: 复制
4​​

 

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

显然,一条边至少被经过一次,就是流量至少为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;
}


上一篇: LOJ#2541. 「PKUWC2018」猎人杀

下一篇: SP705 SUBST1 - New Distinct Substrings

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