[bzoj1191]超级英雄hero<二分图匹配*匈牙利算法>

题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1191

今天随便在bzoj找了一题做，题一读完就发现是个匈牙利算法的裸题，原本以为可以一次过的，结果WA了不下五次，深感羞愧，后来我改变了方法，没有用邻接链表，改用邻接矩阵，结果一下子就过了，这让我甚是懵逼，到现在都没搞明白我的邻接链表哪里错了

-------------PS:最后把编号改回了0~n-1就过了

这道题纯粹是裸题，没有一丝思想上的难度，但是我自己小小处理了一个地方，这个地方处理或不处理不会影响最后的答案，就是我把锦囊标号0~n-1全部加1变成了1~n（PS：强迫症而已，不影响答案）【其实好像是有错误的】

首先来看看我的邻接链表方法吧

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 #include<cstdlib>
 6 #include<cmath>
 7 #include<queue>
 8 #define maxn 2005
 9 using namespace std;
10 
11 struct edge{
12     int u,v,nxt;
13 }e[maxn<<2];
14 
15 int vis[maxn],att[maxn],head[maxn];
16 int n,m,ans;
17 
18 int pos=0;
19 void adde(int u,int v)
20 {
21     e[pos].u=u;
22     e[pos].v=v;
23     e[pos].nxt=head[u];    
24     head[u]=pos++;
25 }
26 
27 bool can(int x)
28 {
29     for(int i=head[x];i!=-1;i=e[i].nxt)
30     {
31         int v=e[i].v;
32         if(vis[v]==0)
33         {
34             vis[v]=1;
35             if(can(att[v])||!att[v])
36             {
37                 att[v]=x;
38                   return 1;
39             }    
40         }
41     }
42     return 0;
43 }
44 
45 int main()
46 {
47     memset(att,0,sizeof(att));
48     memset(head,-1,sizeof(head));
49     scanf("%d%d",&n,&m);
50     for(int i=1;i<=m;i++)
51     {
52         int a,b;
53         scanf("%d%d",&a,&b);
54         if(a!=b)
55         {
56             adde(i,a);
57             adde(i,b);
58         }else adde(i,a);
59     }
60     for(int i=1;i<=m;i++)
61     {
62         memset(vis,0,sizeof(vis));
63         if(can(i))ans++;
64         else break;
65     }
66     cout<<ans;
67 }

View Code

然后就是我更改后的邻接矩阵，这个代码倒是一次过了，不过就让我瞬间懵逼（链表哪错了？？？？）

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<iostream>
 4 #include<algorithm>
 5 #include<cstdlib>
 6 #include<cmath>
 7 #include<queue>
 8 #define maxn 1005
 9 using namespace std;
10 
11 
12 int map[maxn][maxn];
13 int vis[maxn],att[maxn];
14 int n,m,ans;
15 
16 bool can(int x)
17 {
18     for(int i=1;i<=n;i++)
19     {
20         if(map[x][i]==1&&vis[i]==0)
21         {
22             vis[i]=1;
23             if(!att[i]||can(att[i]))
24             {
25                 att[i]=x;
26                 return 1;
27             }
28         }
29         
30     }
31     return 0;
32 }
33 
34 int main()
35 {
36     memset(att,0,sizeof(att));
37     scanf("%d%d",&n,&m);
38     for(int i=1;i<=m;i++)
39     {
40         int a,b;
41         scanf("%d%d",&a,&b);
42         map[i][a+1]=1;map[i][b+1]=1;
43     }
44     for(int i=1;i<=m;i++)
45     {
46         memset(vis,0,sizeof(vis));
47         if(can(i))ans++;
48         else break;
49     }
50     cout<<ans;
51 }

View Code

PS：链表的问题还望各位大佬发现问题并指出一下Orz

[bzoj1191]超级英雄hero<二分图匹配*匈牙利算法>

相关推荐