#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize(4)
#include<bits/stdc++.h>
#define LL long long
#define LD long double
#define ull unsigned long long
#define fi first
#define se second
#define mk make_pair
#define PLL pair<LL, LL>
#define PLI pair<LL, int>
#define PII pair<int, int>
#define SZ(x) ((int)x.size())
#define ALL(x) (x).begin(), (x).end()
#define fio ios::sync_with_stdio(false); cin.tie(0);
using namespace std;
const int N =
5000 +
7;
const int inf =
0x3f3f3f3f;
const LL INF =
0x3f3f3f3f3f3f3f3f;
const int mod =
998244353;
const double eps = 1e-
8;
const double PI = acos(-
1);
template<
class T,
class S> inline
void add(T &a, S b) {a += b;
if(a >= mod) a -=
mod;}
template<
class T,
class S> inline
void sub(T &a, S b) {a -= b;
if(a <
0) a +=
mod;}
template<
class T,
class S> inline
bool chkmax(T &a, S b) {
return a < b ? a = b,
true :
false;}
template<
class T,
class S> inline
bool chkmin(T &a, S b) {
return a > b ? a = b,
true :
false;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<
int>
G[N];
vector<
int>
rG[N];
int L[N], totL;
int R[N], totR;
bool vis[N];
int matchL[N], matchR[N];
bool visL[N], visR[N];
vector<
int>
V;
int path(
int u) {
visL[u] =
true;
for(auto &
v : G[u]) {
if(!
visR[v]) {
visR[v] =
true;
if(matchR[v] ==
0 ||
path(matchR[v])) {
matchR[v] =
u;
matchL[u] =
v;
return 1;
}
}
}
return 0;
}
int main() {
int cnt =
0;
for(
int i =
1; i <= totL; i++
) {
memset(visL, 0,
sizeof(visL));
memset(visR, 0,
sizeof(visR));
if(path(i)) {
cnt++
;
}
}
cnt = n -
cnt;
memset(visL, 0,
sizeof(visL));
memset(visR, 0,
sizeof(visR));
for(
int i =
1; i <= totL; i++
) {
if(!
matchL[i]) {
path(i);
}
}
for(
int i =
1; i <= totL; i++
) {
if(visL[i]) {
V.push_back(L[i]);
}
}
for(
int i =
1; i <= totR; i++
) {
if(!
visR[i]) {
V.push_back(R[i]);
}
}
printf("%d\n", cnt);
for(
int i =
0; i < SZ(V); i++
) {
printf("%d%c", V[i],
" \n"[i == SZ(V) -
1]);
}
return 0;
}
/*
*/
转载于:https://www.cnblogs.com/CJLHY/p/11289578.html
相关资源：JAVA上百实例源码以及开源项目
