46pts 求调
查看原帖
46pts 求调
363317
Nicrobot楼主2023/8/14 13:24

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;
}
2023/8/14 13:24
加载中...