HY 书院共有 \(n\) 名同学，你要将他们分为 \(m\) 个组。由于一些特殊的原因，每个同学只有 2 个组想去.
现在你想把他们安排到组里，然后进行入教活动。
入教活动需要在组内细分成活动队，每一个活动队恰好包含两个人，每个人最多参加一个活动队。不难发现对于每一个组，要么每个人都可以参加一个活动队，要么恰好有一个人参加不了活动队。
如果有参加不了活动队的人，他会很愤怒的退出，而这会亏损入教组给你的收益。已知目前你的收益为 \(k\) ，每存在一个人参加不了活动队就会给你的收益扣除 \(1\) ，求你分组后最大可能的净收益。
\(1\leq n,m\leq 10^5,1\leq k\leq 10^9,1\leq a_i,b_i\leq n\)
看上去应该是一个图论的题目 .
然后，然后我就不会做了 .
考虑连边 \(a_i\) 和 \(b_i\) . 转为一个 \(m\) 个点，\(n\) 条边的图 .
首先钦定所有边都选 \(a_i\) ，如果一个点的入度是奇数为 \(1\) ，如果是偶数就是 \(0\) .
那么，考虑调整一条边的方向，会造成什么 .
\((0,1)\rightarrow (1,0)\)
\((0,0)\rightarrow (1,1)\)
\((1,1)\rightarrow (0,0)\)
接着，发现，通过这几个操作，会使初始有 \(x\) 个入度为 \(1\) 的点的图 ，变成 \(x\% 2\) 个点的度数为 \(1\) .
那么，建图 dfs 就可以了 .
时间复杂度 : \(O(n+m)\)
空间复杂度 : \(O(n+m)\)
code
#include<bits/stdc++.h>
using namespace std;
inline int read(){
char ch=getchar();
while(ch<'0'||ch>'9')ch=getchar();
int res=0;
while(ch>='0'&&ch<='9'){
res=res*10+ch-'0';
ch=getchar();
}
return res;
}
inline void print(int res){
if(res==0){
putchar('0');
return;
}
int a[10],len=0;
while(res>0){
a[len++]=res%10;
res/=10;
}
for(int i=len-1;i>=0;i--)
putchar(a[i]+'0');
}
int n,m,k;
bool vis[100010];
vector<int>v;
vector<pair<int,int> >g[100010];
int cnt[100010];
void dfs(int x){
vis[x]=true;
v.push_back(x);
for(int i=0;i<(int)g[x].size();i++){
int to=g[x][i].first,id=g[x][i].second;
if(!vis[to]){
dfs(to);
}
}
}
int main(){
freopen("profit.in","r",stdin);
freopen("profit.out","w",stdout);
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
n=read();m=read();k=read();
for(int i=0;i<n;i++){
int a=read()-1,b=read()-1;
g[a].push_back(make_pair(b,i));
g[b].push_back(make_pair(a,i));
cnt[a]++;
}
int ans=0;
for(int i=0;i<m;i++){
if(!vis[i]){
v.clear();
dfs(i);
int sum=0;
for(int j=0;j<(int)v.size();j++){
if(cnt[v[j]]&1){
sum++;
}
}
ans+=sum%2;
}
}
k=k-ans;
if(k<0)putchar('-');
k=abs(k);
print(k);
putchar('\n');
return 0;
}
/*inline? ll or int? size? min max?*/