易错点:
- 最大匹配的题在加边时经常需要将其中一个的编号平移n个单位.
- 有多组数据.
- 注意边数上限.
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
const int N=550;
int vis[N],match[N];
struct Edge{
int from,to,nxt;
}e[N*10];
int head[N],edgeCnt=1;
void addEdge(int u,int v){
e[++edgeCnt].from=u;
e[edgeCnt].to=v;
e[edgeCnt].nxt=head[u];
head[u]=edgeCnt;
}
bool dfs(int x){
for(int i=head[x];i;i=e[i].nxt){
int nowV=e[i].to;
if(vis[nowV])continue;
vis[nowV]=1;
if(!match[nowV]||dfs(match[nowV])){
match[nowV]=x;
return 1;
}
}
return 0;
}
void init(){
memset(match,0,sizeof(match));
memset(e,0,sizeof(e));
edgeCnt=1;
memset(head,0,sizeof(head));
}
int main(){
int n,m,k;
while(1){
scanf("%d",&n);
if(n==0)break;
scanf("%d%d",&m,&k);
init();
int rubbish;
for(int i=1;i<=k;i++){
int u,v;
scanf("%d%d%d",&rubbish,&u,&v);
if(u==0||v==0)continue;
addEdge(u,v+n);
addEdge(v+n,u);
}
int ans=0;
for(int i=1;i<=n;i++){
memset(vis,0,sizeof(vis));
if(dfs(i))ans++;
}
printf("%d\n",ans);
}
return 0;
}
rubbish好评
rubbish好评