P1894 [USACO4.2]完美的牛栏The Perfect Stall

链接:P1894

----------------------------------------------------------

我觉得这道题如果去掉题面,就是一道蓝题了。

 

-----------------------------------------------------------

这道题还是裸的二分图匹配,用匈牙利算法就可以AC掉。

什么是匈牙利算法?匈牙利

代码几乎差不多,也不需要优化,读入比模板题还复杂点,(他们应该换一下颜色)


 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 using namespace std;
 5 int vis[2001];
 6 int head[20001];
 7 int match[10000];
 8 struct b{
 9     int to;
10     int next;
11 } e[100001];
12 int n,m;
13 int x;
14 int p;
15 int ans;
16 void add(int f,int t){
17     p++;
18     e[p].next=head[f];
19     e[p].to=t;
20     head[f]=p;
21     }
22 int y;
23 bool dfs(int f){
24     for(int i=head[f];i;i=e[i].next){
25         int v=e[i].to;
26         if(vis[v]) continue;
27         vis[v]=1;
28         if(!match[v]||dfs(match[v])){
29             match[v]=f;
30             return 1;
31         }
32     }
33     return 0;
34 }
35 int main(){
36     scanf("%d%d",&n,&m);
37     for(int i=1;i<=n;++i){
38         scanf("%d",&x);
39         for(int j=1;j<=x;++j){
40             cin>>y;
41             add(i,y);
42         }
43     }
44     for(int i=1;i<=n;++i){
45         memset(vis,0,sizeof(vis));
46         if(dfs(i)) ans++;
47     }
48     printf("%d",ans);
49     return 0;
50 }

Ac

 

暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇