题目描述
滑雪场坐落在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;
- }
没有帐号? 立即注册