RT。
已经过了 P1345,显示 Wrong Answer.wrong answer Your solution is not so good.
#include <bits/stdc++.h>
using namespace std;
const int N = 20005, M = 200005;
const int inf = 1e9;
int n, m, s, t;
int head[M], nxt[M], to[M], edge[M], tot = 1;
int d[N], now[N];
void add(int u, int v, int w) {
// cout << u << ' ' << v << ' ' << w << '\n';
to[++tot] = v, edge[tot] = w, nxt[tot] = head[u], head[u] = tot;
to[++tot] = u, edge[tot] = 0, nxt[tot] = head[v], head[v] = tot;
}
bool bfs() {
memset(d, 0, sizeof(d));
queue<int> q;
q.push(s);
now[s] = head[s];
d[s] = 1;
while (!q.empty()) {
int x = q.front();
q.pop();
for (int i = head[x]; i; i = nxt[i]) {
int y = to[i];
if (!d[y] && edge[i]) {
d[y] = d[x] + 1;
now[y] = head[y];
if (y == t) return 1;
q.push(y);
}
}
}
return 0;
}
int dinic(int x, int flow) {
if (x == t) return flow;
int rest = flow;
for (int i = now[x]; i && rest; i = nxt[i]) {
now[x] = i;
int y = to[i];
if (edge[i] && d[y] == d[x] + 1) {
int k = dinic(y, min(edge[i], rest));
if (k == 0) now[y] = 0;
edge[i] -= k;
edge[i ^ 1] += k;
rest -= k;
}
}
return flow - rest;
}
int main() {
cin >> n >> m >> s >> t;
t += n;
for (int i = 1; i <= n; i++) {
int d; cin >> d;
add(i, i + n, d);
}
for (int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v;
add(u + n, v, inf);
add(v + n, u, inf);
}
// for (int i = 1; i <= n; i++) add(i, i + n, 1);
long long maxflow = 0, flow;
while (bfs()) {
// cout << 1 << '\n';
while (flow = dinic(s, inf)) maxflow += flow;
}
// cout << maxflow;
vector<int> ans;
for (int i = 2; i <= n * 2; i += 2) {
// cout << to[i ^ 1] << '\n';
if (edge[i ^ 1] && !edge[i]) ans.push_back(to[i ^ 1]);
}
sort(ans.begin(), ans.end());
for (int i : ans) cout << i << ' ';
return 0;
}