POJ-1270-Following Orders

浅浅的花香味﹌ 2021-12-24 05:05 85阅读 0赞

### 链接：[https://vjudge.net/problem/POJ-1270][https_vjudge.net_problem_POJ-1270] ###

### 题意： ###

给n个字符，同时给m个约束条件，求满足约束条件下的所有排列情况。

### 思路： ###

跟POJ1128很像。

按照约束建图。DFS跑一遍就行。

### 代码： ###

#include <iostream>
    #include <memory.h>
    #include <vector>
    #include <map>
    #include <algorithm>
    #include <cstdio>
    #include <math.h>
    #include <queue>
    #include <string>
    #include <stack>
    #include <iterator>
    #include <stdlib.h>
    #include <time.h>
    #include <assert.h>
    
    using namespace std;
    typedef long long LL;
    const int MAXN = 30 + 10;
    int Vis[MAXN];
    int in[MAXN];
    int M[MAXN][MAXN];
    char res[MAXN];
    int cnt;
    
    void DFS(int num)
    {
        if (num == cnt)
        {
            res[num] = '\0';
            cout << res << endl;
            return;
        }
    
        for (int i = 0;i < 26;i++)
        {
            if (in[i] == 0 && Vis[i] == 1)
            {
                in[i] = -1;
                for (int j = 0;j < 26;j++)
                    if (M[i][j])
                        --in[j];
                res[num] = 'a'+i;
                DFS(num+1);
                in[i] = 0;
                for (int j = 0;j < 26;j++)
                    if (M[i][j])
                        ++in[j];
            }
        }
    }
    
    int main()
    {
        string s;
        while (getline(cin, s))
        {
            cnt = 0;
            memset(in, 0, sizeof(in));
            memset(Vis, 0, sizeof(Vis));
            memset(M, 0, sizeof(M));
            for (int i = 0;i < s.length();i++)
                if (s[i] != ' ')
                    Vis[s[i]-'a'] = 1, ++cnt;
            getline(cin, s);
            for (int i = 0;i < s.length();)
            {
                int l = s[i]-'a';
                int r = s[i+2]-'a';
                i += 4;
                if (!M[l][r])
                    M[l][r] = 1;
                ++in[r];
            }
            DFS(0);
            cout << endl;
        }
    
        return 0;
    }

转载于:https://www.cnblogs.com/YDDDD/p/10724502.html

[https_vjudge.net_problem_POJ-1270]: https://vjudge.net/problem/POJ-1270