bzoj1059 BZOJ 1059矩陣游戲－IT工程師數位筆記本

文章出處

BZOJ 1059矩陣游戲：給定一個大小為N×N的黑白染色矩陣，試判斷能否通過交換行與列使矩陣左上角至右下角這一對角線上所有點均為黑色。

Analysis

易知若幾個黑點原本同行或同列，不管如何變換，它們始終同行或同列。因此我們只需判斷是否存在N個點互不同行，也互不同列。
由此轉化為二分圖模型。對于一個坐標為(i,j)的黑點，由第i行向第j列連邊。若此二分圖存在完美匹配，則可滿足題目要求。
跑網絡流或者使用匈牙利算法均可。

Code

#includeconst int N=205;int t,n,x,ed,ans,v[N*N],nxt[N*N],g[N],f[N];bool b[N];void read(int &x){    char c;    while((c=getchar())<'0' || c>'9');    x=c-'0';    while((c=getchar())>='0' && c<='9') x=x*10+c-'0';}void add(int x,int y){    v[++ed]=y;    nxt[ed]=g[x];    g[x]=ed;}bool find(int x){    for(int i=g[x];i;i=nxt[i]) if(!b[v[i]]){        b[v[i]]=1;        if(!f[v[i]] || find(f[v[i]])) return f[v[i]]=x,1;    }    return 0;}int main(){    read(t);    while(t--){        ed=ans=0;        for(int i=1;i<=n;i++) g[i]=0;        read(n);        for(int i=1;i<=n;i++) for(int j=1;j<=n;j++){            read(x);            if(x) add(i,j);        }        for(int i=1;i<=n;i++) f[i]=0;        for(int i=1;i<=n;i++){            for(int j=1;j<=n;j++) b[j]=0;            if(find(i)) ans++;        }        printf("%s\n",ans==n?"Yes":"No");    }    return 0;}

看文倉www.kanwencang.com網友整理上傳,為您提供最全的知識大全,期待您的分享，轉載請注明出處。
歡迎轉載：http://www.kanwencang.com/bangong/20170210/100177.html

文章列表