自动搬运

查看原文

来自洛谷，原作者为

	cc123321 **

搬运于2025-08-24 22:03:39，当前版本为作者最后更新于2018-08-16 07:51:07，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

哎，我还是太弱了，一天偶然在办公室看都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;
}