QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#127626#898. 二分图最大匹配Ignotus#RE 0ms0kbC++142.0kb2023-07-19 20:55:332023-07-19 20:55:35

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-07-19 20:55:35]
  • 评测
  • 测评结果:RE
  • 用时:0ms
  • 内存:0kb
  • [2023-07-19 20:55:33]
  • 提交

answer

#include <bits/stdc++.h>

template <typename T>
void rd(T& x){
	x = 0; char c = getchar(); int f = 1;
	while(!isdigit(c)) f = c == '-' ? -1 : 1, c = getchar();
	while(isdigit(c)) x = x * 10 + c - '0', c = getchar();
	x *= f;
}
template <typename T, typename... Args>
void rd(T& x, Args&... args){rd(x); rd(args...);}
template <typename T>
void wt(T x, char ed){
	if(x < 0) putchar('-'), x = -x;
	static short st[20], tp;
	do st[++tp] = x % 10, x /= 10; while(x);
	while(tp) putchar(st[tp--] + '0');
	putchar(ed);
}

using ll = long long;
const int N = 1e4 + 10;
const ll INF = 0x3f3f3f3f3f3f3f3f;

int n1, n2, m, S, T;

struct edge{
	int u, v; ll w;
}e[N << 1];
int head[N], cnte = 1;

void adde(int u, int v, ll w){
	e[++cnte] = {head[u], v, w}, head[u] = cnte;
	e[++cnte] = {head[v], u, 0}, head[v] = cnte;
}

int dis[N], cur[N];
bool bfs(){
	memset(dis, 0, sizeof dis);
	std::queue <int> q;
	dis[S] = 1, q.push(S), cur[S] = head[S];
	while(q.size()){
		int x = q.front(); q.pop();
		for(int i = head[x]; i; i = e[i].u){
			int y = e[i].v;
			if(!dis[y] && e[i].w){
				dis[y] = dis[x] + 1, cur[y] = head[y];
				q.push(y);
			}
		}
	}
	return dis[T];
}
ll dfs(int x, ll lim){
	if(x == T || !lim) return lim;
	ll ret = 0;
	for(int i = cur[x], k; i && lim; i = e[i].u){
		int y = e[i].v;
		cur[x] = i;
		if(dis[y] == dis[x] + 1){
			k = dfs(y, std::min(lim, e[i].w));
			e[i].w -= k, e[i ^ 1].w += k, ret += k, lim -= k;
		}
	}
	return ret;
}

ll dinic(){
	ll flow = 0;
	while(bfs()) flow += dfs(S, INF);
	return flow;
}

int main(){
	rd(n1, n2, m);
	S = n1 + n2 + 1, T = n1 + n2 + 2;
	for(int i = 1, u, v; i <= m; ++i){
		rd(u, v), ++u, ++v;
		adde(u, v + n1, 1);
	}
	for(int i = 1; i <= n1; ++i) adde(S, i, 1);
	for(int i = 1; i <= n2; ++i) adde(i + n1, T, 1);
	int ans = dinic();
	wt(ans, '\n');
	for(int i = 1; i <= n1; ++i){
		for(int j = head[i]; j; j = e[j].u){
			int y = e[j].v;
			if(y > n1 && y <= n1 + n2 && !e[j].w) wt(i - 1, ' '), wt(y - n1 - 1, '\n');
		}
	}
	return 0;
}

详细

Test #1:

score: 0
Runtime Error

input:

100000 100000 200000
78474 45795
32144 46392
92549 13903
73460 34144
96460 92850
56318 77066
77529 84436
76342 51542
77506 99268
76410 89381
1778 61392
43607 96135
84268 74827
14857 35966
32084 94908
19876 174
1481 94390
12423 55019
64368 92587
81295 7902
25432 46032
36293 61128
73555 84836
8418 102...

output:


result: