TIOJ 1204 E.魔法部的任務 [Matching]

17    75514    poao899    1004K    8203MS    G++     0.79K     2010-04-17 21:12:26                       .


DAG 最小路徑覆蓋 == 最大匹配




















//***************************************

#include<stdio.h>
int T, n, match[1010], cnt, p[1010][2], t[1010];
bool vst[1010], con[1010][1010];
inline int abs(int a, int b){return a>b? a-b: b-a;}
bool aug(int now){
    if(vst[now]) return 0;
    vst[now]= 1;
    for(int i=1; i<=n; i++)
        if(con[now][i]){
            if(match[i]==-1|| aug(match[i])){
                match[i]= now;
                return 1;
            }
        }
    return 0;
}
int main(){
    scanf("%d", &T);
    while(T--){
        scanf("%d", &n);
        cnt= 0;
        for(int i=1; i<=n; i++){
            scanf("%d%d%d", &t[i], &p[i][0], &p[i][1]);
            match[i]= -1;
        }
        for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++)
                con[i][j]= (i!=j)&& (abs(p[i][0], p[j][0])+ abs(p[i][1], p[j][1])+ t[i]<= t[j]);

        for(int i=1; i<=n; i++){
            for(int j=1; j<=n; j++) vst[j]= 0;
            if(aug(i)) cnt++;
        }
        printf("%d\n", n-cnt);
    }
}