题面
大秦 为你打开 题目传送门
题目翻译
军队要开始演习了。有 $N$ 名队员，从 $0$ 到 $N-1$ 编号。现在要将队员分成红队和蓝队。它们中有 $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
| #include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128 int128;
namespace FastIO
{
template<typename T> inline T read(T& x) {
x = 0;
int f = 1;
char ch;
while (!isdigit(ch = getchar())) if (ch == '-') f = -1;
while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
x *= f;
return x;
}
template<typename T, typename... Args> inline void read(T& x, Args &...x_) {
read(x);
read(x_...);
return;
}
inline ll read() {
ll x;
read(x);
return x;
}
};
using namespace FastIO;
const int N = 210;
const int M = 40010;
class Graph {
private :
struct Edge {
int to, nt, wt;
Edge() {}
Edge(int to, int nt, int wt) : to(to), nt(nt), wt(wt) {}
}e[M];
int hd[N], cnte;
public :
inline void AddEdge(int u, int v, int w = 0) {
e[++cnte] = Edge(v, hd[u], w);
hd[u] = cnte;
}
inline int head(int u) { return hd[u]; }
inline int nt(int u) { return e[u].nt; }
inline int to(int u) { return e[u].to; }
inline int wt(int u) { return e[u].wt; }
};
int n, m;
int gp[210];
Graph G;
vector<int >v;
int ma[210], vis[210];
void Input() {
scanf("%d%d", &n, &m);
for(int i = 1; i <= n; i++) {
scanf("%d", &gp[i]);
}
int u, v;
for(int i = 1; i <= m; i++) {
scanf("%d%d", &u, &v);
u++, v++;
if(gp[u] != gp[v]) {
G.AddEdge(u, v);
G.AddEdge(v, u);
}
}
}
int Dfs(int u) {
for(int i = G.head(u); i; i = G.nt(i)) {
int v = G.to(i);
if(!vis[v] && gp[v]) {
vis[v] = 1;
if(!ma[v] || Dfs(ma[v])) {
ma[v] = u;
return 1;
}
}
}
return 0;
}
int Match() {
int cnt = 0;
memset(ma, 0, sizeof (ma));
for(int u = 1; u <= n; u++) {
memset(vis, 0, sizeof(vis));
if(!gp[u] && Dfs(u)) {
cnt++;
}
}
return cnt;
}
void Work() {
int ans = Match();
for(int i = 1; i <= n; i++) {
gp[i] = gp[i] ^ 1;
int tmp = Match();
if(tmp < ans) {
ans = tmp;
v.push_back(i);
}
else {
gp[i] = gp[i] ^ 1;
}
}
printf("%d ", v.size());
for(auto &p : v){
printf("%d ", p - 1);
}
}
int main() {
Input();
Work();
return 0;
}
|
