排序——Topsort / Floyd 约束的各种判定

题目

Topsort法 （Topsort具有对约束的判定能力，解约束能力）

• 如何判定约束矛盾
  • 存在环 qcnt < n
• 如何判定约束不完全
  • 不存在环 且 队列存在时刻元素大于1个
• 如何判定约束完全
  • 队列任意时刻元素恒为1个

#include <bits/stdc++.h>
using namespace std;
const int N = 30;
int sq[N], in[N], qin[N];
int g[N][N];
int st[N];
int n, m;
int topsort(int cnt)
{
    int qcnt = 0;
    queue<int> q;
    memcpy(qin, in, sizeof in);
    
    for(int i = 1; i <= n; i++)
        if(!qin[i]) q.push(i);
        
    bool undef = false;
    while(q.size())
    {
        if(q.size() > 1) undef = true;
        int u = q.front(); q.pop(); sq[++qcnt] = u;
        
        for(int i = 1; i <= n; i++)
        {
            if(g[u][i])
                if(--qin[i] == 0)
                    q.push(i);
        }
    }

    if(qcnt < n) return 2; //约束矛盾
    if(undef) return 0; //部分约束
    return 1; //完全约束
    
    return 0;
}
int main()
{
    while(scanf("%d%d", &n, &m), n)
    {
        int type = 0, t, cnt = 0;
        memset(in, 0, sizeof in);
        memset(g, 0, sizeof g);
        memset(st, 0, sizeof st);
        for(int i = 1; i <= m; i++)
        {
            char str[5];
            scanf("%s", str);
            
            if(!type)
            {
                int a = str[0] - 'A' + 1;
                int b = str[2] - 'A' + 1;
                if(!st[a]) st[a] = true, cnt++;
                if(!st[b]) st[b] = true, cnt++;
                
                if(!g[a][b]) in[b]++;
                g[a][b] = 1;
                type = topsort(cnt);
                if(type) t = i;
            }
        }
        
        if(type == 0)
        {
            printf("Sorted sequence cannot be determined.\n");
        }
        else if(type == 1)
        {
            printf("Sorted sequence determined after %d relations: ", t);
            for(int i = 1; i <= n; i++)
                printf("%c", sq[i] + 'A' - 1);
            printf(".\n");
        }
        else
        {
            printf("Inconsistency found after %d relations.\n", t);
        }
    }
}

Floyd法 （Floyd具有求任意两点距离（关系）的能力）

#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
const int N = 30;
typedef pair<int, int> PII;
PII ans[N];
int g[N][N];
int n, m;
void floyd(int k)
{
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            g[i][j] |= g[i][k] & g[k][j];
        }
    }
}
bool check()
{
    for(int i = 1; i <= n; i++)
    {
        int cnt = 0;
        for(int j = 1; j <= n; j++)
            if(g[j][i]) cnt++;
        ans[i] = {cnt, i};
        
        for(int j = 1; j <= n; j++)
            if(i != j && g[i][j]) cnt++;

        if(cnt != n) return 0;
        
    }
    
    sort(ans+1, ans+n+1);
    
    return 1;
}

int main()
{
    while(scanf("%d%d", &n, &m), n)
    {
        memset(g, 0, sizeof g);
        for(int i = 1; i <= n; i++)
            g[i][i] = 1;
        int type = 0, t;
        for(int i = 1; i <= m; i++)
        {
            char str[5];
            scanf("%s", str);
            int a = str[0] - 'A' + 1;
            int b = str[2] - 'A' + 1;
            
            if(!type)
            {
                if(g[b][a]) type = 2, t = i;
                g[a][b] = 1;
                floyd(a); floyd(b);
                if(check()) type = 1, t = i;
            }
        }
        if(!type) printf("Sorted sequence cannot be determined.\n");
        else if(type == 1)
        {
            printf("Sorted sequence determined after %d relations: ", t);
            for(int i = 1; i <= n; i++)
                printf("%c", ans[i].y + 'A' - 1);
            printf(".\n");
        }
        else printf("Inconsistency found after %d relations.\n", t);
    }
}