题解 P8095 [USACO22JAN] Cereal 2 S

先不考虑第一喜欢和第二喜欢的区别,假设奶牛可以任意选择第一喜欢和第二喜欢。那么可以把奶牛看做无向边,麦片看做是顶点,建出一张无向图。

当然图不一定联通,考虑每个 \(x\) 点的联通块:

  • 如果是树,那么有 \(x-1\) 条边,考虑浪费掉一个点(例如根),每条边选择儿子即可。在有第一喜欢和第二喜欢的情况下,这样做自然也是可行的。

  • 如果不是树,那么至少有 \(x\) 条边。显然最多只有 \(x\) 只奶牛满足。考虑他的生成树(这里拿 DFS 树更方便)包含 \(x-1\) 条边,再随便选一条额外的边。我们先选择额外的边,它的第一喜欢的点设为根。其他边按照树做就行了。

于是每个连通块都最大化了,就做好了。

代码不够优美,仅供参考。

// By: Little09
// Problem: P8095 [USACO22JAN] Cereal 2 S
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P8095
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mem(x) memset(x,0,sizeof(x))
#define printYes puts("Yes")
#define printYES puts("YES")
#define printNo puts("No")
#define printNO puts("NO")

const ll inf=1000000000000000000; 
//const ll mod=998244353;
//const ll mod=1000000007;

const int N=100005;
int n,m; 
int a[N],b[N];

vector<int>t[N],v[N];
vector<int>g[N],val[N];

inline int read()
{
    int F=1,ANS=0;
	char C=getchar();
    while (C<'0'||C>'9')
	{
		if (C=='-') F=-1;
		C=getchar();
	}
    while (C>='0'&&C<='9')
	{
		ANS=ANS*10+C-'0';
		C=getchar();
	}
    return F*ANS;
}
inline char readchar()
{
	char C=getchar();
    while (C<33||C>126) C=getchar();
    return C;
}
inline int raed(){return read();}
bool vis[N];
int s,num;
int ans[N],cnt;
bool used[N];
void dfs(int x,int fa)
{
	num++;
	vis[x]=1;
	for (int i=0;i<t[x].size();i++)
	{
		if (v[x][i]==fa) continue;
		if (vis[t[x][i]]==1)
		{
			if (s==-1) 
			{
				s=a[v[x][i]];
				ans[++cnt]=v[x][i];
				used[v[x][i]]=1;
			}
			continue;
		}
		g[x].push_back(t[x][i]);
		g[t[x][i]].push_back(x);
		val[x].push_back(v[x][i]);
		val[t[x][i]].push_back(v[x][i]);
		dfs(t[x][i],v[x][i]);
	}
}

void dfs2(int x,int fa)
{
	for (int i=0;i<g[x].size();i++)
	{
		if (val[x][i]==fa) continue;
		ans[++cnt]=val[x][i];
		used[val[x][i]]=1;
		dfs2(g[x][i],val[x][i]);
	}
}

int main()
{
	m=read(),n=raed();
	for (int i=1;i<=m;i++)
	{
		a[i]=read(),b[i]=read();
		t[a[i]].push_back(b[i]);
		t[b[i]].push_back(a[i]);
		v[a[i]].push_back(i);
		v[b[i]].push_back(i);
	}
	int tot=0;
	for (int i=1;i<=n;i++)
	{
		if (vis[i]==1) continue;
		s=-1,num=0;
		dfs(i,-1);
		if (s==-1) tot+=num-1;
		else tot+=num;
		if (s==-1) dfs2(i,-1);
		else dfs2(s,-1);
	}
	for (int i=1;i<=m;i++)
	{
		if (used[i]==0) ans[++cnt]=i;
	}
	cout << m-tot << endl;
	for (int i=1;i<=cnt;i++) printf("%d\n",ans[i]);
	return 0;
}

上一篇:YbtOJ-变量观测【鸽笼原理】


下一篇:Painter绘制《围城》过程图解