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();    }}