1422:Air Raid

keyword

最小パス被覆　C++

概要

ノード数N(<120)のDAGが与えられる。最小パス被覆を計算する問題。
模擬地区予選で類題が出た問題。DAGの最小パス被覆は(u,v)に対してu->v'となるような2部グラフの最大マッチングを頂点数から引けば良い。

int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        for(int i=0; i<300; i++)
            G[i].clear();
        int E;
        scanf("%d%d",&V,&E);
        for(int i=0; i<150; i++)
            for(int j=0; j<150; j++)
                graph[i][j] = false;
        for(int i=0; i<E; i++){
            int x, y;
            scanf("%d%d",&x,&y);
            graph[x-1][y-1] = true;
        }
        for(int i=0; i<V; i++)
            for(int j=0; j<V; j++)
                if(i!=j && graph[i][j])
                    add_edge(i,j+V);
        V *= 2;
        printf("%d\n",(V>>1)-bipartite_matching());
    }
    return 0;
}