【HNOI2016模拟3.26】A

Description

给出n个球，m个筐子。每个球可以放在第ai个或者第bi个筐子里。求最少有多少个筐子里有奇数个球，和最优情况下的方案数。

n,m<=2*10^5

Solution

我们运用调整法解决这道题。

我们先随便把每个球扔到任意一个筐子里。这样我们就得到了一堆偶数筐和奇数筐。

然后，对于每一个球的方案，它相当于同时改变这两个筐子的奇偶性。

很明显，当我们把它当成一张图连完边后，有偶数个奇数筐的联通块可以通过任意的调整而变成全部为偶数。等于没有。同理，奇数个的也可以调整成只有一个奇数筐，答案为1。

第一问一遍dfs就解决了。

至于输出答案，我们把每个奇数筐都放一个到一个点。dfs树中的root。这相当于把每个奇数筐到root的路径取反。当然，取了两次反等于没取。最后，根据边的情况就知道一种合法方案了。

Code

#include<cstdio>
#include<cstring>
#include<algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define rep(i,a) for(int i=last[a];i;i=next[i])
#define N 200005
using namespace std;
int n,m,l,a[N],x[N],y[N],cnt[N],ans;
int next[N*2],t[N*2],v[N*2],last[N];
bool bz[N];
void add(int x,int y,int z) {
    t[++l]=y;v[l]=z;next[l]=last[x];last[x]=l;
}
int dfs(int x) {
    bz[x]=;int z=a[x]%2;
    rep(i,x) if (!bz[t[i]]) z+=dfs(t[i]);
    return z;
}
int solve(int x) {
    bz[x]=;int z=a[x]%2;
    rep(i,x) if (!bz[t[i]]) {
        int y=solve(t[i]);z+=y;
        cnt[v[i]]=y;
    }
    return z;
}
int main() {
    scanf("%d%d",&n,&m);
    fo(i,,n) {
        scanf("%d%d",&x[i],&y[i]);
        a[x[i]]++;add(x[i],y[i],i);add(y[i],x[i],i);
    }
    fo(i,,m) if (!bz[i]&&dfs(i)%2) ans++;
    printf("%d\n",ans);
    memset(bz,,sizeof(bz));
    fo(i,,m) if (!bz[i]) solve(i);
    fo(i,,n)
        if (cnt[i]%2) printf("%d ",y[i]);
        else printf("%d ",x[i]);
}