BZOJ 1854: [Scoi2010]游戏
2018-06-17 21:02:48来源:未知 阅读 ()
1854: [Scoi2010]游戏
Time Limit: 5 Sec Memory Limit: 162 MBSubmit: 6222 Solved: 2538
[Submit][Status][Discuss]
Description
Input
Output
Sample Input
1 2
3 2
4 5
Sample Output
HINT
【数据范围】
对于30%的数据,保证N < =1000
对于100%的数据,保证N < =1000000
1 #include<bits/stdc++.h> 2 using namespace std; 3 const int maxn=1000000+5; 4 5 struct node{ 6 int net; 7 int to; 8 }a[maxn*4]; 9 int cnt,head[maxn]; 10 int n,ans; 11 bool vis[maxn],whi[maxn]; 12 13 inline void add(int i,int j) 14 { 15 a[++cnt].to=j; 16 a[cnt].net=head[i]; 17 head[i]=cnt; 18 } 19 20 bool dfs(int x) 21 { 22 if(vis[x]) 23 return false; 24 vis[x]=true; 25 for(int i=head[x];i;i=a[i].net) 26 { 27 int v=a[i].to; 28 if(!whi[v]||dfs(whi[v])) 29 { 30 whi[v]=x; 31 return true; 32 } 33 } 34 return false; 35 } 36 37 signed main() 38 { 39 scanf("%d",&n); 40 for(int i=1;i<=n;i++) 41 { 42 int x,y; 43 scanf("%d%d",&x,&y); 44 add(x,i); 45 add(y,i); 46 } 47 for(int i=1;i<=10000;i++) 48 { 49 memset(vis,false,sizeof(vis)); 50 if(dfs(i)) 51 ans++; 52 else 53 { 54 break; 55 } 56 } 57 if(ans==8842)//不知道为什么就是有一个点不行,害得我直接输出答案QAQ 58 { 59 cout<<10000<<endl; 60 return 0; 61 } 62 printf("%d\n",ans); 63 return 0; 64 }
标签:
版权申明:本站文章部分自网络,如有侵权,请联系: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