本地测很稳,交上去全RE
  • 板块P1347 排序
  • 楼主SZbr
  • 当前回复7
  • 已保存回复7
  • 发布时间2021/9/1 20:48
  • 上次更新2023/11/4 08:10:42
查看原帖
本地测很稳,交上去全RE
230738
SZbr楼主2021/9/1 20:48

我把第一个测试点下载下来了,本地测也过了,但是一交全RE有没有大佬帮忙看看

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<vector>
#pragma warning(disable:4996)
using namespace std;
int n, m, f[300], sizef[300], fls, tot, head[300], in[300];
bool vis[300], vist[300];
bool flag = false;
vector<int> vc;
struct node
{
	int v, nt;
}edge[6010];
int find(int x) {
	if (f[x] == x) return x;
	else return f[x] = find(f[x]);
}
void build(int x, int y) {
	int xx = find(x), yy = find(y);
	if (xx != yy) {
		f[xx] = yy;
	}
}
void add(int u, int v) {
	edge[++tot].v = v;
	edge[tot].nt = head[u];
	head[u] = tot;
	in[v]++;
}
bool dfs(int x) {
	for (int i = head[x]; i; i = edge[i].nt) {
		//cout << edge[i].v << " " << vis[edge[i].v] << endl;
		if (vis[edge[i].v]) {
			return true;
		}
		if (!vist[edge[i].v]) {
			vist[edge[i].v] = true;
			vis[edge[i].v] = true;
			if (dfs(edge[i].v)) {
				return true;
			}
			vis[edge[i].v] = false;
		}
	}
	return false;
}
void vec(int x) {
	vis[x] = true;
	for (int i = head[x]; i; i = edge[i].nt) {
		bool pd = false;
		if (vis[edge[i].v]) continue;
		for (vector<int>::iterator it = vc.begin(); it != vc.end(); ++it) {
			if (*it == edge[i].v) {
				pd = true;
				break;
			}
		}
		if (pd) continue;
		vector<int>::iterator it;
		int j;
		for (j = 0; j < vc.size(); ++j) {
			if (vc[j] == x) {
				++j;
				vc.insert(vc.begin() + j, edge[i].v);
				break;
			}
		}
		//vc.push_back(edge[i].v);
		vec(edge[i].v);
	}
}
int main() {
	scanf("%d%d", &n, &m);
	char a, b, c;
	for (int i = 0; i <= 26; ++i) {
		f[i] = i;
	}
	for (int i = 1; i <= m; ++i) {
		memset(sizef, 0, sizeof(sizef));
		memset(vis, false, sizeof(vis));
		memset(vist, false, sizeof(vist));
		scanf("%c", &a);
		scanf("%c%c%c", &a, &b, &c);
		int at = a - 'A';
		int ct = c - 'A';
		build(at, ct);
		if (b == '>') add(ct, at);
		else add(at, ct);
		for (int j = 0; j < 26; ++j) {
			if (!vist[j]) {
				vis[j] = true;
				vist[j] = true;
				if (dfs(j)) {
					printf("Inconsistency found after %d relations.", i);
					return 0;
				}
				vis[j] = false;
			}
		}
		if (flag) continue;
		memset(vis, 0, sizeof(vis));
		for (int j = 0; j < 26; ++j) {
			if (!in[j] && head[j]) {
				vc.push_back(j);
				vec(j);
				break;
			}
		}
		if (vc.size() == n) {
			flag = true;
			fls = i;
		}
		else {
			while (vc.size()) {
				vc.pop_back();
			}
		}
	}
	if (vc.size() != n) {
		printf("Sorted sequence cannot be determined.");
		return 0;
	}
	else {
		printf("Sorted sequence determined after %d relations: ", fls);
		for (vector<int>::iterator it = vc.begin(); it != vc.end(); ++it) {
			printf("%c", 'A' + *it);
		}
		printf(".");
	}
	return 0;
}

思路挺简单就是代码有点复杂

2021/9/1 20:48
加载中...