CF1994F Stardew Valley 题解

刘梓轩2010 · 2024-09-13 16:27:14 · 题解

题目传送门：

luogu

CF1994F

题意

给你一张 n 个点 m 条边的图，上面有重要的和不重要的边，重要的边必须走，不重要的可走可不走，问你能不能构造出欧拉回路。

思路

首先，我们可以先把所有重要的边放到实际的图里，然后考虑加上某一些不重要的边，使得这张图上有欧拉回路。

让我们考虑如何构造。

首先，题目里已经保证了重要的边可以使得图联通，那么我们只用考虑度数的问题。我们只把不重要的边拿出来，我们发现，在一个连通块内，如果有奇数个奇度点，那么无论如何加边，我们都无法使得这张图满足条件，因为加边后奇度点的个数一定是 +2 或者 -2 的关系。

否则，贪心的加边，用不重要的边去跑出一个生成树森林，如果一个点是奇度点，那么就在实际的图上加上这个点到它父亲的边。到最后，如果根节点的度数是奇数，此时所有的非根节点都已经是偶度点了，说明原来这个连通块就有奇数个奇度点，说明没有合法方案。

最后，在实际图上跑出欧拉回路即可。

对于一组数据，时间复杂度是 O(n+m)，可以通过。

温馨提示，用 vector 存图跑欧拉回路时千万不能用 auto，否则每次遍历点的时候都会从 vector 的开头开始跑，会 TLE。

Code

#include <bits/stdc++.h>
#define endl '\n'
#define int long long
#define fi first
#define se second
using namespace std;
const int N=5e5+10;
const int inf=0x3f3f3f3f3f3f3f3f;
struct Node
{
    int v,id;
};
stack<int> st;
int t;
int n,m;
vector<Node> G[N],el[N];//1边,0边 
int deg[N];
bool vis[N];//点 
bool del[N];//边 
int cnt;
void dfs(int u)
{
    vis[u]=1;
    for(auto x:el[u])
    {
        int v=x.v;
        int id=x.id;
        if(vis[v]) continue;
        dfs(v);
        if(deg[v])
        {
            G[u].push_back({v,id});
            G[v].push_back({u,id});
            deg[u]^=1;
            deg[v]^=1;
            cnt++;
        }
    }
}
int ne[N];
void euler(int u)
{
    for(int i=ne[u];i<G[u].size();i=ne[u])
    {
        ne[u]=i+1;
        int v=G[u][i].v;
        int id=G[u][i].id;
        if(del[id]) continue;
        del[id]=1;
        euler(v);
    }
    st.push(u);
}
signed main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);
    cin>>t;
    while(t--)
    {
        cin>>n>>m;
        for(int i=1;i<=n;i++)
        {
            ne[i]=deg[i]=vis[i]=0;
            G[i].clear();
            el[i].clear();
        }
        for(int i=1;i<=m;i++) del[i]=0;
        cnt=0;
        for(int i=1;i<=m;i++)
        {
            int u,v,c;
            cin>>u>>v>>c;
            if(c)
            {
                G[u].push_back({v,i});
                G[v].push_back({u,i});
                deg[u]^=1;
                deg[v]^=1;
                cnt++;
            }
            else
            {
                el[u].push_back({v,i});
                el[v].push_back({u,i});
            }
        }
        bool fl=1;
        for(int i=1;i<=n;i++)
        {
            if(!vis[i])
            {
                dfs(i);
                if(deg[i])
                {
                    fl=0;
                    break;
                }
            }
        }
        if(!fl)
        {
            cout<<"NO"<<endl;
            continue;
        }
        cout<<"YES"<<endl<<cnt<<endl;
        euler(1);
        while(!st.empty())
        {
            cout<<st.top()<<" ";
            st.pop();
        }
        cout<<endl;
    }
    return 0;
}