【BZOJ 1305】[CQOI2009]dance跳舞

【链接】我是链接,点我呀:)

【题意】

在这里输入题意

【题解】

男生和女生每个人都分身成两个节点
即x[1],x[2]和y[1],y[2]

然后如果i和j不相互喜欢

那么add(x[i][2],y[j][2],1)

如果相互喜欢的话

add(x[i][1],y[j][1],1)

然后对于每个男生

add(x[i][1],y[i][1],k)

对于每个女生

add(y[i][2],y[i][1],k)

然后对于每个男生

add(s,x[i][1],mid)

add(y[i][1],t,mid)

这里的mid是二分的值。

这个mid就是舞会的轮数了。

如果能够满流显然每个人都能配对跳mid支舞

显然是有单调性的。

(然后发现原来的dicnic的模板是错的。。边数的计算要特别careful.

【代码】

#include <bits/stdc++.h>

using namespace std;

const int N = 50;

struct abc{

    int nex,en,flow;

}bian[2][N*N*2+8*N+10];

int n,k,x[N+10][3],y[N+10][3],fir[2][N*4+10],tfir[N*4+10],totm,deep[N*4+10];

int cnt = 0;

bool bo[N+10][N+10];

char s[N+10];

queue<int> dl;

//每个男人分为(x1,x2)

//每个女人分为(y1,y2)

void add(int x,int y,int cost,int i){

    bian[i][totm].nex = fir[i][x];

    fir[i][x] = totm;

    bian[i][totm].en = y,bian[i][totm].flow = cost;

    totm++;

    bian[i][totm].nex = fir[i][y];

    fir[i][y] = totm;

    bian[i][totm].en = x,bian[i][totm].flow = 0;

    totm++;

}

bool bfs(int s,int t){

    dl.push(s);

    memset(deep,255,sizeof deep);

    deep[s] = 0;

    while (!dl.empty()){

        int x = dl.front();

        dl.pop();

        for (int temp = fir[1][x]; temp!= -1 ;temp = bian[1][temp].nex){

            int y = bian[1][temp].en;

            if (deep[y]==-1 && bian[1][temp].flow>0){

                deep[y] = deep[x] + 1;

                dl.push(y);

            }

        }

    }

    return deep[t]!=-1;

}

int dfs(int x,int t,int limit){

    if (x == t) return limit;

    if (limit == 0) return 0;

    int cur,f = 0;

    for (int temp = tfir[x];temp!=-1;temp = bian[1][temp].nex){

        tfir[x] = temp;

        int y = bian[1][temp].en;

        if (deep[y] == deep[x] + 1 && (cur = dfs(y,t,min(limit,bian[1][temp].flow))) ){

            f += cur;

            limit -= cur;

            bian[1][temp].flow -= cur;

            bian[1][temp^1].flow += cur;

            if (!limit) break;

        }

    }

    return f;

}

int get_flow(){

    int now = 0;

    while (bfs(0,cnt)){

        for (int i = 0;i <= cnt;i++) tfir[i] = fir[1][i];

        int xxx = dfs(0,cnt,10000);

        now+=xxx;

    }

    return now;

}

int main(){

    //freopen("F:\\program\\rush\\rush_in.txt","r",stdin);

    ios::sync_with_stdio(0),cin.tie(0);

    memset(fir[0],255,sizeof fir[0]);

    cin >> n >> k;

    for (int i = 1;i <= n;i++){

        cin >> (s+1);

        for (int j = 1;j <= n;j++)

            if (s[j]=='Y'){

                bo[i][j] = 1;

            }

    }

    for (int i = 1;i <= n;i++){

        for (int j = 1;j <= 2;j++)

            x[i][j] = ++cnt;

    }

    for (int i = 1;i <= n;i++)

        for (int j = 1;j <= 2;j++)

            y[i][j] = ++cnt;

    cnt++;

    for (int i = 1;i <= n;i++){

        for (int j = 1;j <= n;j++){

            if (bo[i][j])

                add(x[i][1],y[j][1],1,0);

            else{

                add(x[i][2],y[j][2],1,0);

            }

        }

    }

    for (int i = 1;i <= n;i++){

        add(x[i][1],x[i][2],k,0);

        add(y[i][2],y[i][1],k,0);

    }

    int l = 0,r = n+1,temp1 = 0;

    while (l<=r){

        int i = (l+r)>>1;

        for (int j = 0;j < totm;j++) bian[1][j] = bian[0][j];

        for (int j = 0;j <= cnt;j++) fir[1][j] = fir[0][j];

        int tt = totm;

        for (int j = 1;j <= n;j++){

            add(0,x[j][1],i,1);

            add(y[j][1],cnt,i,1);

        }

        int temp = get_flow();

        if (temp!=i*n){

            r = i-1;

        }else {

            temp1 = i;

            l = i+1;

        }

        totm = tt;

    }

    cout<<temp1<<endl;

    return 0;

}

巴特西

【BZOJ 1305】[CQOI2009]dance跳舞

最新文章

热门文章