首页 > 代码库 > [bzoj1191]超级英雄hero<二分图匹配*匈牙利算法>
[bzoj1191]超级英雄hero<二分图匹配*匈牙利算法>
题目链接：http://www.lydsy.com/JudgeOnline/problem.php?id=1191
今天随便在bzoj找了一题做，题一读完就发现是个匈牙利算法的裸题，原本以为可以一次过的，结果WA了不下五次，深感羞愧，后来我改变了方法，没有用邻接链表，改用邻接矩阵，结果一下子就过了，这让我甚是懵逼，到现在都没搞明白我的邻接链表哪里错了
这道题纯粹是裸题，没有一丝思想上的难度，但是我自己小小处理了一个地方，这个地方处理或不处理不会影响最后的答案，就是我把锦囊标号0~n-1全部加1变成了1~n（PS：强迫症而已，不影响答案）
首先来看看我的邻接链表方法吧，我自己没有找出错误在哪，跪求各位大佬帮我查出错误！！！
Orz Orz Orz Orz Orz
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 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=1;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;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,0,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 a++;b++;55 if(a!=b)56 {57 adde(i,a);58 adde(i,b);59 }else adde(i,a);60 }61 for(int i=1;i<=m;i++)62 {63 memset(vis,0,sizeof(vis));64 if(can(i))ans++;65 else break;66 }67 cout<<ans;68 }
PS：这是一个未AC代码 ↑
然后就是我更改后的邻接矩阵，这个代码倒是一次过了，不过就让我瞬间懵逼（链表哪错了？？？？）
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 }
PS：链表的问题还望各位大佬发现问题并指出一下Orz
[bzoj1191]超级英雄hero<二分图匹配*匈牙利算法>
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。