Untitled

 avatar
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