玄关 100分但却RE(在线等)
  • 板块P1347 排序
  • 楼主TLE_MLE_RE
  • 当前回复5
  • 已保存回复5
  • 发布时间2024/7/7 14:25
  • 上次更新2024/7/7 16:29:05
查看原帖
玄关 100分但却RE(在线等)
1110359
TLE_MLE_RE楼主2024/7/7 14:25

CodeCode

#include<bits/stdc++.h>
using namespace std;
int n, m; // n表示顶点数(字母数量),m表示边数(关系数量)
int graph[10010][10010]; // 邻接矩阵存储有向图,graph[i][j]=1表示i->j存在依赖
int degree[10010]; // 入度数组,记录每个顶点的入度
int now[10010]; // 当前处理时各顶点的入度(动态更新)
bool b[10010]; // 标记数组,b[i]=1表示顶点i已被加入序列
string ans; // 存储排序结果的字符串
// top函数——拓扑排序并返回排序状态
int top(){
    ans = ""; // 清空上一轮排序结果
    int f = 1; // f标记是否为唯一排序(f=1为唯一)
    for(int i=1; i<=n; i++){ // 初始化
        now[i] = degree[i];
        b[i] = 0;
    }
    for(int o=0; o<n; o++){
        int cnt = 0, minpos;
        for(int i=1; i<=n; i++) //寻找入度为0的节点
            if(b[i]==0 && now[i]==0) cnt++, minpos=i;
        if(cnt == 0) return -1; // 存在环,无法排序
        if(cnt >= 2) f = 0; // 不是唯一排序
        ans += minpos+64; // 将字符加入结果
        b[minpos] = 1; // 标记该顶点已处理
        for(int j=1; j<=n; j++) // 更新相关顶点的入度
            if(graph[minpos][j] == 1)
                now[j]--;
    }
    return f; // 返回排序状态
}

int main(){
    cin >> n >> m; // 输入顶点数和边数
    getchar();
    for(int i=1; i<=26; i++){// 初始化图和入度数组
        for(int j=1; j<=26; j++)
            graph[i][j] = 0;
        degree[i] = 0;
    }
    int flag = 0; // 标记是否已找到答案或矛盾
    for(int i=1; i<=m; i++){
        string tmp;
        getchar(); // 消耗换行符
        cin >> tmp; // 读取依赖关系
        char t1 = tmp[0] - 64, t2 = tmp[tmp.size()-1] - 64; // 转换为顶点编号
        if(graph[t1][t2] == 0) degree[t2]++; // 更新入度
        graph[t1][t2] = 1; // 添加依赖关系
        int p = top(); // 进行拓扑排序
        if(flag == 0){ // 如果还没有找到答案或矛盾
            if(p == 1){
                printf("Sorted sequence determined after %d relations: ",i);
                cout << ans << ".\n"; //直接输出排序结果(我是傻逼,我就不放在printf)
                flag = 1;
            }else if(p == -1){
                printf("Inconsistency found after %d relations.\n",i); //有环
                flag = 1;
            }
        }
    }
    if(!flag) printf("Sorted sequence cannot be determined.\n");//全else时就是无法排序
}

是100分但是RE了一个点。。。

zhangzheyang

2024/7/7 14:25
加载中...