BZOJ1305 网络流最大流

BZOJ1305 网络流最大流
分析：建立源点和汇点，将男孩分为喜欢点和不喜欢点，每个男孩喜欢点跟源点连接，权值为要求的答案，女孩跟汇点连接，权值为要求的答案；男孩的喜欢点和男孩的不喜欢点链接，权值为k，女孩的喜欢点和女孩的不喜欢点链接，权值为k；男孩跟喜欢的女孩连接，权值为1，同样男孩不喜欢的女孩链接，权值为1.建完图后二分查找最大答案，用Dinic跑最大流。
网络流最难的部分是建图，图建好了，问题就差不多解决了。

#include <bits/stdc++.h>
using namespace std;
const int N = 250;
int n, k, st, ed, cnt;
struct node{
    int v, w, nxt;
}edge[N * N];
int fir[N], deep[N];
char s[51][51];
inline void add(int u, int v, int w){
    edge[++cnt] = (node){v, w, fir[u]}; fir[u] = cnt;
    edge[++cnt] = (node){u, 0, fir[v]}; fir[v] = cnt;
}
inline int bfs(){
    memset(deep, 0, sizeof(deep));
    deep[st] = 1;
    queue<int> q;
    q.push(st);
    while(!q.empty()){
        int u = q.front();
        q.pop();
        for(int i = fir[u]; i; i = edge[i].nxt){
            int v = edge[i].v;
            if(edge[i].w && !deep[v]){
                deep[v] = deep[u] + 1;
                q.push(v);
            }
        }
    }
//    for(int i = 0; i <= 4 * n + 1; i++){
//        printf("%d ", deep[i]);
//    }
//    printf("
");
    return deep[ed];
}
inline int dfs(int u, int fl){
    if(u == ed || fl == 0) return fl;
    int f = 0;
    for(int i = fir[u]; i; i = edge[i].nxt){
        int v = edge[i].v;
        if(edge[i].w && deep[u] + 1 == deep[v]){
            int x = dfs(v, min(edge[i].w, fl));
            edge[i].w -= x;
            edge[i^1].w += x;
            fl -= x;
            f += x;
        }
    }
    if(!f) deep[u] = -2;
    return f;
}
inline int Dinic(){
    int ans = 0, d;
    while(bfs()){
        while((d = dfs(st, 0x3f3f3f3f))){
            ans += d;
        }
    }
    return ans;
}
//0 源点
//1~n 男孩的喜欢点
//n+1~2*n 男孩的不喜欢点
//2*n+1~3*n 女孩的喜欢点
//3*n+1~4*n 女孩的不喜欢点
//4*n+1 汇点
inline void built(int mid){
    cnt = 1;
    memset(fir, 0, sizeof(fir));
    for(int i = 1; i <= n; i++){
        add(st, i, mid);
        add(i + 2 * n, ed, mid);
        add(i, i + n, k);
        add(i + 3 * n, i + 2 * n, k);
    }
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            if(s[i][j] == 'Y') add(i, j + 2 * n, 1);
            else add(i + n, j + 3 * n, 1);
        }
    }
}
int main(){
#ifdef ONLINE_JUDGE
#else
    freopen("in.txt", "r", stdin);
#endif //ONLINE_JUDGE
    cin>>n>>k;
    for(int i = 1; i <= n; i++){
        scanf("%s", s[i] + 1);
    }
    int l = 1, r = n;
    st = 0, ed = 4 * n + 1;
    while(l <= r){
        int mid = (l + r) / 2;
        //       printf("%d
", mid);
        built(mid);
        if(Dinic() >= n * mid) l = mid + 1;
        else r = mid - 1;
    }
    cout<<l - 1<<"
";
    return 0;
}