CF1907G Lights 题解

· · 题解

题解

我们把原问题转化为图上问题，第 i 个灯会影响 a_i 灯的状态，于是可以建立一条 i 指向 a_i 的有向边表示关系。

这时候我们发现，对于图中入度为 0 的点，没有其它点能影响它，我们只能选择是否改变这些点的状态，并把其产生的影响传递给下一个点。

遍历过的入度为 0 的点我们势必不会再去考虑它。于是很合理的想法就是用拓扑排序，一步步将能删的点删掉并统计贡献。拓扑到最后，图中就剩下了数个环。

如何处理环呢？不难发现，环上两个颜色为 1 的点可以两两相消，其产生的贡献即是由一个点走到另一个点的距离。显然，我们选择图上相邻的两个颜色为 1 的点相消是最优的，且环上颜色为 1 的点的数目必须为偶数，否则就只能输出 '-1'。

于是对于一个环，我们可以把环上的颜色为 1 的点顺次编号，奇数编号与偶数编号的点可以互消，且有“奇消偶”和“偶消奇”两种方案。我们可以把这两种方案的贡献都统计下来，最后再选择和更小的作为消去方案即可。

实现贡献统计也非常简单。实际上，两种方案所经过的路径在环上是交替出现的，所以我们也只需要顺次统计两个标点间的路径长度，然后将其交替加入两种方案即可。

\text{Code:}

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define maxn 200050
#define maxm 200050 
#define vi vector <int>
#define vvi vector <vi>
#define endl '\n'
#define ll long long
using namespace std;

int n; 
int idg[maxn];
bool tag[maxn];
queue <int> q;

void clean()
{
    memset(idg, 0, sizeof(int)*(n + 5));
    memset(tag, false, sizeof(bool)*(n + 5));
}

void solve()
{
    cin >> n;
    vi a(n + 1);
    clean();
    for(int i = 1; i <= n; i ++){
        char ch; cin >> ch;
        tag[i] = ch - '0';
    }
    for(int i = 1; i <= n; i ++){
        cin >> a[i];
        idg[a[i]] ++;
    }
    for(int i = 1; i <= n; i ++){
        if(idg[i] == 0) q.push(i);
    }
    vi ans;
   //拓扑排序
    while(q.size()){
        int x = q.front(); q.pop();
        int y = a[x];
        idg[y] --;
        if(tag[x]) tag[y] = !tag[y];
        if(idg[y] == 0) q.push(y);
        if(tag[x]) tag[x] = false, ans.emplace_back(x);
    }
   //以下为处理环
    for(int i = 1; i <= n; i ++){
        if(idg[i] && tag[i]){ //在环上且为 1
            vi ansa, ansb;
            int nw = i;
            bool flag = false; //flag 作为交替统计的标记
            do{
                idg[nw] --;
                if(tag[nw]) flag = !flag;
                if(flag) ansa.emplace_back(nw);
                else ansb.emplace_back(nw);
                nw = a[nw];
            }while(idg[nw]);
            if(flag) {cout << -1 << endl; return;}
            if(ansa.size() < ansb.size()) //选择更小的方案加入答案
                ans.insert(ans.end(), ansa.begin(), ansa.end());
            else 
                ans.insert(ans.end(), ansb.begin(), ansb.end());
        }
    }
    cout << ans.size() << endl;
    for(int e : ans) cout << e << ' ';
    cout << endl;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0); //cout.tie(0);

    int t = 1;
    cin >> t; 
    while(t --) solve();

    return 0;
}