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:46:36 on Problem 1469
#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],ch[410][410];
/*void addedge(int u,int v)
{
    th[cnt].e=v;
    th[cnt].next=head[u];
    head[u]=cnt++;
}*/
int gungary(int u,int m)
{
    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;
            }
        }
    }*/
    for(i=0;i<m;i++){
        if(ch[u][i]==1&&vis[i]==0){
            vis[i]=1;
            if(link[i]==-1||gungary(link[i],m)){
                link[i]=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++){
            for(j=0;j<m;j++){
                ch[i][j]=0;
            }
        }
        for(i=0;i<n;i++){
                scanf("%d",&u);
           for(j=0;j<u;j++){
                scanf("%d",&v);
                ch[i][v-1]=1;
               /* 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,m))
                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