求助,总是 re 两个点。
#include <bits/stdc++.h>
#define rep(i, f, t) for(int i(f); i <= t; ++i)
#define re(i, t) for(int i(1); i <= t; ++i)
#define per(i, t, f) for(int i(t); i >= f; --i)
#define pe(i, t) for(int i(t); i >= 1; --i)
#define ste(i, f, t, s) for(int i(f); i <= t; i += s)
#define ets(i, t, f, s) for(int i(t); i >= f; i -= s)
#define each(i, x) for(auto &i : (x))
#define nx(i, u) for(int i(head[u]); i; i = e[i].next)
typedef long long ll;
typedef long double lb;
// #define int long long
using namespace std;
#define inf 0x3f3f3f3f
const int N = 1e4+3;
int n, m, st, ed, u, v;
ll w;
struct edge {
int to, next;
int val;
}e[2000020];
int head[N], cnt = 1;
void add (int u, int v, int w) {
e[++cnt] = (edge){v, head[u], w};
head[u] = cnt;
}
int gap[N], h[N], vis[N], surp[N];
struct cmp {
bool operator ()(int xi, int yi) const {
return h[xi] < h[yi];
}
};
priority_queue<int, vector<int>, cmp> pq;
queue<int>q;
bool bfs () {
fill(h+1, h+n+1, inf);
h[ed] = 0;
q.push(ed);
while(!q.empty()) {
int u = q.front(); q.pop();
nx(i, u) {
int v = e[i].to;
if((e[i ^ 1].val) && h[v] > h[u] + 1) {
h[v] = h[u] + 1;
q.push(v);
}
}
}
return h[st] ^ inf;
}
void push (int u) {
nx(i, u) {
int v = e[i].to;
if((e[i].val) && (h[v] + 1 == h[u])) {
int sur = min(e[i].val, surp[u]);
e[i].val -= sur;
e[i ^ 1].val += sur;
surp[u] -= sur;
surp[v] += sur;
if((v ^ st) && (v ^ ed) && (!vis[v])) {
pq.push(v);
vis[v] = 1;
}
if(!surp[u]) return ;
}
}
}
void relabel (int u) {
h[u] = inf;
nx(i, u) {
int v = e[i].to;
if(e[i].val && h[v] + 1 < h[u]) h[u] = h[v] + 1;
}
}
int hlpp () {
if(!bfs()) return 0;
h[st] = n;
fill(gap+1, gap+n+1, 0);
re(i, n) if(h[i] ^ inf) ++gap[h[i]];
nx(i, st) {
int v = e[i].to;
if(int sur = e[i].val) {
e[i].val -= sur, e[i ^ 1].val += sur;
surp[st] -= sur;
surp[v] += sur;
if((v ^ st) && (v ^ ed) && (!vis[v])) {
pq.push(v);
vis[v] = 1;
}
}
}
while(!pq.empty()) {
int u = pq.top(); pq.pop();
vis[u] = 0;
push(u);
if(surp[u]) {
gap[h[u]]--;
if(!gap[h[u]]) {
re(v, n) {
if((v ^ st) && (v ^ ed) && (h[v] > h[u]) && (h[v] < n+1))
h[v] = n+1;
}
}
relabel(u); ++gap[h[u]];
pq.push(u); vis[u] = 1;
}
}
return surp[ed];
}
signed main () {
cin >> n >> m;
ed = 520;
re(i, n) {
cin >> w;
if(w) add(st, i, 1), add(i, st, 0);
else add(i, ed, 1), add(ed, i, 0);
}
re(i, m) {
cin >> u >> v;
add(u, v, 1), add(v, u, 0);
add(v, u, 1), add(u, v, 0);
}
cout << hlpp();
return 0;
}