令人无法理解的问题
  • 板块学术版
  • 楼主ker_xyxyxyx_xxs
  • 当前回复9
  • 已保存回复9
  • 发布时间2021/7/23 15:31
  • 上次更新2023/11/4 13:34:00
查看原帖
令人无法理解的问题
335477
ker_xyxyxyx_xxs楼主2021/7/23 15:31

这个题本地测试样例会RE,但是交上去直接AC。 如果在程序中输出任意数值,也不会RE,可以正常运行并且AC,但是没有更改任何东西只是输出了一个数就可以不RE,这是为什么??? 代码如下:

# include <iostream>
# include <cstdio>
# include <cstring>
# include <queue>
# include <algorithm>
# include <cstring>
using namespace std;
const int maxm = 1e5 + 5;
const int maxn = 100 + 5;
const int inf = 0x3f3f3f3f;
string s;
int n , a1 , a2 , an , b1 , b2 , bn;
typedef struct {
	int x , y , z , next;
} Edge;
Edge edge[maxm];
int E , elast[maxm];
int mark[maxn][maxn];
int cur[maxm];
int S , T;
void add_edge(int x , int y , int z) {
	E ++;
	edge[E].x = x;
	edge[E].y = y;
	edge[E].z = z;
	edge[E].next = elast[x];
	elast[x] = E;
}
int dis[maxm] , cnt[maxm];
void bfs(int start) {
	dis[start] = 0;
	queue<int> q;
	q.push(start);
	while (!q.empty()) {
		int cur = q.front();
		q.pop();
		for (int i = elast[i] ; i ; i = edge[i].next) {
			int v = edge[i].y;
			if (dis[v]) continue;
			q.push(v);
			dis[v] = dis[cur] + 1;
			cnt[dis[v]] ++;
		}
	}
}

int dfs(int u , int flow) {
	int delta;
	if (u == T) return flow;
	delta = 0;
	for (int i = cur[u] ; i ; i = edge[i].next) {
		int v = edge[i].y;
		cur[u] = i;
		if (dis[u] == dis[v] + 1) {
			int temp = dfs(v , min(flow - delta , edge[i].z));
			edge[i].z -= temp;
			edge[i ^ 1].z += temp;
			delta += temp;
			if (delta == flow) return delta;
		}
	}
	cur[u] = elast[u];
	if (-- cnt[dis[u]] == 0) dis[S] = T;
	cnt[++ dis[u]] ++;
	return delta;

}
int Isap() {
	int ans = 0;
	memset(cnt , 0 , sizeof cnt);
	memset(dis , 0 , sizeof dis);
	
	bfs(T);
	
	for (int i = 1 ; i <= T ; i ++) {
		cur[i] = elast[i];
	}
	while (dis[S] < T) {
		ans += dfs(S , inf);
	}
	
	//cerr << "ak" << endl;
	return ans;
}
bool check(int a1 , int a2 , int an , int b1 , int b2 , int bn) {
	memset(elast , 0 , sizeof elast);
	E = 1;
	for (int i = 1 ; i <= n ; i ++) {
		for (int j = 1 ; j <= n ; j ++) {
			if (mark[i][j] == 1) {
				add_edge(i , j , inf);
				add_edge(j , i , 0);
			}
			if (mark[i][j] == 2) {
				add_edge(i , j , 1);
				add_edge(j , i , 0);
			}
		}
	}
	add_edge(S , a1 , an);
	add_edge(a1 , S , 0);
	add_edge(S , b1 , bn);
	add_edge(b1 , S , 0);
	add_edge(a2 , T , an);
	add_edge(T , a2 , 0);
	add_edge(b2 , T , bn);
	add_edge(T , b2 , 0);
	int cnt = Isap();
	if (cnt == an + bn) return true;
	else return false;
}

int main() {
	while (scanf("%d%d%d%d%d%d%d" , &n , &a1 , &a2 , &an , &b1 , &b2 , &bn) != EOF) {
		a1 ++;
		a2 ++;
		b1 ++;
		b2 ++;
		for (int i = 1 ; i <= n ; i ++) {
			cin >> s;
			for (int j = 0 ; j < n ; j ++) {
				if (s[j] == 'X') {
					mark[i][j + 1] = 0;
				}
				if (s[j] == 'N') {
					mark[i][j + 1] = 1;
				}
				if (s[j] == 'O') {
					mark[i][j + 1] = 2;
				}
			}
		}

		S = n + 1;
		T = n + 2;

		if (check(a1 , a2 , an , b1 , b2 , bn) && check(a2 , a1 , an , b1 , b2 , bn)) {
			printf("Yes\n");
		} else {
			printf("No\n");
		}
	}
	return 0;
}

(题目是3163,只不过单纯问一个问题不用看题)

2021/7/23 15:31
加载中...