SD省队集训2019Day1之“等你哈苏德”

等你哈苏德&＃xff08;wait&＃xff09;

题目描述

Joker 有一些黑白区间\([l_i,r_i]\)&＃xff0c;有些区间已经被指定了颜色&＃xff0c;有些却没有。你要指定
这些未染色区间的颜色&＃xff0c;使得数轴上对于每个点&＃xff0c;覆盖他的黑区间个数和白区间个数差
的绝对值小于等于1。

输入格式

从文件 wait.in 中读入数据。
输入正整数 m, n
接下来 m 行每行三个整数 Li, Ri,wi&＃xff0c;保证 1 ≤ Li ≤ Ri ≤ n,wi ∈ [−1, 1]
wi &＃61; −1 表示未染色&＃xff0c;wi &＃61; 0 表示是白色&＃xff0c;wi &＃61; 1 表示是黑色

输出格式

输出到文件 wait.out 中。
如果无解&＃xff0c;输出 −1。
否则输出一行 m 个 0/1 数表示每个区间是黑色还是白色。如果有多解&＃xff0c;输出任意一个均可得分。

做法

离散化后&＃xff0c;我们就只需要考虑区间的端点处的个数差。
把每个数轴上的点对应到一个图上的点&＃xff0c;一个区间\([l_i,r_i]\)视作\(l_i\)和\(r_i\)间的一条有向边&＃xff0c;其中黑色为从\(l_i\)到\(r_i\)&＃xff0c;白色相反&＃xff0c;染色视作定向。
如果沿着每条边遍历各个节点&＃xff0c;那么这就是一个欧拉路径问题。所以把奇度数的点排序后依次连接&＃xff0c;跑欧拉回路即可。
一部分线段染色相当于是混合图欧拉回路&＃xff0c;跑网络流即可。

代码

#include
#define maxn 200100
using namespace std;
namespace WXHAK
{
struct edge
{int r, nxt, w, id;
} e[maxn <<2];
int head[maxn], S, T, q[maxn], esz, l, r, cur[maxn], dep[maxn];
void addedge(int u, int v, int w, int id)
{e[&＃43;&＃43;esz].r &＃61; v;e[esz].nxt &＃61; head[u];head[u] &＃61; esz;e[esz].w &＃61; w;e[esz].id &＃61; id;e[&＃43;&＃43;esz].r &＃61; u;e[esz].nxt &＃61; head[v];head[v] &＃61; esz;e[esz].w &＃61; 0;e[esz].id &＃61; -id;
}
bool bfs()
{for (int i &＃61; S; i <&＃61; T; &＃43;&＃43;i)cur[i] &＃61; head[i], dep[i] &＃61; 0;l &＃61; r &＃61; 0, q[r&＃43;&＃43;] &＃61; S, dep[S] &＃61; 1;while (l }
int find(int u, int flow)
{if (u &＃61;&＃61; T)return flow;int used &＃61; 0, a &＃61; 0;for (int &t &＃61; cur[u]; t; t &＃61; e[t].nxt)if (e[t].w && dep[e[t].r] &＃61;&＃61; dep[u] &＃43; 1){a &＃61; find(e[t].r, min(flow - used, e[t].w));e[t].w -&＃61; a, e[t ^ 1].w &＃43;&＃61; a, used &＃43;&＃61; a;if (used &＃61;&＃61; flow)return used;}if (!used)dep[u] &＃61; -1;return used;
}
void init(int _S, int _T)
{S &＃61; _S, T &＃61; _T, esz &＃61; 1;for (int i &＃61; S; i <&＃61; T; &＃43;&＃43;i)head[i] &＃61; 0;
}
int dinic()
{int ans &＃61; 0, a &＃61; 0;while (bfs())while (a &＃61; find(S, 1 <<30))ans &＃43;&＃61; a;return ans;
}
void cal(int anses[])
{for (int i &＃61; 1; i <&＃61; esz; &＃43;&＃43;i)if (!e[i].w && e[i].id)anses[abs(e[i].id)] &＃61; e[i].id > 0 ? !anses[abs(e[i].id)] : anses[abs(e[i].id)];
}
} // namespace WXHAKint mtp, in[maxn], out[maxn], anses[maxn], tg[maxn];
int li[maxn], ri[maxn], lx[maxn], wi[maxn], lsh[maxn <<1], tp, n, m;
int main()
{freopen("wait.in", "r", stdin);freopen("wait.out", "w", stdout);scanf("%d%d", &m, &n);for (int i &＃61; 1; i <&＃61; m; &＃43;&＃43;i){scanf("%d%d%d", &li[i], &ri[i], &wi[i]);ri[i]&＃43;&＃43;;lsh[&＃43;&＃43;tp] &＃61; li[i], lsh[&＃43;&＃43;tp] &＃61; ri[i];lx[&＃43;&＃43;mtp] &＃61; li[i], lx[&＃43;&＃43;mtp] &＃61; ri[i];}]sort(lsh &＃43; 1, lsh &＃43; tp &＃43; 1);sort(lx &＃43; 1, lx &＃43; mtp &＃43; 1);tp &＃61; unique(lsh &＃43; 1, lsh &＃43; tp &＃43; 1) - lsh - 1;for (int i &＃61; 1; i <&＃61; m; &＃43;&＃43;i){li[i] &＃61; lower_bound(lsh &＃43; 1, lsh &＃43; tp &＃43; 1, li[i]) - lsh;ri[i] &＃61; lower_bound(lsh &＃43; 1, lsh &＃43; tp &＃43; 1, ri[i]) - lsh;}]for (int i &＃61; 1; i <&＃61; mtp; i &＃43;&＃61; 2){int x &＃61; lower_bound(lsh &＃43; 1, lsh &＃43; tp &＃43; 1, lx[i]) - lsh;int y &＃61; lower_bound(lsh &＃43; 1, lsh &＃43; tp &＃43; 1, lx[i &＃43; 1]) - lsh;if (x &＃61;&＃61; y)continue;tg[i] &＃61; rand() % 2;if (tg[i] &＃61;&＃61; 0)in[y]&＃43;&＃43;, out[x]&＃43;&＃43;;elsein[x]&＃43;&＃43;, out[y]&＃43;&＃43;;}for (int i &＃61; 1; i <&＃61; m; &＃43;&＃43;i){int r &＃61; (wi[i] &＃61;&＃61; -1 ? rand() % 2 : wi[i]);anses[i] &＃61; r;if (r &＃61;&＃61; 0)out[li[i]]&＃43;&＃43;, in[ri[i]]&＃43;&＃43;;elseout[ri[i]]&＃43;&＃43;, in[li[i]]&＃43;&＃43;;}WXHAK::init(0, tp &＃43; 1);int sum &＃61; 0;for (int i &＃61; 1; i <&＃61; tp; &＃43;&＃43;i)if ((in[i] - out[i]) & 1)return puts("-1"), 0;for (int i &＃61; 1; i <&＃61; tp; &＃43;&＃43;i){int d &＃61; (in[i] - out[i]) / 2;if (d > 0)WXHAK::addedge(WXHAK::S, i, d, 0), sum &＃43;&＃61; d;else if (d <0)WXHAK::addedge(i, WXHAK::T, -d, 0);}for (int i &＃61; 1; i <&＃61; m; &＃43;&＃43;i)if (wi[i] &＃61;&＃61; -1){if (anses[i] &＃61;&＃61; 0)WXHAK::addedge(ri[i], li[i], 1, i);elseWXHAK::addedge(li[i], ri[i], 1, i);}for (int i &＃61; 1; i <&＃61; mtp; i &＃43;&＃61; 2){int x &＃61; lower_bound(lsh &＃43; 1, lsh &＃43; tp &＃43; 1, lx[i]) - lsh;int y &＃61; lower_bound(lsh &＃43; 1, lsh &＃43; tp &＃43; 1, lx[i &＃43; 1]) - lsh;if (x &＃61;&＃61; y)continue;if (tg[i] &＃61;&＃61; 0)WXHAK::addedge(y, x, 1, 0);elseWXHAK::addedge(x, y, 1, 0);}int wxh &＃61; WXHAK::dinic();if (wxh !&＃61; sum)return puts("-1"), 0;WXHAK::cal(anses);for (int i &＃61; 1; i <&＃61; m; &＃43;&＃43;i){if (wi[i] !&＃61; -1)printf("%d ", wi[i]);elseprintf("%d ", anses[i]);}
}

简单分析一下&＃xff1a;
输入结束后&＃xff0c;首先在91~98行离散化。
99~110行&＃xff0c;对相邻的两个点之间的边定一个任意的方向。
111~119行&＃xff0c;对每个区间对应的边确定方向&＃xff08;有限定的不变&＃xff09;。
125~132行&＃xff0c;源点、汇点加入网络。
133~140行&＃xff0c;141~151行&＃xff0c;这两种边分别加入网络。
4~75及152~164行&＃xff0c;网络流。