首页 > 代码库 > BZOJ 1059 矩阵游戏

BZOJ 1059 矩阵游戏

注意到如果变换前在同一行/列,变换后也在同一行/列。然后二分图匹配。

#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<queue>#define maxn 250#define maxv 550#define maxe 1000050#define inf 2000000000using namespace std;int tt,n,x,nume,g[maxv],dis[maxv],s,t;queue <int> q;struct edge{    int v,f,nxt;}e[maxe];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;}bool bfs(){    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;}void work(){    nume=1;memset(g,0,sizeof(g));    scanf("%d",&n);s=0;t=2*n+1;    for (int i=1;i<=n;i++) {addedge(s,i,1);addedge(i+n,t,1);}    for (int i=1;i<=n;i++)        for (int j=1;j<=n;j++)        {            scanf("%d",&x);            if (x) addedge(i,j+n,1);        }    int max_flow=0;    while (bfs()) max_flow+=dinic(s,inf);    if (max_flow==n) printf("Yes\n");    else printf("No\n");}int main(){    scanf("%d",&tt);    for (int i=1;i<=tt;i++)        work();    return 0;}

 

BZOJ 1059 矩阵游戏