codeforces Kitchen Plates (拓扑或者暴力)
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;
}