P7317 [COCI2018-2019#3] Praktični 题解

larsr · 2024-06-11 19:34:03 · 题解

很好的一道题，但我没做出来。

先假设我们已经决定好边权值的最终值了，此时要用最少次数，很容易想到要用线性基。

那怎么决定最终值呢？首先选择在图上随便选一个生成树，如果一条非树边和它的两个端点路径的回路满足条件的话，那么这个图一定满足条件。

为什么呢？因为一边非树边和它的两个端点路径异或值相等，可以把非树边换成这条路径，那么任何一个回路，都会经过同一条边两次或不经过。

这是只改非树边是最优的，为什么呢？一个回路上更改的值的异或值是一定的，如果只更改非树边，变化量只有一个，线性基的结果也是最小的。那么求出每个非树边要更改的值即可。

时间复杂度 O(n\log V)。

#include<cstdio>
#include<vector>
#include<cstring>
#define N 100010
using namespace std;
int n, m, vis[N], d[N];
struct edge
{
    int to, w, id;
};
vector<edge>e[N];
int vid[N];
int xe[N], xid[N], tot = 0;
int bit[100];
vector<int>ans[100];
void dfs(int now)
{
    vis[now] = 1;
    for(int i = 0; i < e[now].size(); i++)
        if(!vis[e[now][i].to])
        {
            d[e[now][i].to] = d[now] ^ e[now][i].w;
            dfs(e[now][i].to);
        }
}
void dfs1(int now, int fa)
{
    vis[now] = 1;
    for(int i = 0; i < e[now].size(); i++)
    {
        int to = e[now][i].to;
        if(!vis[to])
        {
            dfs1(to, now);
        }
        else if(to != fa && !vid[e[now][i].id])
        {
            tot++;
            vid[e[now][i].id] = 1;
            xe[tot] = d[now] ^ d[to] ^ e[now][i].w;
            xid[tot] = e[now][i].id;
        }
    }
}
int main()
{
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= m; i++)
    {
        int a, b, p;
        scanf("%d%d%d", &a, &b, &p);
        e[a].push_back((edge){b, p, i});
        e[b].push_back((edge){a, p, i});
    }
    dfs(1);
    memset(vis, 0, sizeof vis);
    dfs1(1, 0);
    for(int i = 1; i <= tot; i++)
    {
        int now = xe[i];
        for(int j = 30; j >= 0; j--)
            if(now & (1 << j))
            {
                if(bit[j])now ^= bit[j];
                else
                {
                    bit[j] = now;
                    break;
                }
            }
    }
    for(int i = 1; i <= tot; i++)
    {
        int now = xe[i];
        for(int j = 30; j >= 0; j--)
            if(now & (1 << j))
            {
                ans[j].push_back(xid[i]);
                now ^= bit[j];
            }
    }
    int sum = 0;
    for(int i = 30; i >= 0; i--)
        if(bit[i])
            sum++;
    printf("%d\n", sum);
    for(int i = 30; i >= 0; i--)
    if(bit[i])
    {
        printf("%d %d ", bit[i], ans[i].size());
        for(int j = 0; j < ans[i].size(); j++)printf("%d ", ans[i][j]);
        printf("\n");
    }
    return 0;
}