水题笔记_ 试题库问题 [网络流24, 最大流, 水题]

语文是OI的考察范围

懵逼的 题目

传送至 Luogu

扯淡的 题解

这大概是最水的一道紫题了吧…难度虚高@丁虚高

大概题目比较难懂 或者我语文太烂
题目就是说: 一些试卷, 每张试卷都可以归到特定的组里面, (一张试卷只能用一次), 每个组都有特定的大小(即一个组需要恰好有这么多的试卷归在里面), 问如何完成…

把试卷放在左边, 属性放在右边…就是一个很简单的二分图…
连边…

  • s向所有的试卷都连一条cap = 1的边, 代表每道题都只能选一遍
  • 所有的试卷向他所拥有的属性连一条cap = 1的边, 代表选了这道题, 可以归到他有的这些属性里的任意一个
  • 所有的属性向t连一条cap = 属性需要的题目数量的边, 代表一个属性需要有这么多的题

跑最大流, 如果答案比m小, 无解, 否则输出方案

没了…是不是很简单…?

沙茶的 代码

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
149
150
151
152
153
154
155
156
157
158
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#define MAXN (2000 + 5)
#define MAXM (4000 + 5)
#define INF (0x7ffffff)
#define MAXT (1000 + 5)
#define max(a, b) ((a) > (b) ? (a) : (b))
#define min(a, b) ((a) < (b) ? (a) : (b))
#define rev(a) (((a - 1) ^ 1) + 1)
#define bh(a) ((a) + MAXT)
#define ubh(a) ((a) - MAXT)
const int s = 0, t = MAXN - 1;
using namespace std;
struct edg
{
int from;
int to;
int next;
int cap;
int flow;
edg(){}
edg(int a, int b, int c, int d, int e): from(a), to(b), next(c), cap(d), flow(e){}
}b[MAXM << 1];
int cntb;
int g[MAXN];

int dis[MAXN];

int n;
int kn;
int m;
int ans;
void adn(int, int, int);
void init();
void solve();
int dinic(int, int);
bool bfs();
void print();
int main(int argc, char const *argv[])
{
init();
solve();
if (ans ^ m)
{
puts("No Solution!");
return 0;
}
print();
return 0;
}
void adn(int from, int to, int cap)
{
b[++cntb] = edg(from, to, g[from], cap, 0);
g[from] = cntb;
}
void init()
{
scanf("%d%d", &kn, &n);
for (int i = 1; i <= kn; i++)
{
int srx;
scanf("%d", &srx);
m += srx;
adn(bh(i), t, srx);
adn(t, bh(i), 0);
}
for (int i = 1; i <= n; i++)
{
adn(s, i, 1);
adn(i, 1, 0);
int srn;
scanf("%d", &srn);
for (int j = 1; j <= srn; j++)
{
int srx;
scanf("%d", &srx);
adn(i, bh(srx), 1);
adn(bh(srx), i, 0);
}
}
}
void solve()
{
while (bfs())
{
int zl = dinic(s, INF);
ans += zl;
}
}
bool bfs()
{
memset(dis, 0, sizeof(dis));
queue<int> q;
q.push(s);
dis[s] = 1;
while (!q.empty())
{
int dq = q.front();
q.pop();
for (int i = g[dq]; i; i = b[i].next)
{
if (b[i].cap > b[i].flow && !dis[b[i].to])
{
dis[b[i].to] = dis[dq] + 1;
q.push(b[i].to);
}
}
}
return dis[t];
}
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 (b[i].cap > b[i].flow && dis[b[i].to] == dis[dq] + 1)
{
int zl = dinic(b[i].to, min(b[i].cap - b[i].flow, maxf));
maxf -= zl;
re += zl;
b[i].flow += zl;
b[rev(i)].flow -= zl;
}
}
return re;
}
void print()
{
vector<int> out[MAXT];
for (int i = 0; i <= cntb; i++)
{
if (b[i].cap == b[i].flow && b[i].cap > 0 && b[i].to > MAXT && b[i].from <= MAXT)
{
out[ubh(b[i].to)].push_back(b[i].from);
}
}
for (int i = 1; i <= kn; i++)
{
printf("%d: ", i);
for (int j = 0; j < out[i].size(); j++)
{
printf("%d ", out[i][j]);
}
puts("");
}
}

/*
1 1
1
1 1
*/

By 皮了一下把班里电脑头像换成香蕉君很开心的 Cansult

一天连着翘两节那才叫爽!