Day1:A+组

【元素】
题意:将n个整数分组,使组数最少且元素最多的组的元素个数尽量少。
数据范围给出提示,n<=15,符合这个范围的算法有深搜、状压DP。这里考虑深搜,枚举组数N,对于每一个数枚举其所在的组。时间复杂度为O(刚好能过)。
状压DP时间复杂度较为严谨,为O(2 ^ n * n ^ 2)。 令f[i]为状态i时最少需要的组数,对于两个状态opt、nav。若能合并,则f[opt ^ nav] = min(f[opt], f[nav])。若不能合并,则需讨论。

【反击】
题意:在n个数中找出最多满足条件的完美对数。
n <= 1000,可以暴力判断每两个数是否能符合条件,由于不能重复选取,联想到二分图。二分图求最大匹配方法有许多,这里使用网络流求二分图。将每个点拆成两点,每个点与另一边能与自己匹配的点连一条流量上限为1的边。源点s与一半的点连边,流量上限为正无穷。汇点t与另一半的点连边,流量上限为正无穷。
时间复杂度为O(nlogn).

【最小】
题意:将n点m边图中的点分为白点和黑点。 删除一些边,使剩下的边代价尽量小,且白点与最近的黑点仍按原先的最短路连接。
答案要求按最短路连接,于是先删除不在最短路上的边,再求最小生成树。最短路用spfa求解,由于有多个源点,先将所有黑点入队再求最短路。删边后只需满足白点与黑点由最短路连接,因此可能出现删边后成为森林的现象,在求最小生成树是将所有黑点先行合并。

主要代码如下

【元素】


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void dfs(int t)  {
    if (t > n)  {
        Max = 0;
        for (int i = 1;i <= Num; i++) Max = max(Max, Nec[i][0]);
        if (AnsN > Num)  {  AnsN = Num, AnsM = Max; }
        if (AnsN == Num) {  AnsM = min(AnsM, Max);  }
        return ;
    }
    for (int i = 1;i <= Num + 1; i++)  
        if (!fp(i, t))  {
            Num += (Nec[i][0] == 0);
            Nec[i][++Nec[i][0]] = t;
            LM = Max;
            Max = max(Max, Nec[i][0]);
            dfs(t + 1);
            Nec[i][0]--;
            Num -= (Nec[i][0] == 0);
            Max = LM;
        }
}

【反击】


1
2
3
4
5
6
7
8
9
10
    s = 2 * n + 1;
    t = s + 1;
    for (int i = 1;i <= n; i++)  {
       add(s, i, 1);
       add(i + n, t, 1);
    }
    for (int i = 1;i <= n; i++)  
       for (int j = n + 1;j <= 2 * n; j++)  
           if (fp(p[i], p[j]))
            add(i, j, 1);

【最小】

spfa:


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
void spfa()  {
    int nxt, now;
    while (!q.empty())  {
        for (int e = End[now = q.front()]; e ; e = p[e].next)  
            if (dir[nxt = p[e].gt] > dir[now] + p[e].val)  {
                dir[nxt] = dir[now] + p[e].val;
                LstE[nxt] = e;
                LstV[nxt] = now;
                if (!vis[nxt])  {
                    q.push(nxt);
                    vis[nxt] ^= 1;
                }
            }
        q.pop();
        vis[now] ^= 1;
    }
}

kruskal:


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void kk()  {
    int Num = 0;
    long long ans = 0;
    m *= 2;
    sort(p + 1, p + 1 + m);
    for (int i = 1; p[i].Vi; i++)  {
        if (gf(p[i].bg) != gf(p[i].gt))   {
            tg(p[i].bg, p[i].gt);
            ans += p[i].val;
            Num ++;
        }
    }
    if (ans) cout << ans;
    else printf("impossible");
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注