题解 P4790 【[BalticOI 2018]多角恋】

· · 题解

哎，我还是太弱了，一天偶然在办公室看都ZYC巨佬在看这个题目，身为一个小蒟蒻，当然要在大佬边上假装一起看。

然后我看了看这个毒瘤题，第一反应贪心。然后看着ZYC打开了LOJ的题解，我靠，什么子集动态规划，什么鬼。

然后放学的时候我跟kczno1大佬讲了讲我的想法，然后第二天他告诉我好像是对的。。。

然后我就来敲了一发，居然过掉了。。。

第一如果n是奇数，直接判-1；

定义nex[i]表示i的指向，如果i指向自己，那么就把nex[i] = 0；

use[i]表示i是否被用过；

deg[i]表示i点的入度；

先把已经构成那玩意儿的东西找出来。

然后算出剩下的deg；

每次选择入度为0的点，判断他的nex[]是否被用过。

如果nex[]被用过了，那就只把ans++；

否则看nex[]的入度是否为0，看看需不需要加入队列；

那么消到最后会剩下许多环（有可能也会没有），那么按照环的奇偶性判断一下需要加上多少答案就好了

（注意，代码里面长度为1的环已经判过了，所以就不用再判了）

由于输入比较恶心，所以我用了个map存；

#include<bits/stdc++.h>
#define maxn 500005
using namespace std;
inline int read()
{
    char x = getchar();
    int lin = 0, f = 1;
    while(x < '0' || x > '9')
    {
        if(x == '-') f = -1;
        x = getchar();
    }
    while(x >= '0' && x <= '9')
    {
        lin = lin * 10 + x - '0';
        x = getchar();
    }
    return lin * f;
}
map <string,int> mapp;
int n,tot,ans,u,v,nex[maxn],use[maxn],deg[maxn];
string a,b;
queue <int> q;
int sol(string s)
{
    if(!mapp.count(s))
        mapp[s] = ++tot;
    return mapp[s];
}
int solve(int pos)
{
    if(use[pos]) return 0;
    use[pos] = 1;
    return solve(nex[pos]) + 1;
}
#define PII pair<int,int>
#define fir first
#define sec second
#define ma(a,b) make_pair(a,b)
//PII ss[maxn];
int main(){
    n = read();
    if(n & 1)
    {
        printf("-1");
        return 0;
    }
    for(int i = 1; i <= n; i++)
    { 
        cin >> a >> b;
        u = sol(a); v = sol(b);
        if(u != v)
            nex[u] = v;
    }
    use[0] = 1;//注意 
    for(int i = 1; i <= n; i++)//找出已经符合条件的东西 
        if(i == nex[nex[i]] && !use[i] && !use[nex[i]])
            use[i] = use[nex[i]] = 1;
    for(int i = 1; i <= n; i++)//处理deg 
        if(!use[i])
            ++deg[nex[i]];
    for(int i = 1; i <= n; i++)
        if(!deg[i] && !use[i])
            q.push(i);
    while(q.size())//贪心 
    {
        int now = q.front(); q.pop();
        ++ans;
        if(!use[nex[now]])
        {
            use[nex[now]] = 1;
            --deg[nex[nex[now]]];
            if(!deg[nex[nex[now]]] && !use[nex[nex[now]]])
                q.push(nex[nex[now]]);
        }
    }
    for(int i = 1; i <= n; i++)//判环 
        if(!use[i])
        {
            int k = solve(i);
            if(k <= 1) continue;
            if(k & 1) ++ans;
            ans += k / 2;
        }
    cout << ans;
}