[HDU1038]Ant Trip（并查集+欧拉图）

题目描述

传送门

题目大意：给出一个n个点m条边的无向图，问最少用多少条路径能覆盖每一条边恰好一次。

题解

用并查集维护出每一个连通块，然后统计每一个连通块内有多少个奇点，对答案的贡献应该为max(x/2,1) 需要注意的一点是如果有一个点自己是一个连通块的话对答案的贡献应该为0 口胡一下感觉可以用有上下界的最小流做，然后一看数据范围跑不出来…

代码

#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> #include<cmath> using namespace std; #define N 100005 int n,m,ans; int f[N],du[N],cnt[N]; void clear() { ans=0; memset(du,0,sizeof(du)); memset(cnt,0,sizeof(cnt)); } int find(int x) { if (x==f[x]) return x; f[x]=find(f[x]); return f[x]; } void merge(int x,int y) { int f1=find(x),f2=find(y); if (f1!=f2) f[f1]=f2; } int main() { while (~scanf("%d%d",&n,&m)) { clear(); for (int i=1;i<=n;++i) f[i]=i; for (int i=1;i<=m;++i) { int x,y;scanf("%d%d",&x,&y); merge(x,y); ++du[x],++du[y]; } for (int i=1;i<=n;++i) if (du[i]&1) ++cnt[find(i)]; for (int i=1;i<=n;++i) if (find(i)==i&&du[i]) ans+=max(1,cnt[i]/2); printf("%d\n",ans); } }