这个题本地测试样例会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,只不过单纯问一个问题不用看题)