[BZOJ1059][ZJOI2007]矩阵游戏 二分图最大匹配



事实上,本题等价于询问是否能够找出n个不同行不同列的点.二分图匹配完事了.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 520
#define M 233333
using namespace std;
int T,n,s,t,head[N],to[M],nxt[M],f[M],tot=1;
inline void add(int x,int y,int z)
{
    to[++tot]=y;nxt[tot]=head[x];head[x]=tot;f[tot]=z;
    to[++tot]=x;nxt[tot]=head[y];head[y]=tot;f[tot]=0;
}
void init()
{
    s=0,t=n*2+1;
    memset(head,0,sizeof head);
    memset(nxt,0,sizeof nxt);
    tot=1;
}
int q[N],l,r,dis[N];
bool bfs()
{
    l=1,r=0;
    memset(dis,-1,sizeof dis);
    q[++r]=s;dis[s]=0;
    int x,i,y;
    while(l<=r)
    {
        x=q[l++];
        for(i=head[x];i;i=nxt[i])
        {
            y=to[i];
            if(dis[y]<0&&f[i]>0)
            {
                dis[y]=dis[x]+1;
                if(y==t)return 1;
                q[++r]=y;
            }
        }
    }
    return 0;
}
int dinic(int x,int flow)
{
    if(x==t)return flow;
    int a,temp=flow;
    for(int i=head[x];i;i=nxt[i])if(dis[to[i]]==dis[x]+1&&f[i]>0)
    {
        a=dinic(to[i],min(temp,f[i]));
        if(!a)dis[to[i]]=-1;
        temp-=a,f[i]-=a,f[i^1]+=a;
        if(!temp)return flow;
    }
    return flow-temp;
}
int maxflow()
{
    int re=0;
    while(bfs())re+=dinic(s,1<<30);
    return re;
}
int main()
{
    cin>>T;
    while(T--)
    {
        scanf("%d",&n);
        init();
        for(int x,j,i=1;i<=n;++i)
        {
            add(s,i,1);
            add(i+n,t,1);
            for(j=1;j<=n;++j)
            {
                scanf("%d",&x);
                if(x)add(i,j+n,1);
            }
        }
        if(maxflow()>=n)puts("Yes");
        else puts("No");
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注