P2764 最小路径覆盖问题 (最小点覆盖=顶点数-最大匹配)

题意:最小路径覆盖

题解:对于一个有向图,最小点覆盖 = 顶点数 - 最大匹配

　　这里的最大匹配指的是将原图中每一个点拆成入点、出点, 每条边连接起点的出点和终点的入点

　　源点S连接每个点的出点,汇点T连接每个点的入点,这样建出来的二分图的最大匹配

　　然后输出路径被坑了很久因为自己拆点的标号问题吧

　　我的拆点方式入点是偶数出点是奇数然后特判哪里就要写清楚

#include <bits/stdc++.h>

using namespace std;

const int INF = 0x3f3f3f3f;

int n, m, s, t, cnt, maxflow;

struct node {

    int to, nex, val;

}E[20005];

int head[305];

int cur[305];

void addedge(int x, int y, int va) {

    E[++cnt].to = y; E[cnt].nex = head[x]; head[x] = cnt; E[cnt].val = va;

    E[++cnt].to = x; E[cnt].nex = head[y]; head[y] = cnt; E[cnt].val = 0;

}

int inque[305];

int dep[305];

int to[305];

bool bfs() {

    for(int i = 0; i <= n * 2 + 1; i++) cur[i] = head[i], inque[i] = 0, dep[i] = INF;

    queue<int> que;

    dep[s] = 0; inque[s] = 1;

    que.push(s);

    while(!que.empty()) {

        int u = que.front();

        que.pop();

        inque[u] = 0;

        for(int i = head[u]; i; i = E[i].nex) {

            int v = E[i].to;

            if(E[i].val > 0 && dep[v] > dep[u] + 1) {

                dep[v] = dep[u] + 1;

                if(!inque[v]) {

                    inque[v] = 1;

                    que.push(v);

                }

            }

        }

    }

    if(dep[t] != INF) return true;

    return false;

}

int vis;

int viss[155];

int dfs(int x, int flow) {

    if(x == t) {

        vis = 1;

        maxflow += flow;

        return flow;

    }

    int used = 0;

    int rflow = 0;

    for(int i = cur[x]; i; i = E[i].nex) {

        cur[x] = i;

        int v = E[i].to;

        if(E[i].val > 0 && dep[v] == dep[x] + 1) {

            if(rflow = dfs(v, min(flow - used, E[i].val))) {

                if(v != t && x != s && (x % 2 == 0) && (v % 2 == 1)) to[x / 2] = v / 2, viss[v / 2] = 1;

                used += rflow;

                E[i].val -= rflow;

                E[i ^ 1].val += rflow;

                if(used == flow) break;

            }

        }

    }

    return used;

}

void dinic() {

    maxflow = 0;

    while(bfs()) {

        vis = 1;

        while(vis) {

            vis = 0;

            dfs(s, INF);

        }

    }

}

int main() {

    scanf("%d%d", &n, &m);

    s = 0, t = 1;

    cnt = 1;

    for(int i = 1; i <= n; i++) {

        addedge(s, i << 1, 1);

        addedge(i << 1 | 1, t, 1);

    }

    for(int i = 1; i <= m; i++) {

        int a, b;

        scanf("%d%d", &a, &b);

        addedge(a << 1, b << 1 | 1, INF);

    }

    dinic();

    int ans = n - maxflow;

    for(int i = 1; i <= n; i++) {

        if(!viss[i]) {

            printf("%d", i);

            for(int j = to[i]; j; j = to[j]) printf(" %d", j);

            puts("");

        }

    }

    printf("%d\n", ans);

    return 0;

}

巴特西

P2764 最小路径覆盖问题 (最小点覆盖=顶点数-最大匹配)

最新文章

热门文章