Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

没看懂

Posted by 0700302510 at 2017-06-27 22:22:23 on Problem 3041
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct edge{
    int e;
    int next;
}th[10010];
int vis[510],head[510],link[510];//vis检验是否已经走过,head和根节点有关,link和匹配边有关
int cnt;
void addedge(int u,int v)//建边
{
    th[cnt].e=v;
    th[cnt].next=head[u];
    head[u]=cnt++;
}
int gungary(int u)
{
    int i;
    for(i=head[u];i!=-1;i=th[i].next){//按临接表在查找的过程
        int v=th[i].e;
        if(!vis[v]){
            vis[v]=1;
            if(link[v]==-1||gungary(link[v])){
                link[v]=u;
                return 1;
            }
        }
    }
    return 0;
}
int main()
{
    int n,m,i;
    scanf("%d %d",&n,&m);
    cnt=0;
    memset(head,-1,sizeof(head));
    for(i=0;i<m;i++){
        int u,v;
        scanf("%d%d",&u,&v);
        addedge(u-1,v-1);
    }
    memset(link,-1,sizeof(link));
    int ans=0;
    for(i=0;i<n;i++){
        memset(vis,0,sizeof(vis));
        if(gungary(i))
            ans++;
    }
    printf("%d\n",ans);
    return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator