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-26 23:21:26
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
struct edge{
    int e;
    int next;
}th[110*310];
int cnt;
int head[410],link[410],vis[410];
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 i,j;
    int num;
    int n,m,v,u;
    scanf("%d",&num);
    while(num--){
        memset(head,-1,sizeof(head));
        cnt=0;
        scanf("%d%d",&n,&m);
        for(i=0;i<n;i++){
                scanf("%d",&u);
           for(j=0;j<u;j++){
                scanf("%d",&v);
                addedge(i,v-1);
           }
        }
        int ans=0;
        memset(link,-1,sizeof(link));
        for(i=0;i<n;i++){
            memset(vis,0,sizeof(vis));
            if(gungary(i))
                ans++;
        }
       if(ans!=n)
        printf("NO\n");
       else if(ans==n)printf("YES\n");
    }
    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