题面

有 A,B,C 三个任务要分给 \(n\) 个宇航员，其中每个宇航员都要有且只能有一个任务。

假设所有宇航员的平均年龄为 \(x\)，只有年龄大于等于 \(x\) 的才能分配 A 任务，年龄小于 \(x\) 的才能分配 B 任务，C 任务没有限制。

有 \(m\) 对宇航员互相讨厌对方，他们不能去完成同一个任务。

你需要求出一种方案。若无解输出 No solution.。

\(1 \leq n,m \leq 10^5\)

思路

首先先说算法，这是一个 2-SAT 问题。

首先 A 和 B 可以看成一类，只是在不同的年龄段有不同的表现形式。所以我们可以看成只需要考虑 A / B,C 两个任务。

然后对于每一对互相讨厌的宇航员 \((x,y)\)，如果他们一个只能去 A 和 C，一个只能去 B 和 C，那么我们只需要满足如果一个人去了 A / B，另一个人一定要去 C。连边 \((x+n,y),(y+n,x)\)。（其中 \(i\) 表示 \(i\) 分配到 A / B 任务，\(i+n\) 表示 \(i\) 分配到 C 任务，下同。）

如果这一对宇航员年龄段相同，我们除了上面连的边外，还需要连 \((x,y+n)\) 和 \((y,x+n)\)（想一想，为什么）。

然后正常跑 Tarjan 即可。

时间复杂度 \(O(n)\)。

代码

#include <bits/stdc++.h>
#define CL(x) memset(x,0,sizeof(x))
using namespace std;

const int N = 2e6+5;
int n,m;
int age[N];

struct edge{
    int nxt,to;
} g[N];
int head[N],ec;

void add(int u,int v){
    g[++ec].nxt=head[u];
    g[ec].to=v;
    head[u]=ec;
}

int low[N],dfn[N],color[N],ccnt,dfscnt,vis[N];
stack<int> sta;

void tarjan(int u){
    dfn[u]=low[u]=(++dfscnt);vis[u]=1;
    sta.push(u);
    for(int i=head[u];i;i=g[i].nxt){
        int v=g[i].to;
        if(!dfn[v]){
            tarjan(v);
            low[u]=min(low[u],low[v]);
        }
        else if(vis[v]){
            low[u]=min(low[u],dfn[v]);
        }
    }
    if(low[u]==dfn[u]){
        ccnt++;
        while(sta.top()!=u){
            color[sta.top()]=ccnt;
            vis[sta.top()]=0;
            sta.pop();
        }
        color[u]=ccnt;
        vis[u]=0;
        sta.pop();
    }
}

void clean(){
    CL(low);CL(dfn);CL(color);CL(vis);
    dfscnt=0;ccnt=0;
    while(!sta.empty()) sta.pop();
    CL(g);CL(head);ec=0;
}

int sum;

bool isB(int x){
    return age[x]*n<sum;
}

signed main(){
    while(cin>>n>>m){
        if(!n&&!m) break;
        clean();
        for(int i=1;i<=n;i++) cin>>age[i];
        sum=accumulate(age+1,age+n+1,0);
        for(int i=1;i<=m;i++){
            int x,y;
            cin>>x>>y;
            if(isB(x)!=isB(y)){
                add(x+n,y);add(y+n,x);
            }
            else{
                add(x+n,y);add(x,y+n);
                add(y+n,x);add(y,x+n);
            }
        }
        for(int i=1;i<=(n<<1);i++){
            if(!dfn[i]) tarjan(i);
        }
        bool flag=0;
        for(int i=1;i<=n;i++){
            if(color[i]==color[i+n]){
                cout<<"No solution."<<'\n';
                flag=1;
                break;
            }
        }
        if(flag) continue;
        for(int i=1;i<=n;i++){
            cout<<((color[i]<color[i+n])?(isB(i)?'B':'A'):'C')<<'\n';
        }
    }
    return 0;
}