类似于这道题的题似乎以前多面体在codevs月赛里出过
不管怎么动 处在同一列的格子总是处在同一列 行同理 则问题转化成要找到一些黑格子 其中任意两个都不在同一行或同一列
把行号看成二分图的一部 列看成另一部 那么就变成了一个二分图匹配的问题 对于每一个f[i][j]是黑的 我们连边(i,j),之后匈牙利算法(不会的百度一下或者问学长)搞一下就好了
我在打匈牙利算法的时候 忘记在每一轮的匹配中加上这一轮匹配是否用过的标记 于是就wa了……
还有注意边的数比较多……
#include <cstdio> #include <algorithm> #include <cstring> using namespace std; const int N=41000; int e[N],pre[N],now[N],T,n,tail,to[N],from[N],vis[N],tmp; bool flag; void add(int u,int v){e[++tail]=v;pre[tail]=now[u];now[u]=tail;} bool hungary(int a){ for(int i=now[a];i;i=pre[i]){ if(vis[e[i]]) continue;else vis[e[i]]=1; if(!from[e[i]] || hungary(from[e[i]])) {from[e[i]]=a,to[a]=e[i];return true;} } return false; } int main(){ freopen("1059.in","r",stdin);freopen("1059.out","w",stdout); scanf("%d",&T); while(T--){ scanf("%d",&n); memset(e,0,sizeof(e)); memset(pre,0,sizeof(pre)); memset(now,0,sizeof(now)); memset(to,0,sizeof(to)); memset(from,0,sizeof(from)); tail=0;flag=1; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++){ scanf("%d",&tmp); if(tmp) add(i,j); } for(int i=1;i<=n;i++){ memset(vis,0,sizeof(vis)); if(!hungary(i)) {flag=0;break;} } printf(flag?"Yes\n":"No\n"); } return 0; }