[HOJ 402] 扶養權分配問題

作法：

首先把每個蘿莉隨便丟給其中一個人，那麼現在會得到每個人有某個特定個數的蘿莉，並且如果一個蘿莉可以被分給 A 和 B ，那麼當我們把蘿莉分給另外一個人的時候，會同時改變 A 和 B 擁有的蘿莉數的奇偶性，所以這樣就可以等價成另一個問題：有一張圖，每個點有一個權重（1或是0），並且對於每一條邊，都可以同時對兩端點 xor 1 ，而目標是要讓權值為 1 的點越少越好。而在最後改完權值之後，如果某個 A 還是奇點，那麼就多加一個蘿莉，把他分給 A 就好了。而對於等價後的問題，首先對每個連通塊分開看，對於每個連通塊，首先可以觀察出改完權值之後可以讓奇點數量 <= 1 ，因為如果還有兩個奇點，那麼隨便找一條連接他們的路徑，把路徑上的所有邊的兩端點都 xor 1 ，就可以把兩個奇點消掉了。而構造其實不難，只要隨便找一個這個連通塊的生成樹，從底下開始把所有的奇點都對他和他的祖先 xor，這樣奇點就可以全部往上丟了。並且因為奇點的個數奇偶性不會變，所以原本如果有奇數個奇點，最後就會剩一個奇點在根。最後要注意到，如果一個蘿莉分給的兩個人是同一個人，那就不要在新的圖中建這條邊了，因為他沒有「交換」的動作，而他也只有一種分法，所以就不理他就好了。


code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10,maxm=200000+10 ; ;
 
struct P{int x,y;};
vector<P> edge,ans ;
vector<int> v[maxn] ;
int val[maxn] ;
void change(int id)
{
    swap(edge[id].x,edge[id].y) ;
    val[edge[id].x]++ ;
    val[edge[id].y]++ ;
}
 
bool vis[maxn] ;
void dfs(int x)
{
    vis[x]=1 ;
    for(auto i : v[x])
    {
        int to= edge[i].x==x ? edge[i].y : edge[i].x ;
        if(vis[to]) continue ;
        dfs(to) ;
        if(val[to]%2) change(i) ;
    }
}
 
main()
{
    int n,m ;
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        for(int i=1;i<=n;i++) v[i].clear() ;
        ans.clear() ; edge.clear() ;
        fill(val+1,val+n+1,0) ;
        fill(vis+1,vis+n+1,0) ;
        while(m--)
        {
            int x,y ; scanf("%d%d",&x,&y) ;
            if(x==y) { val[x]++ ; ans.push_back((P){x,x}) ; continue ; }
            edge.push_back((P{x,y})) ; val[x]++ ;
            int sz=edge.size() ;
            v[x].push_back(sz-1) ; v[y].push_back(sz-1) ;
        }
 
        for(int i=1;i<=n;i++) if(!vis[i])
        {
            dfs(i) ;
            if(val[i]%2) ans.push_back((P){i,i}) ;
        }
        printf("%d\n",ans.size()+edge.size()) ;
        for(auto i : ans) printf("%d %d\n",i.x,i.y) ;
        for(auto i : edge) printf("%d %d\n",i.x,i.y) ;
    }
}