EK WA 72pts 求调
查看原帖
EK WA 72pts 求调
694172
Dawn_chen楼主2023/9/7 13:44

rt , 记录 ,题面。

#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
using namespace std;
#define int long long
#define N 10010

struct edge {
	int v, w, ne;
} a[N];

struct prep {
	int fr, ed;
} pre[N];

int n, m, idx = 1, s, t;
int hd[N], vis[N], with[N];

void add(int u, int v, int w) {
	a[ ++ idx].v = v; a[idx].w = w;
	a[idx].ne = hd[u]; hd[u] = idx;
}

bool bfs(int fr) {
	queue <int> q;
	memset(vis, 0, sizeof vis);
	memset(pre, -1, sizeof pre);
	vis[fr] = 1; q.push(fr);
	
	while( ! q.empty()) {
		int u = q.front(); q.pop();
		
		for(int i = hd[u]; i != 0; i = a[i].ne) {
			int v = a[i].v, w = a[i].w;
			if( ! vis[v] && w) {
				pre[v].ed = i; pre[v].fr = u; vis[v] = 1;
				if(v == t) return 1;
				q.push(v);
			}
		}
	}
	
	return 0;
}

int EK() {
	int ans = 0; 
	
	while(bfs(s)) {
		for(int i = t; i != s; i = pre[i].fr) {
			a[pre[i].ed].w -= 1;
			a[pre[i].ed ^ 1].w += 1;
			with[pre[i].fr] = i;
		}
		ans += 1;
	}
	
	return ans;
}

signed main() {
	ios::sync_with_stdio(false);
	cin >> m >> n; 
	s = 0; t = n + 1;
	for(int i = 1; i <= m; i ++) add(s, i, 1), add(i, s, 0);
	for(int i = m + 1; i <= n; i ++) add(i, t, 1), add(t, i, 0);
	int x, y;
	while(cin >> x >> y) {
		if(x == -1 && y == -1) break;
		cin >> x >> y;
		add(x, y, 1); add(y, x, 0);
	}
	cout << EK() << "\n";
	for(int i = 1; i <= n; i ++) {
		int u = i, v = with[i];
		if(v) {
			if(u > v) continue;
			if(u == s || v == s || u == t || v == t) continue;
			cout << u << " " << v << "\n";
		}
	}
	return 0;
}

个人原因不能及时回复请见谅。

2023/9/7 13:44
加载中...