ZOJ 3830 Alkanes 大模擬！！
題目鏈接：點擊打開鏈接
就是給了一個樹形的烷烴，輸出他的科學命名
然後寫寫寫。。。
==強行回憶高中化學
#include
#include
#include
#include
#include
#include
#include
#include
template
inline bool rd(T &ret) {
char c; int sgn;
if (c = getchar(), c == EOF) return 0;
while (c != '-' && (c<'0' || c>'9')) c = getchar();
sgn = (c == '-') ? -1 : 1;
ret = (c == '-') ? 0 : (c - '0');
while (c = getchar(), c >= '0'&&c <= '9') ret = ret * 10 + (c - '0');
ret *= sgn;
return 1;
}
template
inline void pt(T x) {
if (x <0) {
putchar('-');
x = -x;
}
if (x>9) pt(x / 10);
putchar(x % 10 + '0');
}
const int N = 50;
using namespace std;
string name[N] = { "ewrt", "meth", "eth", "prop", "but", "pent", "hex", "hept", "oct", "non", "dec", "undec", "dodec", "tridec", "tetradec", "pentadec" };
vectorG[N];
struct hehe{
int dis[N], pre[N], id, sum;
vectorD[N];
int dfs(int u, int fa){
int siz = 1;
for (int i = 0; i < G[u].size(); i++)
{
int v = G[u][i];
if (v != fa)
siz += dfs(v, u);
}
return siz;
}
int bfs(int s, int t){
memset(dis, -1, sizeof dis);
memset(pre, -1, sizeof pre);
dis[s] = 1;
queueq; q.push(s);
while (!q.empty()){
int u = q.front(); q.pop();
for (int i = 0; i < G[u].size(); i++)
{
int v = G[u][i];
if (dis[v] != -1)continue;
dis[v] = dis[u] + 1;
pre[v] = u;
q.push(v);
}
}
int last = -1, val = 0;
while (t != -1){
for (int i = 0; i < G[t].size(); i++)
{
int v = G[t][i];
if (v != last && v != pre[t]){
if (id == -1 || id > dis[t]) id = dis[t];
sum += dis[t];
D[dfs(v, t)].push_back(dis[t]);
}
}
last = t;
t = pre[t];
}
}
int T;
void work(int s, int t){
T = t;// printf(" %d->%d\n", s, t);
id = -1;
sum = 0;
for (int i = 0; i < N; i++)D[i].clear();
bfs(s, t);
for (int i = 0; i < N; i++)sort(D[i].begin(), D[i].end());
/* for(int i = 0; i 4){
cout << name[D[i].size()];
printf("a");
}
cout << name[i];
printf("yl");
}
cout << name[dis[T]];
puts("ane");
}
}b[2];
int dis[N], pre[N];
int bfs(int s, int t){
memset(dis, -1, sizeof dis);
memset(pre, -1, sizeof pre);
dis[s] = 0;
queueq; q.push(s);
while (!q.empty()){
int u = q.front(); q.pop();
for (int i = 0; i < G[u].size(); i++)
{
int v = G[u][i];
if (dis[v] != -1)continue;
dis[v] = dis[u] + 1;
pre[v] = u;
q.push(v);
}
}
int last = -1, val = 0;
while (t != -1){
for (int i = 0; i < G[t].size(); i++)
{
int v = G[t][i];
if (v != last && v != pre[t])val++;
}
last = t;
t = pre[t];
}
return val;
}
int n, m, len, a[2], siz;
void find_total(){
len = siz = 0;
for (int i = 1; i <= n; i++)
for (int j = i + 1; j <= n; j++)
{
int tmp = bfs(i, j);
if (dis[j] > len || (dis[j] == len && tmp > siz)){
len = dis[j]; a[0] = i; a[1] = j;
siz = tmp;
}
}
/// printf("%d->%d\n", a[0], a[1]);
}
void input(){
for (int i = 0; i < N; i++)G[i].clear();
int u, v;
while (m--){
scanf("%d %d", &u, &v);
G[u].push_back(v);
G[v].push_back(u);
}
}
int main() {
while (~scanf("%d %d", &n, &m)){
input();
find_total();
b[0].work(a[0], a[1]);
b[1].work(a[1], a[0]);
if (b[0].idb[1].id)
b[1].put();
else
{
if (b[0].sum < b[1].sum)
b[0].put();
else if(b[0].sum > b[1].sum)
b[1].put();
else
{
int id = -1;
for(int i = N-1; id==-1 && i >= 0; i--)
{
if(b[0].D[i].size()>b[1].D[i].size())
id = 0;
else if(b[0].D[i].size()b[1].D[i][j])
id = 1;
}
}
if(id==-1)id=0;
b[id].put();
}
}
// b[0].put(); b[1].put();
}
return 0;
}
/*
10 9
1 2
2 3
2 4
4 5
4 6
4 9
9 10
6 8
6 7
2,3,4-trimethyl-3-ethylpentane
10 9
1 2
2 5
2 6
2 3
3 7
3 8
3 4
8 9
8 10
12 11
1 2
2 5
2 6
2 3
3 7
7 11
3 8
3 4
8 9
8 10
7 12
14 13
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
2 10
8 11
4 13
13 14
6 12
14 13
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
3 10
7 11
4 13
10 14
6 12
*/
