大白书例题
#include <iostream>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <map>
#include <set>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
#define rap(a, n) for(int i=a; i<=n; i++)
#define MOD 2018
#define LL long long
#define ULL unsigned long long
#define Pair pair<int, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define _ ios_base::sync_with_stdio(0),cin.tie(0)
//freopen("1.txt", "r", stdin);
using namespace std;
const int maxn = ;struct TwoSAT {
int n;
vector<int> G[maxn*];
bool mark[maxn*];
int S[maxn*], c; bool dfs(int x) {
if (mark[x^]) return false;
if (mark[x]) return true;
mark[x] = true;
S[c++] = x;
for (int i = ; i < G[x].size(); i++)
if (!dfs(G[x][i])) return false;
return true;
} void init(int n) {
this->n = n;
for (int i = ; i < n*; i++)
G[i].clear();
memset(mark, , sizeof(mark));
} void add_clause(int x, int xval, int y, int yval) {
x = x * + xval;
y = y * + yval;
G[x^].push_back(y);
G[y^].push_back(x);
} bool solve() {
for(int i = ; i < n*; i += )
if(!mark[i] && !mark[i+]) {
c = ;
if(!dfs(i)) {
while(c > ) mark[S[--c]] = false;
if(!dfs(i+)) return false;
}
}
return true;
}
};TwoSAT solver;int n, m, total_age, age[maxn];int is_young(int x) {
return age[x] * n < total_age;
}int main() {
while(scanf("%d%d", &n, &m) == && n) {
total_age = ;
for(int i = ; i < n; i++) {
scanf("%d", &age[i]);
total_age += age[i];
} solver.init(n);
for(int i = ; i < m; i++) {
int a, b;
scanf("%d%d", &a, &b);
a--;
b--;
if(a == b) continue;
solver.add_clause(a, , b, ); //不能同时为真
if(is_young(a) == is_young(b))
solver.add_clause(a, , b, ); //不能同时为假
} if(!solver.solve()) printf("No solution.\n");
else {
for(int i = ; i < n; i++)
if(solver.mark[i*]) printf("C\n"); //设的是选c为真 因为年龄小和年龄大的c是相同的 a和b不好直接判断 所以只要c被标记了 那么就是选了c
else if(is_young(i)) printf("B\n"); //如果没选c 那就判断是不是年龄小的
else printf("A\n");
}
}
return ;
}