首页 > 其他 > 详细

【题解】 [ZJOI2007]矩阵游戏 (二分图匹配)

时间:2018-03-15 19:52:14      阅读:214      评论:0      收藏:0      [点我收藏+]

原题目戳我

Solution:

方法很巧妙,我们把每个装备的属性 与 装备编号连起来

从1-10000跑二分图,如果出现断层,就退出,输出答案就好。

memset清理bool快一点,int洛谷上超时了

板子题

 

Code:

技术分享图片
 1 //It is coded by Ning_Mew on 3.14
 2 #include<bits/stdc++.h>
 3 
 4 using namespace std;
 5 
 6 const int maxn=1e6+7;
 7 
 8 int n,ans=0,be[maxn];
 9 bool vis[maxn];
10 int head[maxn],cnt=0;
11 struct Edge{
12     int nxt,to;
13 }edge[maxn*2];
14 
15 void add(int from,int to){
16     edge[++cnt].nxt=head[from];
17     edge[cnt].to=to;
18     head[from]=cnt;
19 }
20 bool find(int k){
21     for(int i=head[k];i!=0;i=edge[i].nxt){
22         int v=edge[i].to;
23         if(vis[v]==false){
24             vis[v]=true;
25             if(be[v]==-1||find(be[v])){be[v]=k;return true;}
26         }
27     }
28     return false;
29 }
30 
31 int main(){
32     scanf("%d",&n);
33     for(int i=1;i<=n;i++){
34         int a,b;scanf("%d%d",&a,&b);
35         add(a,i);add(b,i);
36     }
37     memset(be,-1,sizeof(be));
38     memset(vis,-1,sizeof(vis));
39     for(int i=1;i<=10000;i++){
40         memset(vis,false,sizeof(vis));
41         if(find(i))ans++;
42         else break;
43     }
44     printf("%d\n",ans);
45     return 0;
46 } 
View Code

 

【题解】 [ZJOI2007]矩阵游戏 (二分图匹配)

原文:https://www.cnblogs.com/Ning-Mew/p/8575797.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!