SRM 638 Div2

2333.。。

因为TC过少的参与者。加上不断fst 我掉了div2该。

幸运的是完成的背div1该。。

250

水的问题

500

水的问题。。

直接bfs扩展即可了

注意判重。我还用康托展开了真是多此一举。。

1000

这题理解错题意了。。

我说看别人代码怎么看着不正确劲来着

只是还是很easy的一道题

二进制枚举烧哪些叶子结点

然后对每种烧法

求最短路

求完最短路，枚举边

如果边的两个结点是u,v权值为w

就求最大的(dis[u]+dis[v]+w )/2就是烧完的时间

为啥这样呢

如果某边是最后被烧掉的，有两种情况

一种是u,v分别都是由别的结点传来的火烧过来的

一种是u被v传来的火烧过来的

第一种。最好还是设dis[u] > dis[v]

答案就是( L-(dis[u] - dis[v]) ) / 2 + dis[u] = (dis[u] + dis[v] + L) / 2

另外一种

dis[v] + L = dis[u]

那么相同dis[u] = (dis[v] + L + dis[u]) / 2

二者都能够用这个表示了

然后为了方便我们就不除以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();

    }

}

相关文章