「网络流24题」太空飞行计划 最大闭权和子图

Posted on | In , ,

一个有向图，每个点有点权，点权可正可负。对于任意一条有向边i和j，选择了点i就必须选择点j，你需要选择一些点使得得到权值最大。

题目链接

最大闭权和子图

建图

  • s和点之间连一条为边权为点权的边。
  • 使所有非负权点（负权点）连向t，边权为点权的绝对值。
  • 若需要选y才能选x，连一条由x到y的边，边权是∞。

建模分析

考虑点的依赖关系，若将费用转化为流量，最后的满流的最大流即所有需要的花费。

结论

最大点权和=正权点和-最小割(最大流)

题解

  • 最大闭权和子图
  • 转化为最大流
  • 最后a[i]为正的点即为选择的点

代码

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
#include<bits/stdc++.h>
using namespace std;

const int maxn = 222;
const int INF=1e9+7;

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


int a[maxn], n, m;
struct EdmondsKarp
{
    int n, m;
    vector<Edge> edges;
    vector<int> G[maxn];

    int p[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);
    }

    int Maxflow(int s,int t)
    {
        int flow=0;
        while(1)
        {
            memset(a, 0, sizeof(a));
            queue<int>q;
            q.push(s);
            a[s]=1e9+7;
            while(!q.empty())
            {
                int x=q.front(); q.pop();
                for(int i=0;i<G[x].size();i++)
                {
                    Edge& e=edges[G[x][i]];
                   // cout<<e.to<<' '<<e.cap-e.flow<<endl;
                    if(!a[e.to] && e.cap>e.flow)
                    {
                        p[e.to]=G[x][i];
                        a[e.to]=min(a[x], e.cap-e.flow);
                        q.push(e.to);
                    }
                }
                if(a[t]) break;
            }
            if(!a[t]) break;
            for(int u=t; u!=s; u=edges[p[u]].from)
            {
                edges[p[u]].flow+=a[t];
                edges[p[u]^1].flow-=a[t];
            }
            flow+=a[t];
        }
        return flow;
    }
};

int  w, c;

int main()
{
    EdmondsKarp now;
    scanf("%d%d", &n, &m);
    int sum=0;
    for(int i=1; i<=n; i++)
    {
        scanf("%d", &c);
        sum += c;
        now.Addedge(0, i, c);
        while(1)
        {
            char s;
            scanf("%d%c", &c, &s);
            now.Addedge(i, n+c, INF);
            if(s=='\n' || s=='\r')
                break;
        }
    }
    //cout<<123<<endl;
    for(int i=1;i<=m;i++)
    {
        scanf("%d", &c);
        now.Addedge(n+i, n+m+1, c);
    }
    int k = now.Maxflow(0, n+m+1);
    int ans=sum-k;
    int num=0;
    for(int i=1; i<=n; i++)
    {
        if(a[i])
            num++;
    }
    int j=0;
    for(int i=1; i<=n; i++)
    {
        if(a[i])
        {
            j++;
            printf("%d%c", i, j==num?'\n':' ');
        }
    }
    num=j=0;
    for(int i=1; i<=m; i++)
        if(a[i+n])
            num++;
    for(int i=1; i<=m; i++)
        if(a[i+n])
        {
            j++;
            printf("%d%c", i, j==num?'\n':' ');
        }
    printf("%d\n", ans);
    return 0;
}