Untitled
unknown
plain_text
a year ago
2.4 kB
4
Indexable
#include <iostream> #include <algorithm> #include <vector> using namespace std; vector<string> v[11]; string t[11]; char aft[11][11]; int dp[1111][11] , p[1111][11] , g[11][11]; int check(int k , int k1 , vector<string> a , vector<string> b){ int ok = 0 , ok1 = 0; for(int i = 2; i < a.size(); i++){ if(a[i] == b[0]) ok = 1; } for(int i = 2; i < b.size(); i++){ if(b[i] == a[0]) ok1 = 1; } if(a[0] == b[0]) ok = 1 , ok1 = 1; if(ok == 0 || ok1 == 0) return 0; for(int i = 0; i < a[1].size(); i++){ for(int j = 0; j < b[1].size(); j++){ if(a[1][i] == b[1][j]) { aft[k][k1] = a[1][i]; return 1; } } } return 0; } int main(){ string per; int cnt = 0; while(getline(cin , per)){ cnt++; if(cnt > 1) cout << "\n"; t[0] = per; int n = 10; for(int i = 1; i < n; i++) getline(cin, t[i]); for(int i = 0; i < n; i++){ v[i].clear(); string s = t[i], nw = ""; s += " "; for(int j = 0; j < s.size(); j++){ if(s[j] == ' '){ v[i].push_back(nw); nw = ""; } else { nw += s[j]; } } } int ans = 0; for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ g[i][j] = 0; if(i == j) continue; g[i][j] = check(i,j,v[i],v[j]); } } for(int i = 0; i < (1 << n); i++){ for(int j = 0; j < n; j++){ dp[i][j] = p[i][j] = 0; } } dp[1][0] = 1; for(int mask = 1; mask < (1 << n); mask++){ for(int i = 0; i < n; i++){ if((mask >> i) & 1){ int nw = (mask^(1 << i)); for(int j = 0; j < n; j++){ if((nw >> j) & 1){ if(g[j][i] == 1 && dp[nw][j]){ p[mask][i] = j; dp[mask][i] = 1; } } } } } } for(int i = 1; i < n; i++){ if(g[i][0] == 1 && dp[(1 << n)-1][i]){ int cur = i , mask = (1 << n)-1; vector<int> ord; while(mask > 0){ ord.push_back(cur); int nwmask = mask-(1 << cur); cur = p[mask][cur]; mask = nwmask; } reverse(ord.begin() , ord.end()); ans = 1; for(int i = 0; i < n; i++){ cout << i+1 <<" " << aft[ord[(i-1+n)%n]][ord[i]] <<" " << v[ord[i]][0] <<" " << aft[ord[i]][ord[(i+1)%n]]; if(i < n-1)cout << "\n"; } break; } } if(ans == 0){ cout << "NO SOLUTION EXISTS"; } } return 0; }
Editor is loading...
Leave a Comment