欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

codeforces Kitchen Plates (拓扑或者暴力)

程序员文章站 2024-03-13 23:34:46
...

http://codeforces.com/gym/102219/problem/J

Kitchen Plates

time limit per test

1.0 s

memory limit per test

256 MB

input

standard input

output

standard output

You are given 5 different sizes of kitchen plates. Each plate is marked with a letter AA, BB, CC, DD, or EE. You are given 5 statements comparing two different plates, you need to rearrange the plates from smallest size to biggest size. For example: the sizes of these plates.

 

Input

The input consist of 5 lines. In each line there will be 3 characters, the first and last character will be either AA, BB, CC, DD, or EE and the middle character will be either >> or << describing the comparison between two plates sizes. No two plates will be equal.

Output

The output consist of 55 characters, the sorted order of balls from smallest to biggest plate. Otherwise, if the statements are contradicting print impossibleimpossible. If there are multiple answers, print any of them.

Examples

input

Copy

D>B
A>D
E<C
A>B
B>C

output

Copy

ECBDA

input

Copy

B>E
A>B
E>A
C<B
D<B

output

Copy

impossible

这题写了半天拓扑,别人用next_permutation( ) 暴力十分钟写出来了

心拔凉拔凉的

关于拓扑排序:https://blog.csdn.net/qq_41431457/article/details/89787036

#include<bits/stdc++.h>
using namespace std;

map<char,int> M;
bool vis[6], dir[6][6];
int in[6];
vector<int>  V;
char f[5] = {'A', 'B','C','D','E'};
priority_queue<int,vector<int>,greater<int> > Q;
void toposort()
{
	for(int i=0;i<5;i++)//将所有入度为0的顶点放入序列 
	if(in[i] == 0 ) Q.push(i);
//	cout << Q.size() <<endl;
	while(!Q.empty())
	{
		int x=Q.top(); Q.pop();
		V.push_back(x);
		
		for(int i=0;i<5;i++)//删除所有与x顶点有关的边 
		if(dir[x][i])
		{
			in[i]--;//邻接点入度减一 
			if(!in[i])
			Q.push(i);
		}
	}
}

int main()
{
	M['A'] = 0;
	M['B'] = 1;
	M['C'] = 2;
	M['D'] = 3;
	M['E'] = 4;
	
	int k = 5;
	while(k -- )
	{
		char a,b,c;
		cin >> a >> b >> c;
		if(b == '<') swap(a,c);
		
		in[M[c]]++;
		
		dir[M[a]][M[c]] = vis[M[a]] = vis[M[c]] = true;
	}
	
	toposort();
	
	if(V.size() < 5) 
	{
		cout << "impossible" << endl;
		return 0;
	}
	
	for(int i = 4; i >= 0; i--)
	cout << f[V[i]];
	cout<<endl;
	
	return 0;
}

 

相关标签: 拓扑