Astronauts UVALive - 3713(2-SAT)
2024-10-19 11:53:47
大白书例题
#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 ;
}
最新文章
- jdbc java数据库连接 4)PreParedStatement接口 之 区别和例子
- C++ 字符编码转换类
- Bash注释
- [13]APUE:KQUEUE / FreeBSD
- Linux云主机安装JDK,配置hadoop的详细方式
- 【转】Oracle job procedure 存储过程定时任务
- 如何使用CSS Sprites技术进行图片合并
- Javascript Array Distinct (array.reduce实现)
- C# attribute_特性
- Android 事件处理
- JS URI Encode
- JS--------文件操作基本方法:上传/下载
- python 正则表达式re模块
- linux的shadow文件
- js 日期排序(sort)
- Webview窗口设置遮罩层
- G - SDOI
- python 基础_字符串9
- 洛谷P2679 子串 [noip2015] dp
- 20145324王嘉澜《网络对抗技术》MSF基础应用