哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈哈老娘要放假啦

懵逼的 题目

传送至 Luogu

扯淡的 题解

最小路径覆盖, 就是在一个DAG里面找出最少的几条不相交路径, 使这些路径包含DAG里的所有点…
这里的不相交有两种情况:

1. 严格不相交, 即不能有一个节点在不同路径上出现
2. 非严格不相交, 即点可以重复出现, 当然边也可以...
  1. 严格不想交的情况可以转化为二分图解决, 把每个点裂成两个(注意, 裂点是网络流常用技巧…), 比如说x1, x2, 那么对于每一条有向边(x, y), 我们可以在二分图中这样连x1 -> y2然后就得到一个二分图, n - 二分图的最大匹配数 = 最小路径覆盖的路径条数
    因为在二分图中多匹配一条边, 就相当于在原图中把两条路径覆盖联结成一个, 覆盖数减少了1 (设开始的时候一个点就是一个覆盖ans = n;, 这时就可以ans--;), 所以n - 二分图的最大匹配数 = 最小路径覆盖的路径条数Emmmmmmmm…

  2. 非严格的话…就是Floyd一下…判断两个点在有向图中是否能到达, 就可以把每两个点之间连边了…然后就和上面的一样了…
    想一想…如果允许边重复出现, 是不是就相当于Floyd走了”中间节点”…所以说Floyd的作用就是把原图中相隔比较远的(中间的节点可能被其他路径覆盖而不能再次覆盖)两个节点间连一条边, 把两个节点的距离”缩短”, 从而达到非严格转变为严格的目的…

注意几个细节…

  • 连边的时候要注意from节点是否已经和s之间有边了…
  • 记录路径的时候注意判断每条边的from是不是s…否则会覆盖掉一些记录前驱的数组(to当然也要判断是不是 == t)…

沙茶的 代码

就是上面的细节没注意改了好久(O(Day2))…

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#define MAXN (1600 + 5)
#define INF (0x7ffffff)
#define MAXM (30000 + 5)
#define rev(a) (((a - 1) ^ 1) + 1)
#define cor(a) ((a) + (MAXN))
#define rec(a) ((a > MAXN) ? (a - MAXN) : (a))
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
using namespace std;
int s = 0, t = MAXN * 2 - 1;
struct edg
{
    int from;
    int to;
    int next;
    int cap;
    int flow;
    edg() {}
    edg(int fr, int t, int ne, int c, int fl): from(fr), to(t), next(ne), cap(c), flow(fl) {}
} b[MAXM << 1];
int cntb = 0;
int g[MAXN << 1];

int n;
int m;
int dis[(MAXN << 1) + 5];
int nex[MAXN];
int pre[MAXN];
int cnt = 0;
int out[MAXN << 1][MAXN << 1];
void adn(int, int, int);
int mach(int);
int dinic(int, int);
bool bfs();
void solve();
void initout();
void init();
void dfs(int, int);
int main()
{
    init();
    solve();
    return 0;
}
void init()
{
    scanf("%d%d", &n, &m);
    int srx, sry;
    bool vis[MAXN << 1];
    memset(vis, false, sizeof(vis));
    for (int i = 1; i <= m; i++)
    {
        scanf("%d%d", &srx, &sry);
        adn(srx, cor(sry), 1);
        adn(cor(sry), srx, 0);
        if (!vis[srx])
        {
            adn(s, srx, 1);
            adn(srx, s, 0);
            vis[srx] = true;
        }
        if (!vis[cor(sry)])
        {
            adn(cor(sry), t, 1);
            adn(t, cor(sry), 0);
            vis[cor(sry)] = true;
        }
    }
}
void adn(int fr, int to, int ca)
{
    b[++cntb] = edg(fr, to, g[fr], ca, 0);
    g[fr] = cntb;
}
void solve()
{
    int re = 0;
    while (bfs())
    {
        re += dinic(s, INF);
    }
    initout();
    for (int i = 1; i <= cnt; i++)
    {
        for (int j = 1; j <= out[i][0]; j++)
        {
            printf("%d ", out[i][j]);
        }
        puts("");
    }
    printf("%d", cnt);
}
int dinic(int dq, int maxf)
{
    if (dq == t || (!maxf))
        return maxf;
    int re = 0;
    for (int i = g[dq]; i; i = b[i].next)
    {
        if ((dis[b[i].to] == dis[dq] + 1) && (b[i].cap - b[i].flow > 0))
        {
            int zl = dinic(b[i].to, min(maxf, b[i].cap - b[i].flow));
            maxf -= zl;
            b[i].flow += zl;
            b[rev(i)].flow -= zl;
            re += zl;
            /*if (zl > 0 && b[i].to != t)
                nex[rec(dq)] = rec(b[i].to), pre[rec(b[i].to)] = rec(dq);*/
        }
    }
    return re;
}
bool bfs()
{
    memset(dis, 0, sizeof(dis));
    dis[s] = 1;
    queue<int> q;
    q.push(s);
    while (!q.empty())
    {
        int dq = q.front();
        q.pop();
        for (int i = g[dq]; i; i = b[i].next)
        {
            if ((!dis[b[i].to]) && b[i].cap - b[i].flow > 0)
            {
                dis[b[i].to] = dis[dq] + 1;
                q.push(b[i].to);
            }
        }
    }
    return dis[t];
}
void initout()
{
    for (int i = 1; i <= cntb; i++)
    {
        if (b[i].from != s && b[i].cap == b[i].flow && b[i].cap == 1 && b[i].to != t)
        {
            pre[rec(b[i].to)] = rec(b[i].from);
            nex[rec(b[i].from)] = rec(b[i].to);
        }
    }
    memset(out, 0, sizeof(out));
    bool v[MAXN];
    memset(v, false, sizeof(v));
    for (int i = 1; i <= n; i++)
    {
        if (!v[i])
        {
            v[i] = true;
            ++cnt;
            int dq = i;
            v[dq] = true;
            out[cnt][++out[cnt][0]] = dq;
            while (nex[dq] && pre[nex[dq]] == dq)
            {
                dq = nex[dq];
                v[dq] = true;
                out[cnt][++out[cnt][0]] = dq;
            }
        }
    }
}

By 不想月考的 Cansult