Home > Article > Web Front-end > SRM 638 Div2_html/css_WEB-ITnose
2333. .
Due to the small number of TC entries and the constant fst, I dropped it to div2.
Fortunately, I returned to div1 when I was done. .
250
Water question
500
Water question. .
Just expand bfs directly
Pay attention to the judgment, I also used Cantor to expand it, which is really unnecessary. .
1000
I misunderstood the meaning of this question. . I said it looked wrong when looking at other people’s code
But it’s still a very easy question
Binary enumeration of which leaf nodes to burn
Then for each burning method
Find the shortest path
After finding the shortest path, enumerate the edges
Assume that the two nodes of the edge are u, and the weight of v is w
Just find the maximum (dis[u] dis[v] w )/2 which is the time to burn out
Why is this?
Assume a certain side It is the last one to be burned. There are two situations
One is that u and v are both burned by fire from other nodes
One is that u is passed by v Burned by fire
For the first type, let’s assume dis[u] > dis[v]
The answer is ( L-(dis[u] - dis[v]) ) / 2 dis[u] = (dis[u] dis[v] L) / 2
Second type
dis[v] L = dis[u]
Then the same dis[u] = (dis[v] L dis[u]) / 2
Both can be expressed by this
Then for convenience we will not divide by 2
struct node { int v, w; node () {} node (int _v, int _w) {v = _v; w = _w;}};vector<node>g[22];int ind[22], lea[22], pos[22], d[22], vis[22], q[1111];set<int> s;class CandleTimerEasy{public: int differentTime(vector <int> A, vector <int> B, vector <int> len) { int n = A.size() + 1; for(int i = 0; i < n; i++) g[i].clear(); memset(ind, 0, sizeof(ind)); for(int i = 0; i < n - 1; i++) { g[A[i]].push_back(node(B[i], len[i])); g[B[i]].push_back(node(A[i], len[i])); ++ind[A[i]]; ++ind[B[i]]; } s.clear(); int cnt = 0; memset(pos, -1, sizeof(pos)); for(int i = 0; i < n; i++) { if(ind[i] == 1) { lea[cnt] = i; pos[i] = cnt; cnt++; } } for(int sta = 1; sta < (1 << cnt); sta ++) { int h = 0, t = 0; for(int i = 0; i < n; i++) { d[i] = INF; vis[i] = 0; if(pos[i] != -1) { if(sta & (1 << pos[i])) { q[t++] = i; d[i] = 0; vis[i] = 1; } } } while(h < t) { int u = q[h++]; vis[u] = 0; for(int i = 0; i < g[u].size(); i++) { int v = g[u][i].v; int w = g[u][i].w; if(d[u] + w < d[v]) { d[v] = d[u] + w; if(!vis[v]) { q[t++] = v; vis[v] = 1; } } } } int mx = 0; for(int i = 0; i < n - 1; i++) mx = max(mx, d[A[i]] + d[B[i]] + len[i]); s.insert(mx); } return (int)s.size(); }}