POJ-1270-Following Orders-白红宇

POJ-1270-Following Orders

阅读量：6787 次

发布时间：2019-06-26

本文共 1181 字，大约阅读时间需要 3 分钟。

链接：

题意：

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

思路：

跟POJ1128很像。

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

代码：

#include 
     
      #include 
      
       #include 
       
        #include 
        #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 
                  #include 
                  
                   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;}