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

```8
1 3
1 7
2 4 5
1 8
1 8
0
2 6 5
0```

`4​﻿​`

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

```#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];
void adde(const int &u, const int &v, const int &w) {
e[cnt] = (edge) {v, w, head[u]};
e[cnt] = (edge) {u, 0, head[v]};
}

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;
}

bool bfs(int s, int t) {
queue<int > q;
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() {
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)
printf("%lld", solve());
return 0;
}```

341 人读过

0 条评论