蒟蒻dicnic全wa求助
查看原帖
蒟蒻dicnic全wa求助
747916
jingyu0929楼主2023/4/13 10:29

在ACwing上面点都过了,但复制过来全wa,求助一下这个输出是不是有什么要求(

提交记录

#include<bits/stdc++.h>
#define kg putchar(' ')
#define ch puts(" ")
using namespace std;
const int N = 1e2 + 5,M = 3e4 + 5, inf = 0x3f3f3f3f;

int n,m,S,T;
int h[N],e[M],f[M],ne[M],idx;
int cur[N],de[N];

int fr(){//快读
}

void fw(lwl x){//快写
}

void add(int a,int b,int w) {
	e[idx] = b,f[idx] = w,ne[idx] = h[a],h[a] = idx ++;
	e[idx] = a,f[idx] = 0,ne[idx] = h[b],h[b] = idx ++;
}

int dfs(int u,int limit) {
	if (u == T) {
		return limit;
	}
	int flow = 0;
	for (int i = cur[u]; ~ i && flow < limit; i = ne[i]) {
		cur[u] = i;
		int v = e[i];
		if (de[v] == de[u] + 1 && f[i]) {
			int t = dfs(v,min(f[i],limit - flow));
			if (!t) de[v] = -1;
			flow += t;
			f[i] -= t,f[i ^ 1] += t;
		}
	}
	return flow;
}

bool bfs() {
	queue<int> q;
	memset(de,-1,sizeof de);
	q.push(S);
	de[S] = 0,cur[S] = h[S];
	
	while (q.size()) {
		auto u = q.front();
		q.pop();
		
		for (int i = h[u]; ~ i; i = ne[i]) {
			int v = e[i];
			if (de[v] == -1 && f[i]) {
				de[v] = de[u] + 1;
				cur[v] = h[v];
				if (v == T) return true;
				q.push(v);
			}
		}
	}
	
	return false;
}

int dinic() {
	int ans = 0,flow;
	while (bfs()) {
		while (flow = dfs(S,inf),flow) {
			ans += flow;
		}
	}
	return ans;
}

int main(){
	m = fr(),n = fr();
	S = 0,T = n + 1;
	memset(h,-1,sizeof h);
	for (int i = 1; i <= m; i ++) {
		add(S,i,1);
	}
	for (int i = m + 1; i <= n; i ++) {
		add(i,T,1);
	}
	int a,b;
	while (1) {
		a = fr(), b = fr();
		if (a == -1) break;
		add(a,b,1);
	}
	
	int ans = dinic();
	fw(ans);
	ch;
	for (int i = 0; i < idx; i += 2) {
		if (e[i] > m && e[i] <= n && !f[i]) {
			fw(e[i ^ 1]),kg,fw(e[i]);
			ch;
		}
	}
	return 0;
}
2023/4/13 10:29
加载中...