训练指南 UVALive - 3713 (2-SAT)
2024-08-29 11:26:24
layout: post
title: 训练指南 UVALive - 3713 (2-SAT)
author: "luowentaoaa"
catalog: true
mathjax: true
tags:
- 2-SAT
- 图论
- 训练指南
Astronauts
题意
有A,B,C三个任务要分配个N个宇航员,每个宇航员恰好要分配一个任务,设平均年龄为X,只有年龄大于或等于X的宇航员才能分配任务A。只有年龄严格小于X的宇航员才能分配任务B。而任务C没有限制。有M对宇航员相互讨厌,因此不能分配到同一任务。编程找出一个满足上述所有要求的任务分配方案。
题解
如果憎恶就代表不能一起去C,如果年龄相同就代表不能一起去A/B;
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
const int maxn=1e6+50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
struct TwoSAT{
int n;
vector<int> G[maxn*2];
bool mark[maxn*2];
int S[maxn*2],c;
bool dfs(int x){
if(mark[x^1])return false;
if(mark[x])return true;
mark[x]=true;
S[c++]=x;
for(int i=0;i<G[x].size();i++)
if(!dfs(G[x][i]))return false;
return true;
}
void init(int n){
this->n=n;
for(int i=0;i<n*2;i++)G[i].clear();
memset(mark,0,sizeof(mark));
}
/// x=xval or y= yval;
void add_caluse(int x,int xval,int y,int yval){
x=x*2+xval;
y=y*2+yval;
G[x^1].push_back(y);///如果x为真 那么y必须为假;
G[y^1].push_back(x);///如果y为真 那么x必须为假;
}
bool solve(){
for(int i=0;i<n*2;i+=2)
if(!mark[i]&&!mark[i+1]){
c=0;
if(!dfs(i)){
while(c>0)mark[S[--c]]=false;
if(!dfs(i+1))return false;
}
}
return true;
}
};
int n,a[maxn],m;
TwoSAT solver;
int tol;
int is_young(int x){
return a[x]*n<tol;
}
int main()
{
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
while(cin>>n>>m&&n&&m){
tol=0;
solver.init(n);
for(int i=0;i<n;i++){
cin>>a[i];
tol+=a[i];
}
for(int i=0;i<m;i++){
int a,b;
cin>>a>>b;a--;b--;
solver.add_caluse(a,1,b,1);
if(is_young(a)==is_young(b))
solver.add_caluse(a,0,b,0);
}
if(!solver.solve())cout<<"No solution."<<endl;
else for(int i=0;i<n;i++)
if(solver.mark[i*2])cout<<"C"<<endl;
else if(is_young(i))cout<<"B"<<endl;
else cout<<"A"<<endl;
}
return 0;
}
最新文章
- jpa
- 实现在GET请求下调用WCF服务时传递对象(复合类型)参数
- 理解insert all/insert first的使用
- word 排版问题
- ylbtech-dbs:ylbtech-6,record(生活记录)
- CentOS6.5配置vim使支持Python
- JavaScripts学习日记——DOM
- css区块定位之浮动与清除属性
- JetBrains套装免费学生授权申请(IntelliJ, WebStorm...)
- iOS Regex匹配关键字并修改颜色
- 【SSH系列】-- Hibernate持久化对象的三种状态
- python 模块与包
- springCloud笔记
- ssh-key 与 git账户配置以及多账户配置,以及通信方式从https切换到ssh
- Java享元模式
- SpringJDBC数据库的基本使用
- 分享一个excel根据文件超链接获取链接文档的最后更新时间
- 【FusionCharts学习-2】第一个FusionCharts程序
- 异度之刃 Xenoblade 后感
- 设置iframe内表单target属性以兼容IE、Firefox【转载】