网络流 #有源汇上下界费用流 #最小点覆盖 #Year2002 #POI

最小点覆盖问题

这里可以直接有源汇上下界费用流

// Author: xiaruize
#ifndef ONLINE_JUDGE
#define debug(x) cerr << "On Line:" << __LINE__ << #x << "=" << x << endl
bool start_of_memory_use;
#else
#define debug(x)
#endif
#include <bits/stdc++.h>
using namespace std;
#ifndef ONLINE_JUDGE
clock_t start_clock = clock();
#endif
#define ull unsigned long long
#define ALL(a) (a).begin(), (a).end()
#define pb push_back
#define mk make_pair
#define pii pair<int, int>
#define pis pair<int, string>
#define sec second
#define fir first
#define sz(a) int((a).size())
#define Yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define No cout << "No" << endl
#define NO cout << "NO" << endl
#define mms(arr, n) memset(arr, n, sizeof(arr))
#define rep(i, a, n) for (int i = (a); i <= (n); ++i)
#define per(i, n, a) for (int i = (n); i >= (a); --i)
int max(int a, int b)

{
    if (a > b)
        return a;
    return b;
}
int min(int a, int b)
{
    if (a < b)
        return a;
    return b;
}
const int INF = 0x3f3f3f3f;
const int MOD = 1000000007;
const int N = 2e5 + 10;

namespace MCMF
{
    const int MAXN = 5005, MAXM = 2000005;
    int head[MAXN], cnt = 1;
    struct Edge
    {
        int to, w, c, next;
    } edges[MAXM * 2];
    inline void add(int from, int to, int w, int c)
    {
        edges[++cnt] = {to, w, c, head[from]};
        head[from] = cnt;
    }
    inline void addEdge(int from, int to, int w, int c)
    {
        add(from, to, w, c);
        add(to, from, 0, -c);
    }
    int s, t, dis[MAXN], cur[MAXN];
    bool inq[MAXN], vis[MAXN];
    queue<int> Q;
    bool SPFA()
    {
        while (!Q.empty())
            Q.pop();
        copy(head, head + MAXN, cur);
        fill(dis, dis + MAXN, INF);
        dis[s] = 0;
        Q.push(s);
        while (!Q.empty())
        {
            int p = Q.front();
            Q.pop();
            inq[p] = 0;
            for (int e = head[p]; e != 0; e = edges[e].next)
            {
                int to = edges[e].to, vol = edges[e].w;
                if (vol > 0 && dis[to] > dis[p] + edges[e].c)
                {
                    dis[to] = dis[p] + edges[e].c;
                    if (!inq[to])
                    {
                        Q.push(to);
                        inq[to] = 1;
                    }
                }
            }
        }
        return dis[t] != INF;
    }
    int dfs(int p = s, int flow = INF)
    {
        if (p == t)
            return flow;
        vis[p] = 1;
        int rmn = flow;
        for (int eg = cur[p]; eg && rmn; eg = edges[eg].next)
        {
            cur[p] = eg;
            int to = edges[eg].to, vol = edges[eg].w;
            if (vol > 0 && !vis[to] && dis[to] == dis[p] + edges[eg].c)
            {
                int c = dfs(to, min(vol, rmn));
                rmn -= c;
                edges[eg].w -= c;
                edges[eg ^ 1].w += c;
            }
        }
        vis[p] = 0;
        return flow - rmn;
    }
    int maxflow, mincost;
    inline void run(int s, int t)
    {
        MCMF::s = s, MCMF::t = t;
        while (SPFA())
        {
            int flow = dfs();
            maxflow += flow;
            mincost += dis[t] * flow;
        }
    }
} // namespace MCMF

int n;
int deg[N];

void solve()
{
    cin >> n;
    rep(i, 1, n)
    {
        MCMF::addEdge(0, i, INF, 1);
        MCMF::addEdge(i, n + 1, INF, 0);
        int x;
        cin >> x;
        rep(j, 1, x)
        {
            int y;
            cin >> y;
            deg[i]--;
            deg[y]++;
            MCMF::addEdge(i, y, INF, 0);
        }
    }
    MCMF::addEdge(n + 1, 0, INF, 0);
    rep(i, 1, n)
    {
        if (deg[i] > 0)
            MCMF::addEdge(n + 2, i, deg[i], 0);
        else
            MCMF::addEdge(i, n + 3, -deg[i], 0);
    }
    MCMF::run(n + 2, n + 3);
    cout << MCMF::mincost << endl;
}

signed main()
{
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int testcase = 1;
    // cin >> testcase;
    while (testcase--)
        solve();
#ifndef ONLINE_JUDGE
    bool end_of_memory_use;
    cerr << "Memory use:" << (&end_of_memory_use - &start_of_memory_use) / 1024.0 / 1024.0 << "MiB" << endl;
    cerr << "Time use:" << (double)(clock() - start_clock) / CLOCKS_PER_SEC * 1000.0 << "ms" << endl;
#endif
    return 0;
}