P3007 The Continental Cowngress G 做题记录
一道还算板的题。
我们看到，这题干跟模板题没啥区别，唯一的区别是输出方案如果两者皆可输出 ?。
我们来想想怎样才能两者皆可，首先我们想想判断无解是怎么样的：两者在同一强连通分量里，而强连通分量的编号相当于拓扑序，我们要去拓扑序大的即强连通分量编号小的为答案，但是另一个难道就不能是答案了吗？有可能的。而我们发现，之前排除一个答案的方式是什么？往兄弟点连边，只有有边连向兄弟点的点才不能选，选强连通分量编号小的那个点只能保证答案一定不错。那么另一个点没连向兄弟边仍然能选，那么我们怎么办？我们发现数据范围很小，那么我们最后判断输出是像这样判断另一个是否可行就可以了：
for (rnt i = 1; i <= n; i++)
if (num[i] < num[i + n])
if (dfs(num[i + n], num[i]))
cout << "Y";
else
cout << "?";
else if (dfs(num[i], num[i + n]))
cout << "N";
else
cout << "?";另外，这道题要用上 tarjan 的缩点，缩点建边有两种方式，一种开新数组存边，优点是常数小，但是空间大且用新数组不顺手（你每次多打个下划线试试）
belike：
inline void _add(int u, int v)
{
_e[++cnt] = {v, _head[u]}, _head[u] = cnt;
}
for (rnt u = 1; u <= 2 * n; u++)
for (rnt i = head[u]; i; i = e[i].next)
{
int v = e[i].v;
int fu = num[u], fv = num[v];
if (fu != fv)
_add(fu, fv);//这里用的是新数组
}多打下划线很方便吧……
还有一种就是记录原来的边数，清空 head 数组和 cnt ，然后枚举每条边，优点是空间小，用起来顺手，缺点是常数要大一点。
belike：
m = cnt, cnt = 0;
for (rnt i = 1; i <= 2 * n; i++)
head[i] = 0;
for (rnt i = 1; i <= m; i++)
{
int fu = num[e[i].u], fv = num[e[i].v];
if (fu != fv)
add(fu, fv);
}另外不需要什么互不相交集合联合来存储每个点连了哪些点，所有不同的点相连的边都连上，还是一棵树的。
代码：
//Just Sayori
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <random>
#define ll long long
#define rnt register int
#define gr getchar
#define pr putchar
#define N 100005
#define M 1000000007
using namespace std;
inline ll read()
{
ll x = 0, f = 1;
char ch = gr();
while (ch < '0' || ch > '9')
ch == '-' ? f = -1, ch = gr() : ch = gr();
while (ch >= '0' && ch <= '9')
x = (x << 3) + (x << 1) + (ch ^ 48), ch = gr();
return x * f;
}
inline void write(ll x)
{
static int sta[39], top = 0;
if (x < 0)
pr('-'), x = -x;
do
sta[++top] = x % 10, x /= 10;
while (x);
while (top)
pr(sta[top--] ^ 48);
}
struct edge
{
int v, next;
} e[N << 1], _e[N << 1];
int head[N], cnt, _head[N];
inline void add(int u, int v)
{
e[++cnt] = {v, head[u]}, head[u] = cnt;
}
inline void _add(int u, int v)
{
_e[++cnt] = {v, _head[u]}, _head[u] = cnt;
}
int n, m, a, b, c, x, y, bcc, top;
int dfn[N], low[N], num[N], vis[N], stack[N];
char ch1, ch2;
void tarjan(int u)
{
dfn[u] = low[u] = ++cnt;
vis[u] = 1, stack[++top] = u;
for (rnt i = head[u]; i; i = e[i].next)
{
int v = e[i].v;
if (!dfn[v])
tarjan(v), low[u] = min(low[u], low[v]);
else if (vis[v])
low[u] = min(low[u], dfn[v]);
}
if (dfn[u] == low[u])
{
bcc++;
while (stack[top + 1] != u)
num[stack[top]] = bcc, vis[stack[top--]] = 0;
}
}
bool dfs(int u, int s)
{
if (u == s)
return 1;
for (rnt i = _head[u]; i; i = _e[i].next)
{
int v = _e[i].v;
if (dfs(v, s))
return 1;
}
return 0;
}
int main()
{
cin.tie(0);
//ios::sync_with_stdio(0);
n = read(), m = read();
for (rnt i = 1; i <= m; i++)
{
a = read(), cin >> ch1, x = (ch1 == 'Y'), b = read(), cin >> ch2, y = (ch2 == 'Y');
add(a + (x & 1)*n, b + (y ^ 1)*n), add(b + (y & 1)*n, a + (x ^ 1)*n);
}
for (rnt i = 1; i <= 2 * n; i++)
if (!dfn[i])
tarjan(i);
for (rnt i = 1; i <= n; i++)
if (num[i] == num[i + n])
return puts("IMPOSSIBLE"), 0;
cnt = 0;
for (rnt u = 1; u <= 2 * n; u++)
for (rnt i = head[u]; i; i = e[i].next)
{
int v = e[i].v;
int fu = num[u], fv = num[v];
if (fu != fv)
_add(fu, fv);
}
for (rnt i = 1; i <= n; i++)
if (num[i] < num[i + n])
if (dfs(num[i + n], num[i]))
cout << "Y";
else
cout << "?";
else if (dfs(num[i], num[i + n]))
cout << "N";
else
cout << "?";
return 0;
}