BZOJ1305/Luogu3153 [CQOI2009]dance跳舞 (network flow)

#define T 1001
#define S 0

struct Edge{
    int nxt,pre,w;
}e[500007];
int cntEdge,head[N];
inline void add(int u,int v,int w){
    e[++cntEdge] = (Edge){head[u], v, w}, head[u] = cntEdge;
}

inline void Add(int u,int v,int w){
    add(u, v, w);
    add(v, u, 0);
}

int q[N],h[N];
inline bool BFS(){
    int t = 0, w = 1;
    Fill(h, -1);
    h[0] = 0, q[0] = 0;
    while(t != w){
        int u = q[t++];
        for(register int i = head[u]; i; i =e[i].nxt){
            int v = e[i].pre;
            if(e[i].w && h[v] == -1){
                h[v] = h[u] + 1;
                q[w++] = e[i].pre;
            }
        }
    }
    return h[T] != -1;
}
inline int DFS(int u, int f){
    if(u == T) return f;
    int w, used = 0;
    for(register int i = head[u]; i; i = e[i].nxt){
        int v = e[i].pre;
        if(h[v] == h[u] + 1){
            w = DFS(v, Min(f - used, e[i].w));
            e[i].w -= w, e[i^1].w += w;
            used += w;
            if(used == f) return f;
        }
    }
    if(!used) h[u] = -1;
    return used;
}
inline int Dinic(){
    int sum = 0;
    while(BFS()){
        sum += DFS(0, 0x7fffffff);
    }
    return sum;
}

int n,k,mp[N][N];

inline void Build(int &mid){
    cntEdge=1;
    Fill(head, 0);
    
    R(i,1,n) Add(S, i, mid);
    R(i,1,n) Add(i, i + 500, k);
    R(i,1,n) Add(i + n + 500, i + n, k);
    R(i,1,n) Add(i + n, T, mid);
    R(i,1,n){
        R(j,1,n){
            if(mp[i][j])
                Add(i, n + j, 1);
            else
                Add(i + 500, n + j + 500, 1);
        }
    }
}

int main(){
    io >> n >> k;
    R(i,1,n){
        char str[57];
        scanf("%s", str + 1);
        R(j,1,n)
            mp[i][j] = (str[j] == 'Y');
    }
    
    int maxx = 0;
    int l = 0, r = 50;
    while(l<=r){
        int mid = (l + r) >> 1;
        Build(mid);
        int ans = Dinic();
        if(ans >= n * mid){
            maxx = mid;
            l = mid + 1;
        }
        else
            r = mid - 1;
    }
    
    printf("%d", maxx);
    return 0;
}

https://www.cnblogs.com/images/cnblogs_com/bingoyes/1504306/o_Scene_1.jpg

BZOJ1305/Luogu3153 [CQOI2009]dance跳舞 (network flow)

原文：https://www.cnblogs.com/bingoyes/p/11191623.html