BZOJ 1059: [ZJOI2007]矩阵游戏
2018-06-17 21:02:51来源:未知 阅读 ()
1059: [ZJOI2007]矩阵游戏
Time Limit: 10 Sec Memory Limit: 162 MBSubmit: 5612 Solved: 2707
[Submit][Status][Discuss]
Description
Input
Output
输出文件应包含T行。对于每一组数据,如果该关卡有解,输出一行Yes;否则输出一行No。
Sample Input
2
0 0
0 1
3
0 0 1
0 1 0
1 0 0
Sample Output
Yes
【数据规模】
对于100%的数据,N ≤ 200
HINT
Source
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int maxn=200+5; 4 struct node{ 5 int net; 6 int to; 7 }t[maxn*2*maxn*2]; 8 int head[maxn]; 9 int n,T,ans; 10 int a[maxn][maxn]; 11 bool vis[maxn]; 12 int whi[maxn],p[maxn],cnt; 13 14 inline void add(int i,int j) 15 { 16 t[++cnt].to=j; 17 t[cnt].net=head[i]; 18 head[i]=cnt; 19 } 20 21 bool dfs(int x) 22 { 23 for(int i=head[x];i;i=t[i].net) 24 { 25 int v=t[i].to; 26 if(!vis[v]) 27 { 28 vis[v]=true; 29 if(!whi[v]||dfs(whi[v])) 30 { 31 whi[v]=x; 32 return true; 33 } 34 } 35 } 36 return false; 37 } 38 39 int main() 40 { 41 scanf("%d",&T); 42 while(T--) 43 { 44 ans=0; 45 memset(head,0,sizeof(head)); 46 memset(whi,0,sizeof(whi)); 47 scanf("%d",&n); 48 for(int i=1;i<=n;i++) 49 { 50 for(int j=1;j<=n;j++) 51 { 52 scanf("%d",&a[i][j]); 53 if(a[i][j]) 54 add(i,j); 55 } 56 } 57 for(int i=1;i<=n;i++) 58 { 59 memset(vis,false,sizeof vis); 60 if(dfs(i)) 61 ans++; 62 } 63 if(ans==n) 64 cout<<"Yes"<<endl; 65 else 66 cout<<"No"<<endl; 67 } 68 return 0; 69 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- bzoj3569 DZY Loves Chinese II 2020-05-25
- bzoj4036 [HAOI2015]按位或 2020-04-26
- 「BZOJ4173」数学 2020-01-15
- bzoj3944 Sum 2019-12-25
- BZOJ1008: [HNOI2008]越狱(快速幂) 2019-08-26
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash