CF 976F Minimal k-covering

传送门

题目大意

给你一张二分图 G=(U,V,E) G = ( U , V , E ) $G = (U, V, E)$， U U $U$ 是图的 X$X$$X$ 部， V V $V$ 是图的 Y$Y$$Y$ 部， E E $E$ 是边集，可能有重边。

我们称 E$E$$E$ 的某个子集 E¯¯¯¯ E ¯ $\overline E$ 是 k-覆盖 的，当且仅当图 G¯¯¯¯=(U,V,E¯¯¯¯) G ¯ = ( U , V , E ¯ ) $\overline G = (U, V, \overline E)$ 的每个顶点至少连接了 k k $k$ 条边；若 E¯¯¯¯$\overline{E}$$\overline E$ 是 k-覆盖 的且不存在元素个数比它更小的边集也是 k-覆盖 的，则称 E¯¯¯¯ E ¯ $\overline E$ 是一个 最小k-覆盖 。

你的任务是对于所有 k∈[0,minDegree] k ∈ [ 0 , m i n D e g r e e ] $k \in [0, minDegree]$，求出 最小k-覆盖，其中 minDegree m i n D e g r e e $minDegree$ 是图 G G $G$ 的所有点度数的最小值。

输入格式

第一行输入三个整数 n1$n_1$$n_1$， n2 n 2 $n_2$ 和 m m $m$（1≤n1,n2≤2000$1\le n_1,n_2\le 2000$$1 \le n_1, n_2 \le 2000$， 0≤m≤2000 0 ≤ m ≤ 2000 $0 \le m \le 2000$），分别代表 U U $U$ 的点数，V$V$$V$ 的点数和边数。

接下来 m m $m$ 行每行两个整数 ui$u_i$$u_i$ 和 vi v i $v_i$，表示第 i i $i$ 条边在 U$U$$U$ 中的端点为 ui u i $u_i$，在 V V $V$ 中的端点为 vi$v_i$$v_i$。

输出格式

输出包含 minDegree+1 m i n D e g r e e + 1 $minDegree + 1$ 行，每行首先输出一个整数 cntk c n t k $cnt_k$，表示 最小k-覆盖 的边集大小，紧接着输出 cntk c n t k $cnt_k$ 个整数，表示属于 最小k-覆盖 的边的标号。边按输入顺序从 1 1 $1$ 开始标号。输出时不必按标号从小到大输出。

思路

  唉，我太弱了，什么都不会，这么简单的傻逼题都做不来。

  一开始我想可以跑一个带上下界的最小费用流，发现好像对于每个 k$k$$k$ 都要重新跑，怕是凉了。唉，我太弱啦！

  需要发现这么一个性质：如果源点向 X X $X$ 部的连边以及 Y$Y$$Y$ 部向汇点的连边的容量都是对应点的度数，则一定满流，因为一个流量就对应一条边。我们考虑反着做：令源点或汇点的边的容量为对应点的度数减去 k k $k$，然后跑最大流。最大流中没有流量的边就是我们要选的边。

  显然，由于每个点的对应的容量变小了，因此肯定有对应边不能增广，也就满足了度数至少为 k$k$$k$ 的条件。由于跑的是最大流，因此得到的答案中删的边也是最多的，这使得留下的边最小。

  我们从大到小枚举 k k $k$，每次在上一次的基础上继续增广。由于增广次数不超过 m$m$$m$ 次，因此时间复杂度为 O((n+m)m) O ( ( n + m ) m ) $O((n + m)m)$。

参考代码

#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <cassert>
#include <cctype>
#include <climits>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <list>
#include <functional>
typedef long long LL;
typedef unsigned long long ULL;
using std::cin;
using std::cout;
using std::endl;
typedef int INT_PUT;
INT_PUT readIn()
{
    INT_PUT a = 0; bool positive = true;
    char ch = getchar();
    while (!(ch == '-' || std::isdigit(ch))) ch = getchar();
    if (ch == '-') { positive = false; ch = getchar(); }
    while (std::isdigit(ch)) { a = a * 10 - (ch - '0'); ch = getchar(); }
    return positive ? -a : a;
}
void printOut(INT_PUT x)
{
    char buffer[20]; int length = 0;
    if (x < 0) putchar('-'); else x = -x;
    do buffer[length++] = -(x % 10) + '0'; while (x /= 10);
    do putchar(buffer[--length]); while (length);
}

const int INF = (~(int(1) << (sizeof(int) * 8 - 1))) >> 1;
const int maxn = 2005;
int n1, n2, m;

struct NetworkFlow
{
    struct Edge
    {
        int from, to, cap, flow;
        Edge() {}
        Edge(int from, int to, int cap) : from(from), to(to), cap(cap), flow() {}
    };
    std::vector<Edge> edges;
    std::vector<std::vector<int> > G;
    void addEdge(int from, int to, int cap)
    {
        edges.push_back(Edge(from, to, cap));
        edges.push_back(Edge(to, from, 0));
        int i = edges.size();
        G[from].push_back(i - 2);
        G[to].push_back(i - 1);
    }
    int s, t;

    struct Queue
    {
        int c[maxn * 2];
        int head, tail;
        Queue() { clear(); }
        void clear() { head = tail = 0; }
        void push(int x) { c[tail++] = x; }
        void pop() { head++; }
        int front() { return c[head]; }
        bool empty() { return head == tail; }
    } q;
    int vis[maxn * 2];
    int opt[maxn * 2];
    int pre[maxn * 2];
    bool BFS()
    {
        q.clear();
        static int stamp;
        stamp++;
        memset(opt, 0, sizeof(opt));
        opt[s] = INF;
        vis[s] = stamp;
        q.push(s);
        while (!q.empty())
        {
            int from = q.front();
            q.pop();
            for (int i = 0; i < G[from].size(); i++)
            {
                const Edge& e = edges[G[from][i]];
                if (e.flow < e.cap && vis[e.to] != stamp)
                {
                    opt[e.to] = std::min(opt[from], e.cap - e.flow);
                    pre[e.to] = G[from][i];
                    vis[e.to] = stamp;
                    q.push(e.to);
                    if (vis[t] == stamp)
                    {
                        q.clear();
                        break;
                    }
                }
            }
        }
        if (vis[t] != stamp) return false;
        for (int u = t; u != s; u = edges[pre[u]].from)
        {
            edges[pre[u]].flow += opt[t];
            edges[pre[u] ^ 1].flow -= opt[t];
        }
        return true;
    }

    void maxFlow()
    {
        while (BFS());
    }

    NetworkFlow() {}
} nf;

int base;
void statistic(std::vector<int>& ans)
{
    nf.maxFlow();
    for (int i = 1; i <= m; i++)
        if (!nf.edges[(i - 1) << 1].flow)
            ans.push_back(i);
}

int minDegree = INF;
int degree[maxn * 2];
std::vector<std::vector<int> > ans;

void run()
{
    n1 = readIn();
    n2 = readIn();
    m = readIn();
    nf.G.resize(n1 + n2 + 2);
    nf.s = 0;
    nf.t = n1 + n2 + 1;

    for (int i = 1; i <= m; i++)
    {
        int u = readIn();
        int v = readIn() + n1;
        degree[u]++;
        degree[v]++;
        nf.addEdge(u, v, 1);
    }
    for (int i = 1; i <= n1 + n2; i++)
        minDegree = std::min(minDegree, degree[i]);
    int base = (nf.edges.size() >> 1) - 1;

    for (int i = 1; i <= n1; i++)
        nf.addEdge(nf.s, i, degree[i] - minDegree);
    for (int i = 1; i <= n2; i++)
        nf.addEdge(n1 + i, nf.t, degree[n1 + i] - minDegree);

    ans.resize(minDegree + 1);
    statistic(ans[minDegree]);
    for (int i = minDegree - 1; ~i; i--)
    {
        for (int j = 1; j <= n1 + n2; j++)
            nf.edges[(base + j) << 1].cap++;
        statistic(ans[i]);
    }

    for (int i = 0; i <= minDegree; i++)
    {
        printOut(ans[i].size());
        for (int j = 0; j < ans[i].size(); j++)
        {
            putchar(' ');
            printOut(ans[i][j]);
        }
        putchar('\n');
    }
}

int main()
{
    run();
    return 0;
}