「网络流 24 题」最小路径覆盖

Posted on | In , ,

DAG最小路径覆盖=|V|-最大匹配数

题目链接

题解

  • 将每次点拆成两个点，分别为入点和出点，对于每条边(u,v)，u的出点到v的入点建一条边，S到所有出点建边，T到所有入点建边
  • 这样建图满足二分图，跑最大流
  • 最小路径覆盖=|V|-最大匹配数

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
#include<bits/stdc++.h>
using namespace std;
const int maxn = 805;
const int INF=1e9+7;

int n, m, u, v;

// Dinic(最大流算法)

struct Edge
{
    int from, to, cap, flow;
    Edge(int u,int v,int c,int f):from(u), to(v), cap(c), flow(f) {}
};

bool vis[maxn];
struct Dinic
{
    int n, m, s, t;       // 节点数,边数(包括反向弧),源点编号和汇点编号
    vector<Edge> edges;   // 边数。edges[e]和edges[e^1]互为反向弧
    vector<int> G[maxn];  // 邻接表，G[i][j]表示节点i的第j条边在e数组的序号
    bool vis[maxn];      // BFS使用
    int d[maxn];          // 从起点到i的距离
    int cur[maxn];        // 当前弧下标

    void init()
    {
        for(int i=0; i<=n; i++)
            G[i].clear();
        edges.clear();
    }

    void Addedge(int from, int to, int cap)
    {
        edges.push_back(Edge(from, to, cap, 0));
        edges.push_back(Edge(to, from, 0, 0));
        m = edges.size();
        G[from].push_back(m-2);
        G[to].push_back(m-1);
    }

    bool BFS()
    {
        memset(vis,0,sizeof(vis));
        queue<int>Q;
        Q.push(s);
        d[s]=0;
        vis[s]=1;
        while(!Q.empty())
        {
            int x=Q.front();
            Q.pop();
            for(int i=0; i<G[x].size(); i++)
            {
                Edge& e=edges[G[x][i]];
                if(!vis[e.to] && e.cap>e.flow) //只考虑残量网络中的弧
                {
                    vis[e.to]=1;
                    d[e.to]=d[x]+1;
                    Q.push(e.to);
                }
            }
        }
        return vis[t];
    }

    int DFS(int x,int a)
    {
        if(x==t || a==0)
            return a;
        int flow=0, f;
        for(int& i=cur[x]; i<G[x].size(); i++) // 从上次考虑的弧
        {
            Edge& e=edges[G[x][i]];
            if(d[x]+1 == d[e.to] && (f=DFS(e.to, min(a, e.cap-e.flow)))>0)
            {
                e.flow+=f;
                edges[G[x][i]^1].flow-=f;
                flow+=f;
                a-=f;
                if(a==0)
                    break;
            }
        }
        return flow;
    }

    int Maxflow(int s,int t)
    {
        this->s=s;
        this->t=t;
        int flow=0;
        while(BFS())
        {
            memset(cur, 0, sizeof(cur));
            flow += DFS(s,INF);
        }
        return flow;
    }
};

int to[maxn];

int main()
{
    Dinic now;
    scanf("%d%d", &n, &m);
    int st=0, ed=2*n+1;
    for(int i=1; i<=m; i++)
    {
        scanf("%d%d", &u, &v);
        now.Addedge(u,v+n, 1);
    }
    for(int i=1; i<=n; i++)
    {
        now.Addedge(st, i, 1);
        now.Addedge(i+n, ed, 1);
    }
    int ans=n-now.Maxflow(st, ed);
    for(int i=1; i<=n; i++)
    {
        for (int j = 0; j < now.G[i].size(); j++)
        {
            Edge& e = now.edges[now.G[i][j]];
            if (e.flow == 1)
            {
                to[i] = e.to-n;
                break;
            }//找到匹配边        }

        }
    }
    for (int i = 1; i <= n; i++)
    {
        if (!vis[i])
        {
            int x = i;
            while (x)
            {
                printf("%d ", x);
                vis[x] = 1;
                x = to[x];
            }
            printf("\n");
        }
    }
    printf("%d\n", ans);
}