UVa 二分圖匹配 Examples

這些都是劉汝佳的算法訓練指南上的例題，基本包括了常見的幾種二分圖匹配的算法。

二分圖是這樣一個圖，頂點分成兩個不相交的集合X , Y中，其中同一個集合中沒有邊，所有的邊關聯在兩個集合中。

給定一個二分圖G，在G的一個子圖M中，M的邊集中的任意兩條邊都不依附於同一個頂點，則稱M是一個匹配。

最大匹配：包含邊數最多的匹配。

最小點覆蓋 = 最大匹配數         最大獨立集 = N - 最大匹配數 (與最小點覆蓋互補)

最小路徑覆蓋 = N - 最大匹配數

UVa 1411 - Ants

問題可以轉化成求最小權完美匹配，權值為黑點到白點的歐幾裡得距離。KM算法

[cpp]
/* **********************************************
Author      : JayYe
Created Time: 2013-8-17 18:06:01
File Name   : zzz.cpp
 *********************************************** */ 
 
#include <stdio.h>  
#include <string.h>  
#include <math.h>  
#include <algorithm>  
using namespace std; 
 
const double eps = 1e-6; 
 
const int maxn = 100; 
 
struct Point{ 
    int x, y; 
}a[maxn+10]; 
 
bool S[maxn+10], T[maxn+10]; // S表示在左邊集合，T表示在右邊集合  
double lx[maxn+10], ly[maxn+10], slack[maxn+10], w[maxn+10][maxn+10]; // 利用slack來松弛，時間復雜度降到O(n^3)  
int match[maxn+10], n; 
 
bool dfs(int u) { 
    S[u] = 1; 
    for(int i = 1;i <= n; i++) if(!T[i]) 
        if(slack[i] - (w[u][i] - lx[u] - ly[i]) > eps) 
            slack[i] = w[u][i] - lx[u] - ly[i]; 
    for(int i = 1;i <= n; i++) if(fabs(w[u][i] - lx[u] - ly[i]) < eps && !T[i]) { 
        T[i] = 1; 
        if(!match[i] || dfs(match[i])) { 
            match[i] = u; 
            return true; 
        } 
    } 
    return false; 
} 
 
void update() { 
    double delta = 1<<30; 
    for(int i = 1;i <= n; i++) if(!T[i] && delta - slack[i] > eps) 
        delta = slack[i]; 
    for(int i = 1;i <= n; i++) { 
        if(S[i])    lx[i] += delta; 
        if(T[i])    ly[i] -= delta; 
    } 
} 
 
void KM() { 
    int i, j; 
    for(i = 1;i <= n; i++) { 
        lx[i] = 1<<30; 
        ly[i] = match[i] = 0; 
        // 與最大權完美匹配不同，最小權初始lx應該設為最小，每次update有最小增  
        for(j = 1;j <= n; j++) if(lx[i] - w[i][j] > eps) 
            lx[i] = w[i][j]; 
    } 
    
    for(i = 1;i <= n; i++) { 
        while(true) { 
            for(j = 1;j <= n; j++)  S[j] = T[j] = 0 , slack[j] = 1<<30; 
            if(dfs(i))  break; 
            else    update(); 
        } 
    } 
} 
 
void solve() { 
    int i, j, x, y; 
    for(i = 1;i <= n; i++)   scanf("%d%d", &a[i].x, &a[i].y); 
    for(i = 1;i <= n ;i++) { 
        scanf("%d%d", &x, &y); 
        for(j = 1;j <= n; j++) 
            w[i][j] = sqrt((a[j].x - x)*(a[j].x - x) + (a[j].y - y)*(a[j].y - y)); 
    } 
    KM(); 
    for(i = 1;i <= n; i++) printf("%d\n", match[i]); 
} 
 
int main() { 
    while(scanf("%d", &n) != -1) { 
        solve(); 
    } 
    return 0; 
} 

/* **********************************************
Author      : JayYe
Created Time: 2013-8-17 18:06:01
File Name   : zzz.cpp
 *********************************************** */

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
using namespace std;

const double eps = 1e-6;

const int maxn = 100;

struct Point{
    int x, y;
}a[maxn+10];

bool S[maxn+10], T[maxn+10]; // S表示在左邊集合，T表示在右邊集合
double lx[maxn+10], ly[maxn+10], slack[maxn+10], w[maxn+10][maxn+10]; // 利用slack來松弛，時間復雜度降到O(n^3)
int match[maxn+10], n;

bool dfs(int u) {
    S[u] = 1;
    for(int i = 1;i <= n; i++) if(!T[i])
        if(slack[i] - (w[u][i] - lx[u] - ly[i]) > eps)
            slack[i] = w[u][i] - lx[u] - ly[i];
    for(int i = 1;i <= n; i++) if(fabs(w[u][i] - lx[u] - ly[i]) < eps && !T[i]) {
        T[i] = 1;
        if(!match[i] || dfs(match[i])) {
            match[i] = u;
            return true;
        }
    }
    return false;
}

void update() {
    double delta = 1<<30;
    for(int i = 1;i <= n; i++) if(!T[i] && delta - slack[i] > eps)
        delta = slack[i];
    for(int i = 1;i <= n; i++) {
        if(S[i])    lx[i] += delta;
        if(T[i])    ly[i] -= delta;
    }
}

void KM() {
    int i, j;
    for(i = 1;i <= n; i++) {
        lx[i] = 1<<30;
        ly[i] = match[i] = 0;
        // 與最大權完美匹配不同，最小權初始lx應該設為最小，每次update有最小增
        for(j = 1;j <= n; j++) if(lx[i] - w[i][j] > eps)
            lx[i] = w[i][j];
    }
  
    for(i = 1;i <= n; i++) {
        while(true) {
            for(j = 1;j <= n; j++)  S[j] = T[j] = 0 , slack[j] = 1<<30;
            if(dfs(i))  break;
            else    update();
        }
    }
}

void solve() {
    int i, j, x, y;
    for(i = 1;i <= n; i++)   scanf("%d%d", &a[i].x, &a[i].y);
    for(i = 1;i <= n ;i++) {
        scanf("%d%d", &x, &y);
        for(j = 1;j <= n; j++)
            w[i][j] = sqrt((a[j].x - x)*(a[j].x - x) + (a[j].y - y)*(a[j].y - y));
    }
    KM();
    for(i = 1;i <= n; i++) printf("%d\n", match[i]);
}

int main() {
    while(scanf("%d", &n) != -1) {
        solve();
    }
    return 0;
}

UVa 11383 - Golden Tiger Claw
有n*n的格子，每個格子有w(i, j)，現在給每行確定一個整數row(i) ，每列確定一個整數col(i)，使得所有w(i, j) <= row(i) + col(j)。
其實這樣就相當於利用KM算法求最大權完美匹配。KM算法實際上最後求出的所有的lx, ly的和是最小的且都滿足lx(i) + ly(j) >= w(i, j)，所以直接用KM算法來求解，這個應用還是挺靈活的。

[cpp]
/* **********************************************
Author      : JayYe
Created Time: 2013-8-17 19:43:54
File Name   : zzz.cpp
*********************************************** */ 
 
#include <stdio.h>  
#include <string.h>  
 
int max(int a, int b) { return  a>b?a:b; } 
int min(int a, int b) { return  a>b?b:a; } 
 
const int maxn = 500; 
 
int n, match[maxn+10], lx[maxn+10], ly[maxn+10], slack[maxn+10], w[maxn+10][maxn+10]; 
bool S[maxn+10], T[maxn+10]; 
 
bool dfs(int i) { 
    S[i] = 1; 
    for(int j = 1;j <= n; j++) if(!T[j]) 
        slack[j] = min(slack[j], lx[i] + ly[j] - w[i][j]); 
    for(int j = 1;j <= n; j++) if(w[i][j] == lx[i] + ly[j] && !T[j]) { 
        T[j] = 1; 
        if(!match[j] || dfs(match[j])) { 
            match[j] = i; 
            return true; 
        } 
    } 
    return false; 
} 
 
void update() { 
    int delta = 1<<30; 
    for(int i = 1;i <= n ;i++) if(!T[i]) 
        delta = min(delta, slack[i]); 
    for(int i = 1;i <= n; i++) { 
        if(S[i])    lx[i] -= delta; 
        if(T[i])    ly[i] += delta; 
    } 
} 
 
void KM() { 
    int i, j; 
    for(i = 1;i <= n; i++) { 
        lx[i] = ly[i] = match[i] = 0; 
        for(j = 1;j <= n; j++) 
            lx[i] = max(lx[i], w[i][j]); 
    } 
    for(i = 1;i <= n; i++) { 
        while(true) { 
            for(j = 1;j <= n; j++)  S[j] = T[j] = 0, slack[j] = 1<<30; 
            if(dfs(i))  break; 
            else    update(); 
        } 
    } 
} 
 
void solve() { 
    int i, j; 
    for(i = 1;i <= n; i++) 
        for(j = 1;j <= n; j++)  scanf("%d", &w[i][j]); 
    KM(); 
    int ans = 0; 
    for(i = 1;i <= n; i++)  printf("%d%c", lx[i], i < n ? ' ' : '\n'), ans += lx[i]; 
    for(i = 1;i <= n; i++)  printf("%d%c", ly[i], i < n ? ' ' : '\n'), ans += ly[i]; 
    printf("%d\n", ans); 
} 
 
int main() { 
    while(scanf("%d", &n) != -1) { 
        solve(); 
    } 
    return 0; 
} 

/* **********************************************
Author      : JayYe
Created Time: 2013-8-17 19:43:54
File Name   : zzz.cpp
*********************************************** */

#include <stdio.h>
#include <string.h>

int max(int a, int b) { return  a>b?a:b; }
int min(int a, int b) { return  a>b?b:a; }

const int maxn = 500;

int n, match[maxn+10], lx[maxn+10], ly[maxn+10], slack[maxn+10], w[maxn+10][maxn+10];
bool S[maxn+10], T[maxn+10];

bool dfs(int i) {
    S[i] = 1;
    for(int j = 1;j <= n; j++) if(!T[j])
        slack[j] = min(slack[j], lx[i] + ly[j] - w[i][j]);
    for(int j = 1;j <= n; j++) if(w[i][j] == lx[i] + ly[j] && !T[j]) {
        T[j] = 1;
        if(!match[j] || dfs(match[j])) {
            match[j] = i;
            return true;
        }
    }
    return false;
}

void update() {
    int delta = 1<<30;
    for(int i = 1;i <= n ;i++) if(!T[i])
        delta = min(delta, slack[i]);
    for(int i = 1;i <= n; i++) {
        if(S[i])    lx[i] -= delta;
        if(T[i])    ly[i] += delta;
    }
}

void KM() {
    int i, j;
    for(i = 1;i <= n; i++) {
        lx[i] = ly[i] = match[i] = 0;
        for(j = 1;j <= n; j++)
            lx[i] = max(lx[i], w[i][j]);
    }
    for(i = 1;i <= n; i++) {
        while(true) {
            for(j = 1;j <= n; j++)  S[j] = T[j] = 0, slack[j] = 1<<30;
            if(dfs(i))  break;
            else    update();
        }
    }
}

void solve() {
    int i, j;
    for(i = 1;i <= n; i++)
        for(j = 1;j <= n; j++)  scanf("%d", &w[i][j]);
    KM();
    int ans = 0;
    for(i = 1;i <= n; i++)  printf("%d%c", lx[i], i < n ? ' ' : '\n'), ans += lx[i];
    for(i = 1;i <= n; i++)  printf("%d%c", ly[i], i < n ? ' ' : '\n'), ans += ly[i];
    printf("%d\n", ans);
}

int main() {
    while(scanf("%d", &n) != -1) {
        solve();
    }
    return 0;
}

UVa 1006 - Fixed Partition Memory Management

大概題意是有n個程序要讓他們在m個內存區域裡運行，一個內存區域不能同時進行兩個程序，但是可以先運行完一個程序再運行下一個。轉換成求最小權匹配，最後輸出有點麻煩。

[cpp]
/* **********************************************
Author      : JayYe
Created Time: 2013-8-18 8:52:59
File Name   : zzz.cpp
 *********************************************** */ 
 
#include <stdio.h>  
#include <string.h>  
#include <algorithm>  
using namespace std; 
 
int max(int a, int b) { return a>b?a:b; } 
int min(int a, int b) { return a>b?b:a; } 
 
int n, m, slack[555], lx[55], ly[555], match[555], w[55][555], mem[22], a[22], t[22]; 
bool S[55], T[555]; 
 
bool dfs(int i) { 
    S[i] = 1; 
    for(int j = 1;j <= n*m; j++) if(!T[j]) 
        slack[j] = min(slack[j], w[i][j] - lx[i] - ly[j]); 
    for(int j = 1;j <= n*m; j++) if(w[i][j] == lx[i] + ly[j] && !T[j]) { 
        T[j] = 1; 
        if(!match[j] || dfs(match[j])) { 
            match[j] = i; 
            return true; 
        } 
    } 
    return false; 
} 
 
void update() { 
    int delta = 1<<30; 
    for(int i = 1;i <= n*m; i++) if(!T[i]) 
        delta = min(delta, slack[i]); 
    for(int i = 1;i <= n; i++) if(S[i])     
        lx[i] += delta; 
    for(int i = 1;i <= n*m; i++) if(T[i]) 
        ly[i] -= delta; 
} 
 
void KM() { 
    int i, j; 
    for(i = 1;i <= n; i++) { 
        lx[i] = 1<<30; 
        for(j = 1;j <= n*m; j++) { 
            lx[i] = min(lx[i], w[i][j]); 
            ly[j] = match[j] = 0; 
        } 
    } 
 
    for(i = 1;i <= n; i++) { 
        while(true) { 
            for(j = 1;j <= n*m; j++)    S[j] = T[j] = 0, slack[j] = 1<<30; 
            if(dfs(i))  break; 
            else    update(); 
        } 
    } 
} 
 
void solve() { 
    for(int i = 1;i <= m; i++)  scanf("%d", &mem[i]); 
    for(int i = 1;i <= n; i++) 
        for(int j = 1;j <= n*m; j++) 
            w[i][j] = 1<<30; 
    for(int i = 1;i <= n; i++) { 
        int k; 
        scanf("%d", &k); 
        for(int j = 1;j <= k; j++)  scanf("%d%d", &a[j], &t[j]); 
        a[k+1] = 1<<30; 
        for(int j = 1;j <= m; j++) { 
            for(int l = 1;l <= k; l++) if(mem[j] >= a[l] && mem[j] < a[l+1]) { 
                for(int ii = 1;ii <= n; ii++) { 
                    w[i][(j-1)*n + ii] = ii*t[l]; 
                } 
            } 
        } 
    }    
 
    KM(); 
} 
 
int main() { 
    int cas = 1; 
    while(scanf("%d%d", &m, &n) != -1) { 
        solve(); 
        printf("Case %d\n", cas++); 
        int ans = 0; 
        for(int i = 1;i <= n; i++)  ans += lx[i]; 
        for(int i = 1;i <= n*m; i++)    ans += ly[i]; 
        printf("Average turnaround time = %.2lf\n", (double)ans/n); 
        
        int from[55], to[55], in[55], sum; // from表示程序從什麼時間開始，to表示結束時間，in表示在哪個內存區域裡運行  
        for(int i = n*m;i >= 1; i--) { 
            if(i%n == 0)    sum = 0; 
            if(match[i]) { 
                int tmp = w[match[i]][i]; 
                from[match[i]] = sum; 
                int num = i%n; 
                if(i%n == 0)    num = n; 
                to[match[i]] = sum = tmp/num + sum; 
                in[match[i]] = i/n + 1; 
                if(i%n == 0)    in[match[i]]--; 
            } 
        } 
        for(int i = 1;i <= n; i++) 
            printf("Program %d runs in region %d from %d to %d\n", i, in[i], from[i], to[i]); 
    } 
    return 0; 
} 

/* **********************************************
Author      : JayYe
Created Time: 2013-8-18 8:52:59
File Name   : zzz.cpp
 *********************************************** */

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

int max(int a, int b) { return a>b?a:b; }
int min(int a, int b) { return a>b?b:a; }

int n, m, slack[555], lx[55], ly[555], match[555], w[55][555], mem[22], a[22], t[22];
bool S[55], T[555];

bool dfs(int i) {
    S[i] = 1;
    for(int j = 1;j <= n*m; j++) if(!T[j])
        slack[j] = min(slack[j], w[i][j] - lx[i] - ly[j]);
    for(int j = 1;j <= n*m; j++) if(w[i][j] == lx[i] + ly[j] && !T[j]) {
        T[j] = 1;
        if(!match[j] || dfs(match[j])) {
            match[j] = i;
            return true;
        }
    }
    return false;
}

void update() {
    int delta = 1<<30;
    for(int i = 1;i <= n*m; i++) if(!T[i])
        delta = min(delta, slack[i]);
    for(int i = 1;i <= n; i++) if(S[i])   
        lx[i] += delta;
    for(int i = 1;i <= n*m; i++) if(T[i])
        ly[i] -= delta;
}

void KM() {
    int i, j;
    for(i = 1;i <= n; i++) {
        lx[i] = 1<<30;
        for(j = 1;j <= n*m; j++) {
            lx[i] = min(lx[i], w[i][j]);
            ly[j] = match[j] = 0;
        }
    }

    for(i = 1;i <= n; i++) {
        while(true) {
            for(j = 1;j <= n*m; j++)    S[j] = T[j] = 0, slack[j] = 1<<30;
            if(dfs(i))  break;
            else    update();
        }
    }
}

void solve() {
    for(int i = 1;i <= m; i++)  scanf("%d", &mem[i]);
    for(int i = 1;i <= n; i++)
        for(int j = 1;j <= n*m; j++)
            w[i][j] = 1<<30;
    for(int i = 1;i <= n; i++) {
        int k;
        scanf("%d", &k);
        for(int j = 1;j <= k; j++)  scanf("%d%d", &a[j], &t[j]);
        a[k+1] = 1<<30;
        for(int j = 1;j <= m; j++) {
            for(int l = 1;l <= k; l++) if(mem[j] >= a[l] && mem[j] < a[l+1]) {
                for(int ii = 1;ii <= n; ii++) {
                    w[i][(j-1)*n + ii] = ii*t[l];
                }
            }
        }
    }  

    KM();
}

int main() {
    int cas = 1;
    while(scanf("%d%d", &m, &n) != -1) {
        solve();
        printf("Case %d\n", cas++);
        int ans = 0;
        for(int i = 1;i <= n; i++)  ans += lx[i];
        for(int i = 1;i <= n*m; i++)    ans += ly[i];
        printf("Average turnaround time = %.2lf\n", (double)ans/n);
      
        int from[55], to[55], in[55], sum; // from表示程序從什麼時間開始，to表示結束時間，in表示在哪個內存區域裡運行
        for(int i = n*m;i >= 1; i--) {
            if(i%n == 0)    sum = 0;
            if(match[i]) {
                int tmp = w[match[i]][i];
                from[match[i]] = sum;
                int num = i%n;
                if(i%n == 0)    num = n;
                to[match[i]] = sum = tmp/num + sum;
                in[match[i]] = i/n + 1;
                if(i%n == 0)    in[match[i]]--;
            }
        }
        for(int i = 1;i <= n; i++)
            printf("Program %d runs in region %d from %d to %d\n", i, in[i], from[i], to[i]);
    }
    return 0;
}

UVa 11419 - SAM I AM

最小點覆蓋， 求出最大匹配後，最後要找到最小的點覆蓋集。最小的點覆蓋集的尋找過程，先從右邊的非匹配點出發找交錯路，並把路徑上的點都標記下，最後的點覆蓋集就是左邊的標記了的頂點加上右邊未標記的匹配點。

[html]
/* ********************************************** 
Author      : JayYe 
Created Time: 2013-8-18 11:10:00 
File Name   : zzz.cpp 
 *********************************************** */ 
 
#include <stdio.h> 
#include <string.h> 
#include <algorithm> 
using namespace std; 
 
const int maxn = 1000+10; 
 
bool mp[maxn][maxn], vis[maxn]; 
int match[maxn], markl[maxn], markr[maxn], right[maxn], n, m; 
 
// 求最大匹配數 
bool dfs(int i) { 
    for(int j = 1;j <= m; j++) if(mp[i][j] && !vis[j]) { 
        vis[j] = 1; 
        if(!match[j] || dfs(match[j])) { 
            match[j] = i; 
            return true; 
        } 
    } 
    return false; 
} 
// 交錯路尋找點覆蓋集 
void findmin(int i) { 
    markr[i] = 1; 
    for(int j = 1;j <= n; j++) if(mp[j][i] && !markl[j]) { 
        markl[j] = 1; 
        if(right[j]) { 
            findmin(right[j]); 
        } 
    } 
} 
 
int main() { 
    int k, i, j, x, y; 
    while(scanf("%d%d%d", &n, &m, &k) != -1 && n) { 
        for(i = 1;i <= n; i++) 
            for(j = 1;j <= m; j++) 
                mp[i][j] = 0; 
        while(k--) { 
            scanf("%d%d", &x, &y); 
            mp[x][y] = 1; 
        } 
        int ans = 0; 
        for(i = 1;i <= m; i++)  match[i] = 0; 
        for(i = 1;i <= n; i++) { 
            for(j = 1;j <= m; j++)  vis[j] = 0; 
            if(dfs(i))  ans++; 
        } 
        printf("%d", ans); 
        for(i = 1;i <= n; i++)  markl[i] = markr[i] = right[i] = 0; 
        for(i = 1;i <= m; i++) if(match[i]) 
            right[match[i]] = i; 
        for(i = 1;i <= m; i++) if(!match[i]){ 
            findmin(i); 
        } 
        //左邊標記過的匹配點 
        for(i = 1;i <= n; i++) if(markl[i]) printf(" r%d", i); 
        //右邊未標記的匹配點 
        for(i = 1;i <= m; i++) if(match[i] && !markr[i])　 printf(" c%d", i); puts("");  
    }  
    return 0; 
} 

/* **********************************************
Author      : JayYe
Created Time: 2013-8-18 11:10:00
File Name   : zzz.cpp
 *********************************************** */

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

const int maxn = 1000+10;

bool mp[maxn][maxn], vis[maxn];
int match[maxn], markl[maxn], markr[maxn], right[maxn], n, m;

// 求最大匹配數
bool dfs(int i) {
    for(int j = 1;j <= m; j++) if(mp[i][j] && !vis[j]) {
        vis[j] = 1;
        if(!match[j] || dfs(match[j])) {
            match[j] = i;
            return true;
        }
    }
    return false;
}
// 交錯路尋找點覆蓋集
void findmin(int i) {
    markr[i] = 1;
    for(int j = 1;j <= n; j++) if(mp[j][i] && !markl[j]) {
        markl[j] = 1;
        if(right[j]) {
            findmin(right[j]);
        }
    }
}

int main() {
    int k, i, j, x, y;
    while(scanf("%d%d%d", &n, &m, &k) != -1 && n) {
        for(i = 1;i <= n; i++)
            for(j = 1;j <= m; j++)
                mp[i][j] = 0;
        while(k--) {
            scanf("%d%d", &x, &y);
            mp[x][y] = 1;
        }
        int ans = 0;
        for(i = 1;i <= m; i++)  match[i] = 0;
        for(i = 1;i <= n; i++) {
            for(j = 1;j <= m; j++)  vis[j] = 0;
            if(dfs(i))  ans++;
        }
        printf("%d", ans);
        for(i = 1;i <= n; i++)  markl[i] = markr[i] = right[i] = 0;
        for(i = 1;i <= m; i++) if(match[i])
            right[match[i]] = i;
        for(i = 1;i <= m; i++) if(!match[i]){
            findmin(i);
        }
        //左邊標記過的匹配點
        for(i = 1;i <= n; i++) if(markl[i]) printf(" r%d", i);
        //右邊未標記的匹配點
        for(i = 1;i <= m; i++) if(match[i] && !markr[i])　 printf(" c%d", i); puts("");
    }
    return 0;
}

UVa 12083 - Guardian of Decency

最大獨立集，根據男女劃分為二分圖，求最大匹配數，結果就是總數減去最大匹配數。
wrong answer注意有一個地方，身高的條件不是至少相差40厘米，而是身高相差大於40厘米。

[html]
/* ********************************************** 
Author      : JayYe 
Created Time: 2013-8-18 13:26:39 
File Name   : zzz.cpp 
*********************************************** */ 
 
#include <stdio.h> 
#include <string.h> 
#include <algorithm> 
using namespace std; 
 
const int maxn = 500+5; 
 
struct PP { 
    int h; 
    char music[111],sport[111]; 
}boy[maxn], girl[maxn], tmp; 
 
int n, m, match[maxn]; 
bool vis[maxn], mp[maxn][maxn]; 
 
bool dfs(int i) { 
    for(int j = 1;j <= m; j++) if(mp[i][j] && !vis[j]) { 
        vis[j] = 1; 
        if(!match[j] || dfs(match[j])) { 
            match[j] = i; 
            return true; 
        } 
    } 
    return false; 
} 
 
char sex[2], music[111], sport[111]; 
int main() { 
    int t, i, j; 
    scanf("%d", &t); 
    while(t--) { 
        scanf("%d", &n); 
        int n1 = 0, n2 = 0, h; 
        for(i = 1;i <= n; i++) { 
            scanf("%d%s%s%s", &tmp.h, sex, tmp.music, tmp.sport); 
            if(sex[0] == 'M')   boy[++n1] = tmp; 
            else    girl[++n2] = tmp; 
        } 
        n = n1, m = n2; 
        for(i = 1;i <= n; i++) { 
            for(j = 1;j <= m; j++) { 
                if(abs(boy[i].h - girl[j].h) <= 40 && strcmp(boy[i].music, girl[j].music) == 0 && strcmp(boy[i].sport, girl[j].sport) != 0) { 
                    mp[i][j] = 1; 
                } 
                else 
                    mp[i][j] = 0; 
            } 
        } 
        for(i = 1;i <= m; i++)  match[i] = 0; 
        int ans = 0; 
        for(i = 1;i <= n; i++) { 
            for(j = 1;j <= m; j++) vis[j] = 0; 
            if(dfs(i))  ans++; 
        } 
        printf("%d\n", n+m-ans); 
    } 
    return 0; 
} 

/* **********************************************
Author      : JayYe
Created Time: 2013-8-18 13:26:39
File Name   : zzz.cpp
*********************************************** */

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

const int maxn = 500+5;

struct PP {
    int h;
    char music[111],sport[111];
}boy[maxn], girl[maxn], tmp;

int n, m, match[maxn];
bool vis[maxn], mp[maxn][maxn];

bool dfs(int i) {
    for(int j = 1;j <= m; j++) if(mp[i][j] && !vis[j]) {
        vis[j] = 1;
        if(!match[j] || dfs(match[j])) {
            match[j] = i;
            return true;
        }
    }
    return false;
}

char sex[2], music[111], sport[111];
int main() {
    int t, i, j;
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        int n1 = 0, n2 = 0, h;
        for(i = 1;i <= n; i++) {
            scanf("%d%s%s%s", &tmp.h, sex, tmp.music, tmp.sport);
            if(sex[0] == 'M')   boy[++n1] = tmp;
            else    girl[++n2] = tmp;
        }
        n = n1, m = n2;
        for(i = 1;i <= n; i++) {
            for(j = 1;j <= m; j++) {
                if(abs(boy[i].h - girl[j].h) <= 40 && strcmp(boy[i].music, girl[j].music) == 0 && strcmp(boy[i].sport, girl[j].sport) != 0) {
                    mp[i][j] = 1;
                }
                else
                    mp[i][j] = 0;
            }
        }
        for(i = 1;i <= m; i++)  match[i] = 0;
        int ans = 0;
        for(i = 1;i <= n; i++) {
            for(j = 1;j <= m; j++) vis[j] = 0;
            if(dfs(i))  ans++;
        }
        printf("%d\n", n+m-ans);
    }
    return 0;
}
UVa 1201 - Taxi Cab Scheme

最小路徑覆蓋，在圖上找盡量少的路徑使得每個結點恰好在一條路徑上(換句話說， 不同的路徑不能有公共點)。單獨的結點也看做一條路徑。

[html]
/* ********************************************** 
Author      : JayYe 
Created Time: 2013-8-18 14:08:39 
File Name   : zzz.cpp 
*********************************************** */ 
 
#include <stdio.h> 
#include <string.h> 
#include <algorithm> 
using namespace std; 
 
const int maxn = 500+10; 
 
struct TAXI { 
    int time, x1, y1, x2, y2; 
}a[maxn]; 
 
int n, match[maxn]; 
bool vis[maxn], mp[maxn][maxn]; 
 
bool dfs(int i) { 
    for(int j = 1;j <= n; j++) if(mp[i][j] && !vis[j]) { 
        vis[j] = 1; 
        if(!match[j] || dfs(match[j])) { 
            match[j] = i; 
            return true; 
        } 
    } 
    return false; 
} 
 
int main() { 
    int i, j, t; 
    scanf("%d", &t); 
    while(t--) { 
        scanf("%d", &n); 
        for(i = 1;i <= n; i++) { 
            int hour, minute; 
            scanf("%d:%d%d%d%d%d", &hour, &minute, &a[i].x1, &a[i].y1, &a[i].x2, &a[i].y2); 
            a[i].time = hour*60 + minute; 
            // 直接把時間全部轉換成分鐘，這樣更好判斷了。 
        } 
        for(i = 1;i <= n; i++) { 
            mp[i][i] = 0; 
            int time = a[i].time; 
            for(j = 1;j <= n; j++) if(j != i) { 
                int ti = time + abs(a[i].x1 - a[i].x2) + abs(a[i].y1 - a[i].y2); 
                ti += abs(a[i].x2 - a[j].x1) + abs(a[i].y2 - a[j].y1); 
                if(ti < a[j].time) 
                    mp[i][j] = 1; 
                else 
                    mp[i][j] = 0; 
            } 
        } 
 
        for(i = 1;i <= n; i++)  match[i] = 0; 
        int ans = 0; 
        for(i = 1;i <= n; i++) { 
            for(j = 1;j <= n; j++)  vis[j] = 0; 
            if(dfs(i))  ans++; 
        } 
        printf("%d\n", n - ans); 
    } 
    return 0; 
} 

/* **********************************************
Author      : JayYe
Created Time: 2013-8-18 14:08:39
File Name   : zzz.cpp
*********************************************** */

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

const int maxn = 500+10;

struct TAXI {
    int time, x1, y1, x2, y2;
}a[maxn];

int n, match[maxn];
bool vis[maxn], mp[maxn][maxn];

bool dfs(int i) {
    for(int j = 1;j <= n; j++) if(mp[i][j] && !vis[j]) {
        vis[j] = 1;
        if(!match[j] || dfs(match[j])) {
            match[j] = i;
            return true;
        }
    }
    return false;
}

int main() {
    int i, j, t;
    scanf("%d", &t);
    while(t--) {
        scanf("%d", &n);
        for(i = 1;i <= n; i++) {
            int hour, minute;
            scanf("%d:%d%d%d%d%d", &hour, &minute, &a[i].x1, &a[i].y1, &a[i].x2, &a[i].y2);
            a[i].time = hour*60 + minute;
            // 直接把時間全部轉換成分鐘，這樣更好判斷了。
        }
        for(i = 1;i <= n; i++) {
            mp[i][i] = 0;
            int time = a[i].time;
            for(j = 1;j <= n; j++) if(j != i) {
                int ti = time + abs(a[i].x1 - a[i].x2) + abs(a[i].y1 - a[i].y2);
                ti += abs(a[i].x2 - a[j].x1) + abs(a[i].y2 - a[j].y1);
                if(ti < a[j].time)
                    mp[i][j] = 1;
                else
                    mp[i][j] = 0;
            }
        }

        for(i = 1;i <= n; i++)  match[i] = 0;
        int ans = 0;
        for(i = 1;i <= n; i++) {
            for(j = 1;j <= n; j++)  vis[j] = 0;
            if(dfs(i))  ans++;
        }
        printf("%d\n", n - ans);
    }
    return 0;
}