BZOJ 1305 跳舞

注意：

1.既然有两种舞，不如每个人拆两个点。

2.不能每次补1的流量，那样会具有贪心的效果（能流则流）无法达到最优。

  因此只能枚举，每次求最大流。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define maxn 60
#define maxv 550
#define maxe 1000050
#define inf 1000000007
using namespace std;
int n,k,map[maxn][maxn],g[maxv],nume=1,dis[maxv],s,t;
struct edge
{
    int v,f,nxt;
}e[maxe];
char ss[maxn];
queue <int> q;
void addedge(int u,int v,int f)
{
    e[++nume].v=v;e[nume].f=f;e[nume].nxt=g[u];g[u]=nume;
    e[++nume].v=u;e[nume].f=0;e[nume].nxt=g[v];g[v]=nume;
}
void build()
{
    s=0;t=6*n+1;
    for (int i=1;i<=n;i++)
    {
        addedge(s,i,1);
        addedge(i,n+i,inf);addedge(i,2*n+i,k);
        addedge(3*n+i,5*n+i,inf);addedge(4*n+i,5*n+i,k);
        addedge(5*n+i,t,1);
    }
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++)
        {
            if (map[i][j]) addedge(n+i,3*n+j,1);
            else addedge(2*n+i,4*n+j,1);
        }
}
void rebuild(int x)
{
    for (int i=g[s];i;i=e[i].nxt) {e[i].f=x;e[i^1].f=0;}
    for (int i=g[t];i;i=e[i].nxt) {e[i^1].f=x;e[i].f=0;}
    for (int i=2;i<=nume;i+=2)
    {
        e[i].f+=e[i^1].f;
        e[i^1].f=0;
    }
}
bool bfs()
{
    while (!q.empty()) q.pop();
    for (int i=s;i<=t;i++) dis[i]=inf;
    dis[s]=0;q.push(s);
    while (!q.empty())
    {
        int head=q.front();q.pop();
        for (int i=g[head];i;i=e[i].nxt)
        {
            int v=e[i].v;
            if ((dis[v]==inf) && (e[i].f))
            {
                dis[v]=dis[head]+1;
                q.push(v);
            }
        }
    }
    if (dis[t]==inf) return false;
    return true;
}
int dinic(int x,int low)
{
    if (x==t) return low;
    int ret=0;
    for (int i=g[x];low && i;i=e[i].nxt)
    {
        int v=e[i].v;
        if ((e[i].f) && (dis[v]==dis[x]+1))
        {
            int dd=dinic(v,min(low,e[i].f));
            ret+=dd;low-=dd;
            e[i].f-=dd;e[i^1].f+=dd;
        }
    }
    if (!ret) dis[x]=inf;
    return ret;
}
int main()
{
    scanf("%d%d",&n,&k);
    for (int i=1;i<=n;i++)
    {
        scanf("%s",ss);
        for (int j=0;j<n;j++)
            if (ss[j]=='Y') map[i][j+1]=1;
    }        
    build();int ret,i;
    for (i=1;;i++)
    {
        ret=0;rebuild(i);
        while (bfs())
            ret+=dinic(s,inf);
        if (ret<i*n) break;
    }
    printf("%d
",i-1);
    return 0;
}