题目：
现在有一个长度为n的序列待构造，给出m对关系(i, j,x)，表示(a_i|a_j=x)，请在满足这m对关系的情况下构造出的最小字典序的序列。
分析：
每当我们看到最小字典序的时候，基本都是贪心的思想。本题可以知道，我们要让序列前面的数尽可能的小。对于他给出的关系，需要按位来考虑，但是有一些麻烦的就是你确定一个数的一位的时候，他会影响到与他有关系的数，感觉就是一个二分图的思想。我们可以用(f0[i][j])表示第(i)个数在第(j)位必定填0，(f1[i][j])同理必定填1。顺序遍历序列，枚举位，能填0就填0。
实现：
对于给出的关系 若x在第(k)位上为0，那么(i)和(j)在第k位上都必须填0，若x在第(k)位上为1，那么(i)和(j)在第k位上至少要有一个人是1。同时不能忽略(i=j)的情况，若(i==j)且x在第(k)位上为1，那么(i)在第k位上必须填1。那么现在我们预处理出了必须填的情况，但是还有一种情况我们是不能确定的，就是当某位可以填0或者填1的时候，怎么办？基于贪心的思想，肯定是填0最好，但是不一定能填上。为什么？因为如果你这一位填0，那么和他有关的那个数的这一位必须就填1，所以要在合法的情况下，才能填上0。这就是用到了二分图的思想，实现上我们将这种模糊的关系连一条边，对于当前(a_i)决定要填0的时候，遍历一下，若目标数在该位上必须填0，那么我当前(a_i)就只能填1了，因为模糊的优先级是不如必定的。
#include
using namespace std;
#define rep(i, a, n) for(int i = a; i < n; i++)
#define all(x) x.begin(), x.end()
#define pb push_back
#define ios ios::sync_with_stdio(false);cin.tie(0);
#define debug(x) cout << x << endl;
#define SZ(x) (int)x.size()
typedef long long LL;
typedef unsigned long long ULL;
typedef pair PII;
const int inf = 0x3f3f3f3f;
void read(int &x) {int s = 0, f = 1; char ch = getchar(); while(!isdigit(ch)) {f = (ch == '-' ? -1 : f); ch = getchar();} while(isdigit(ch)) {s = s * 10 + ch - '0'; ch = getchar();} x = s * f;}
const int N = 100005;
int n, m;
vector g[N][30];
int f0[N][30], f1[N][30]; //第i个数的第j位必须填0或者必须填1
signed main()
{
cin >> n >> m;
rep(i, 1, m + 1)
{
int u, v, c;
cin >> u >> v >> c;
if(u > v) swap(u, v);
for(int j = 29; j >= 0; j --)
{
if(c >> j & 1)
{
if(u == v)
f1[u][j] = f1[v][j] = 1;
else
g[u][j].push_back(v);
}
else
f0[u][j] = f0[v][j] = 1;
}
}
rep(i, 1, n + 1)
{
int res = 0;
for(int j = 29; j >= 0; j --)
{
bool can0 = 1;
if(f1[i][j])
can0 = 0;
else if(!f1[i][j] && !f0[i][j])
{
for(int v : g[i][j])
if(f0[v][j])
can0 = 0;
}
if(can0) //这位填0
for(int v : g[i][j])
f1[v][j] = 1;
else
res += 1 << j;
}
cout << res << ' ';
}
cout << '\n';
}
Original: https://www.cnblogs.com/DM11/p/16649209.html
Author: DM11
Title: D. 2+ doors（构造 二分图） CF 1715D
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/604346/
转载文章受原作者版权保护。转载请注明原作者出处！