CF587D Duff in Mafia 做题记录

· · 个人记录

人生的第二道黑，2-SAT 的大杂烩，出场了。

看到 匹配，我又想起了二分图，当然这不重要。我们知道，一个点发出的边只能选一条，要求最小的最大边权。

首先观察颜色，我们要保证每个颜色的边是匹配，那一个点最多一种颜色只能有两条边，这样选走一条还剩一条，三条及以上就是必错了，所以用 vector 存下每条边的颜色和编号，按颜色排序，一个点的 vector 内前面的第二条边和它同色就直接输出 NO。

然后我们要求最小的最大边权，想到二分答案。然后在函数里面开始建边吧！
首先一个点发出的边只能选一条，选了其他都不能选，而这样时间复杂度是 O(n^2) 的，但是我们可以用前缀优化建边，但是我们发现，像下面这种情况，我们以往的 i+2n 和 i+3n 会出错。 但是我们可以动态开点，记录前一个点的 p_0 和 p_1，然后连边，belike：

now1 = ++tot, now2 = ++tot;
add(v[i][j].second, now1), add(now2, v[i][j].second + m);//second 表示边的编号
if (j)
{
  add(last1, now1), add(now2, last2);
  add(v[i][j].second, last2), add(last1, v[i][j].second + m);
}
last1 = now1, last2 = now2;

通过我们的特判，一个点发出的边相同颜色的只有两条的了，所以一条不选那就要选另一条，但是这里要注意不能只连选了一条不选另一条，因为这样会两个都不选；但可以只连不选一条选另一条，因为另一个在上面就连好了。当然场上以防万一也可以，不过小心爆空间。

for (rnt j = 1; j < v[i].size(); j++)
  if (v[i][j].first == v[i][j - 1].first)
    add(v[i][j].second + m, v[i][j - 1].second), add(v[i][j - 1].second + m, v[i][j].second), add(v[i][j].second, v[i][j - 1].second + m), add(v[i][j - 1].second, v[i][j].second + m);//后两个可以删除。

最后边权大于当前二分值的边直接排除：

for (rnt i = 1; i <= m; i++)
  if (a[i].t > k)
    add(i, i + m);

然后跑 tarjan()，最后考虑输出答案，但是翻译没写怎么输出，首先输出 Yes 或 No，如果输出 Yes，那么输出最大边权和分组的边数，然后从小到大输出边的编号。另外注意，当 r=M 时也要输出 No。
另另外，二分出的答案不一定执行了 work()，所以跑一遍再输出。

AC 代码：

//Just Sayori
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#define ll long long
#define rnt register int
#define gr getchar
#define pr putchar
#define N 500005
#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 top = 0, sta[39];
    if (x < 0)
        pr('-');
    do
        sta[++top] = x % 10, x /= 10;
    while (x);
    while (top)
        pr(sta[top--] ^ 48);
}

struct edge
{
    int v, next;
} e[N << 3];
int head[N], cnt;

inline void add(int u, int v)
{
    e[++cnt] = {v, head[u]}, head[u] = cnt;
}
int n, m, ans, bcc, top, tot, now1, now2, last1, last2;
int dfn[N], low[N], num[N], vis[N], ord[N], stack[N];
vector<pair<int, int>> v[N];

struct node
{
    ll v, u, c, t;
} a[N];

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 work(int k)
{
    for (rnt i = 1; i <= tot; i++)
        dfn[i] = num[i] = vis[i] = head[i] = stack[i] = 0;
    bcc = cnt = top = 0, tot = 2 * m;
    for (rnt i = 1; i <= n; i++)
    {
        for (rnt j = 0; j < v[i].size(); j++)
        {
            now1 = ++tot, now2 = ++tot;
            add(v[i][j].second, now1), add(now2, v[i][j].second + m);
            if (j)
            {
                add(last1, now1), add(now2, last2);
                add(v[i][j].second, last2), add(last1, v[i][j].second + m);
            }
            last1 = now1, last2 = now2;
        }
        for (rnt j = 1; j < v[i].size(); j++)
            if (v[i][j].first == v[i][j - 1].first)
                add(v[i][j].second + m, v[i][j - 1].second), add(v[i][j - 1].second + m, v[i][j].second);
    }
    for (rnt i = 1; i <= m; i++)
        if (a[i].t > k)
            add(i, i + m);
    for (rnt i = 1; i <= 2 * m; i++)
        if (!dfn[i])
            tarjan(i);
    for (rnt i = 1; i <= m; i++)
        if (num[i] == num[i + m])
            return 0;
    return 1;
}

int main()
{
    n = read(), m = read();
    for (rnt i = 1; i <= m; i++)

        a[i] = {read(), read(), read(), read()};
    for (rnt i = 1; i <= m; i++)
        v[a[i].u].push_back(make_pair(a[i].c, i)), v[a[i].v].push_back(make_pair(a[i].c, i));
    sort(v[1].begin(), v[1].end());
    for (rnt i = 1; i <= n; i++, sort(v[i].begin(), v[i].end()))
        for (rnt j = 2; j < v[i].size(); j++)
            if (v[i][j - 2].first == v[i][j].first)
                return puts("No"), 0;
    int l = 0, r = M;
    while (l < r)
    {
        int mid = (l + r) >> 1;
        if (work(mid))
            r = mid;
        else
            l = mid + 1;
    }
    if (r == M)
        return puts("No"), 0;
    puts("Yes");
    work(r);
    write(r), pr(32);
    v[1].clear();
    for (rnt i = 1; i <= m; i++)
        if (num[i] < num[i + m])
            v[1].push_back(make_pair(i, 0));
    write(v[1].size()), pr(10);
    for (rnt i = 0; i < v[1].size(); i++)
        write(v[1][i].first), pr(32);
    return 0;
}