分组策略¶

例题 #1 利用组内元素关系分组集合分组¶

题目描述

现有 \(k\) 个整数集合，第 \(i\) 个集合有 \(s_i\) 个元素。

集合中的数都为正数，且不大于 \(n\)。现定义集合 \(A\) 与集合 \(B\) 相似，当且仅当满足如下条件之一：

\(B\) 与 \(A\) 相似；
将 \(A\) 集合删去一个元素，或更改一个元素的值之后 \(A\) 集合与 \(B\) 集合相等。

现要将 \(K\) 个集合分成至多 \(M\) 组（\(M>N\)），使得每一组内的集合互不相似。要求你给出一种合法的方案。如果无解请输出 impossible。

输入格式

输入文件第一行有三个数 \(n, k, m\)，意义如题目所述。

接下来有 \(k\) 行，每行第一数 \(s_i\) 表示序列长度。之后 \(s_i\) 个数为些集合的元素。

输出格式

如果存在合法方案，输出 \(k\) 个数，表示每个集合（按输入顺序）被分到的组的编号（\(1\sim m\)）。否则，若不存在合法方案则输出 impossible。

对于 \(30\%\) 的数据满足 \(n \le 10\)，\(m \le 2\)，\(k \le 10\)；
对于 \(100\%\) 的数据满足 \(1\le n \le 100\)，\(1\le m \le 100\)，\(1\le k \le 50000\)，\(1\le s_i \le 100\)。

发现同一组的集合元素的和的差值不超过n，于是按mod (n+1)分组即可。

例题 #2 二进制分组 [GXOI/GZOI2019] 旅行者¶

题目描述

J 国有 \(n\) 座城市，这些城市之间通过 \(m\) 条单向道路相连，已知每条道路的长度。

一次，居住在 J 国的 Rainbow 邀请 Vani 来作客。不过，作为一名资深的旅行者，Vani 只对 J 国的 \(k\) 座历史悠久、自然风景独特的城市感兴趣。为了提升旅行的体验，Vani 想要知道他感兴趣的城市之间「两两最短路」的最小值（即在他感兴趣的城市中，最近的一对的最短距离）。

也许下面的剧情你已经猜到了—— Vani 这几天还要忙着去其他地方游山玩水，就请你帮他解决这个问题吧。

思路

我们发现，如果单单是枚举关键点配对，时间复杂度就不行。并且我们要求的只是一个值，代表最小值，而不需要知道是哪两个关键点之间的路径。

于是我们就需要知道一个方法可以一次性求出多个关键点对之间的距离的最小值。那么我们可以学到把关键点划分为A,B两个集合，这样我们跑一次最短路就可以求出所有点对(u,v),u\in A,v\in B的最短路中的最小值了。

那么接下来我们考虑A集合中的点对和B集合中的点对。也许我们会考虑分治，但是注意，这里分治**并不能**缩小问题范围。举个例子，我们假设再把A分成A1,A2，那么我们求A1,A2之间的最短路的最小值，并不是只需要在G=A1+A2里面跑最短路就行了，而是还是要在全图中跑。这样我们分治到最后一层（或者接近最底层）就需要跑n次全图的最短路，这是不可接受的。

现在我们知道了每一次跑最短路都需要O(n\log n)，那么我们就也该考虑如何用最少的次数覆盖所有点对的情况。即我们要把点集划分成两个集合A,B，使得每一个点对(x,y)都至少有一次划分时两个点在不同集合中。

这时我们就要请出我们的**二进制分组**了。我们在二进制下诸位考虑每个数（即关键点的编号），如果这个数的当前位为1，我们把这个点放在一个集合，否则就放在另外一个集合。因为两个不同的数在二进制下必定有一位不一样，所以这样分组可以使得每两个数至少有一次被分在了不同的集合中。这样的分组次数是\log n的。

所以总的时间复杂度为O(n \log^2 n)

代码

#include <bits/stdc++.h>
#include <queue>
using namespace std;

#define rep(i, l, r) for (int i = l, END##i = r; i <= END##i; ++i)
#define per(i, r, l) for (int i = r, END##i = l; i >= END##i; --i)
#define pb push_back
#define mp make_pair
#define int long long
#define pii pair<int, int>
#define ps second
#define pf first

// #define innt int
// #define inr int
// #define mian main
// #define iont int

#define rd read()
int read(){
    int xx = 0, ff = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-')
            ff = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
      xx = xx * 10 + (ch - '0'), ch = getchar();
    return xx * ff;
}
void write(int out) {
    if (out < 0)
        putchar('-'), out = -out;
    if (out > 9)
        write(out / 10);
    putchar(out % 10 + '0');
}

// const bool enable_dbg = false;
// template <typename T,typename... Args>
// void dbg(bool flg,T s,Args... args) {
//  if constexpr (enable_dbg){
//      cout << s;
//      if constexpr (sizeof...(Args))
//          dbg(flg,args...);
//  }
// }

const int N = 3e5 + 5;
const int INF = 1e18;
const int M = 1e7;
const int MOD = 1e9 + 7;
int n,m,K;
struct node{
    int v,w;
};

int maxcnt(int x){
    int res=0;
    while(x){
        res++;
        x>>=1;
    }
    return res;
}

vector<node> e[N],g[N];
void add(int a,int b,int c){
    e[a].push_back({b,c});
}

void addg(int a,int b,int c){
    g[a].push_back({b,c});
}

int vis[N],dis[N];
priority_queue<pii> pq;

void djstr(int s){
    while(pq.size())pq.pop();
    for(int i=1;i<=n+2;i++){
        dis[i]=INF;vis[i]=0;
    }
    dis[s]=0;
    pq.push(mp(0,s));
    while(pq.size()){
        int x=pq.top().ps;
        // cerr<<"expend x:"<<x<<endl;
        pq.pop();
        if(vis[x])continue;
        // cerr<<"really expend x:"<<x<<endl;
        vis[x]=1;
        for(auto v:g[x]){
            // cerr<<"->try v.v:"<<v.v<<endl;
            if(!vis[v.v]&&dis[x]+v.w<dis[v.v]){
                dis[v.v]=dis[x]+v.w;
                pq.push(mp(-dis[v.v],v.v));

                // cerr<<x<<" to "<<v.v<<" apdated to .dis:"<<dis[v.v]<<endl;
            }
        }
    }
}

int flg[N];//感兴趣

int ans=INF;
void devide(int k){
    for(int i=1;i<=n;i++)g[i]=e[i];
    // g[n+1].clear();
    int sz=g[n+1].size();
    while(sz--)g[n+1].pop_back();
    // g[n+2].clear();
    sz=g[n+2].size();
    while(sz--)g[n+2].pop_back();

    // cerr<<k<<"   with GGGGG .g[3]"

    for(int i=1;i<=n;i++){//添加超级源点和汇点
        if(!flg[i])continue;
        if(i&(1<<k))addg(n+1,i,0);
        else addg(i,n+2,0);
    }
    djstr(n+1);
    ans=min(ans,dis[n+2]);
    // cerr<<k<<" .ans:"<<ans<<endl;
}

void devide2(int k){
    for(int i=1;i<=n;i++)g[i]=e[i];
    // g[n+1].clear();
    int sz=g[n+1].size();
    while(sz--)g[n+1].pop_back();
    // g[n+2].clear();
    sz=g[n+2].size();
    while(sz--)g[n+2].pop_back();

    // cerr<<k<<"   with GGGGG .g[3]"

    for(int i=1;i<=n;i++){//添加超级源点和汇点
        if(!flg[i])continue;
        if(i&(1<<k))addg(i,n+2,0);
        else addg(n+1,i,0);
    }
    djstr(n+1);
    ans=min(ans,dis[n+2]);
    // cerr<<k<<" .ans:"<<ans<<endl;
}

void init(){
    for(int i=1;i<=n;i++){
        int sz=e[i].size();
        while(sz--)e[i].pop_back();
    }
    ans=INF;
}

void solve(){
    init();
    n=rd,m=rd,K=rd;
    while(m--){
        int a=rd,b=rd,c=rd;
        add(a,b,c);
    }
    memset(flg,0,sizeof flg);
    for(int i=1;i<=K;i++){
        flg[rd]=1;
    }

    int bit=maxcnt(n);
    for(int i=0;i<bit;i++){
        devide(i);
        devide2(i);
    }
    cout<<ans<<endl;

}

signed main() {
    int T=rd;
    while(T--){
        // cerr<<"----------------"<<endl;
        solve();
    }
    return 0;
}

分组策略¶

例题 #1 利用组内元素关系分组 集合分组¶

例题 #2 二进制分组 [GXOI/GZOI2019] 旅行者¶

例题 #1 利用组内元素关系分组集合分组¶