首页 > 代码库 > 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 矩阵游戏
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。