admin管理员组

文章数量:1130349

Book Club
Time Limit: 5000ms, Special Time Limit:12500ms, Memory Limit:65536KB
Total submit users: 35, Accepted users: 17
Problem 13377 : No special judgement
Problem description

Porto’s book club is buzzing with excitement for the annual book exchange event! Every year, members bring their favorite book and try to find another book they like that is owned by someone willing to trade with them.
I have been to this book exchange before, and I definitely do not want to miss it this year, but I feel that the trading should be improved. In the past, pairs of members interested in each other’s books would simply trade: imagine that person A brought a book that person B liked and vice-versa, then A and B would exchange their books.
I then realized that many members were left with the same book they walked-in with... If instead of looking for pairs I looked for triplets, I could find more valid exchanges! Imagine that member A only likes member B’s book, while B only likes C’s book and C likes A’s book. These 3 people could trade their books in a cycle and everyone would be happy!
But why stop at triplets? Cycles could be bigger and bigger! Could you help me find if it is possible for everyone to go out with a new book? Be careful, because members will not give their book without receiving one they like in return.
Given the members of the book club and the books they like, can we find cycles so that everyone receives a new book?


Input

The first line has two integers: N, the number of people, and M, the total number of “declarations of interest”. Each of the following M lines has two integers, A and B, indicating that member A likes the book that member B brought (0<=A,B < N). Numbers A and B will never be the same (a member never likes the book he brought). 2<=N<=10 000
1<=M<=20 000 and M<=N^2-N.


Output

You should output YES if we can find a new book for every club member and NO if that is not possible.


Sample Input
9 9
0 1
1 2
2 0
3 4
4 3
5 6
6 7
7 8
8 5
Sample Output
YES
Problem Source
HNU Contest 


每个人都有喜欢的书  问能不能通过交换使得每个人都能得到一本新书  

类似于边覆盖的想法 看有没有最小的边 覆盖所有的点

所以就是类似于二分匹配  单向建边 看是不是所有的点都被覆盖了  是则YES

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string.h>
#include <string>
#include <vector>
#include <queue>

#define MEM(a,x) memset(a,x,sizeof a)
#define eps 1e-8
#define MOD 10009
#define MAXN 10010
#define MAXM 100010
#define INF 99999999
#define ll __int64
#define bug cout<<"here"<<endl
#define fread freopen("ceshi.txt","r",stdin)
#define fwrite freopen("out.txt","w",stdout)

using namespace std;

int Read()
{
    char c = getchar();
    while (c < '0' || c > '9') c = getchar();
    int x = 0;
    while (c >= '0' && c <= '9') {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x;
}

void Print(int a)
{
     if(a>9)
         Print(a/10);
     putchar(a%10+'0');
}

int n,m;
vector<int> vec[MAXN];
int link[MAXN];
int vis[MAXN];

int dfs(int u)
{
    for(int i=0;i<vec[u].size();i++)
    {
        int v=vec[u][i];
        if(!vis[v])
        {
            vis[v]=1;
            if(link[v]==-1||dfs(link[v]))
            {
                link[v]=u;
                return 1;
            }
        }
    }
    return 0;
}

void hungary()
{
    MEM(link,-1);
    for(int i=0;i<n;i++)
    {
        MEM(vis,0);
        dfs(i);
    }
    for(int i=0;i<n;i++)
    {
        if(link[i]==-1)
        {
            puts("NO");
            return;
        }
    }
    puts("YES");
}

int main()
{
//    fread;

    while(scanf("%d%d",&n,&m)!=EOF)
    {
        for(int i=0;i<n;i++)
            vec[i].clear();
        while(m--)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            vec[a].push_back(b);
        }
        hungary();
    }
    return 0;
}



Book Club
Time Limit: 5000ms, Special Time Limit:12500ms, Memory Limit:65536KB
Total submit users: 35, Accepted users: 17
Problem 13377 : No special judgement
Problem description

Porto’s book club is buzzing with excitement for the annual book exchange event! Every year, members bring their favorite book and try to find another book they like that is owned by someone willing to trade with them.
I have been to this book exchange before, and I definitely do not want to miss it this year, but I feel that the trading should be improved. In the past, pairs of members interested in each other’s books would simply trade: imagine that person A brought a book that person B liked and vice-versa, then A and B would exchange their books.
I then realized that many members were left with the same book they walked-in with... If instead of looking for pairs I looked for triplets, I could find more valid exchanges! Imagine that member A only likes member B’s book, while B only likes C’s book and C likes A’s book. These 3 people could trade their books in a cycle and everyone would be happy!
But why stop at triplets? Cycles could be bigger and bigger! Could you help me find if it is possible for everyone to go out with a new book? Be careful, because members will not give their book without receiving one they like in return.
Given the members of the book club and the books they like, can we find cycles so that everyone receives a new book?


Input

The first line has two integers: N, the number of people, and M, the total number of “declarations of interest”. Each of the following M lines has two integers, A and B, indicating that member A likes the book that member B brought (0<=A,B < N). Numbers A and B will never be the same (a member never likes the book he brought). 2<=N<=10 000
1<=M<=20 000 and M<=N^2-N.


Output

You should output YES if we can find a new book for every club member and NO if that is not possible.


Sample Input
9 9
0 1
1 2
2 0
3 4
4 3
5 6
6 7
7 8
8 5
Sample Output
YES
Problem Source
HNU Contest 


每个人都有喜欢的书  问能不能通过交换使得每个人都能得到一本新书  

类似于边覆盖的想法 看有没有最小的边 覆盖所有的点

所以就是类似于二分匹配  单向建边 看是不是所有的点都被覆盖了  是则YES

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string.h>
#include <string>
#include <vector>
#include <queue>

#define MEM(a,x) memset(a,x,sizeof a)
#define eps 1e-8
#define MOD 10009
#define MAXN 10010
#define MAXM 100010
#define INF 99999999
#define ll __int64
#define bug cout<<"here"<<endl
#define fread freopen("ceshi.txt","r",stdin)
#define fwrite freopen("out.txt","w",stdout)

using namespace std;

int Read()
{
    char c = getchar();
    while (c < '0' || c > '9') c = getchar();
    int x = 0;
    while (c >= '0' && c <= '9') {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x;
}

void Print(int a)
{
     if(a>9)
         Print(a/10);
     putchar(a%10+'0');
}

int n,m;
vector<int> vec[MAXN];
int link[MAXN];
int vis[MAXN];

int dfs(int u)
{
    for(int i=0;i<vec[u].size();i++)
    {
        int v=vec[u][i];
        if(!vis[v])
        {
            vis[v]=1;
            if(link[v]==-1||dfs(link[v]))
            {
                link[v]=u;
                return 1;
            }
        }
    }
    return 0;
}

void hungary()
{
    MEM(link,-1);
    for(int i=0;i<n;i++)
    {
        MEM(vis,0);
        dfs(i);
    }
    for(int i=0;i<n;i++)
    {
        if(link[i]==-1)
        {
            puts("NO");
            return;
        }
    }
    puts("YES");
}

int main()
{
//    fread;

    while(scanf("%d%d",&n,&m)!=EOF)
    {
        for(int i=0;i<n;i++)
            vec[i].clear();
        while(m--)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            vec[a].push_back(b);
        }
        hungary();
    }
    return 0;
}



本文标签： 匈牙利算法hnuojClubbook

版权声明：本文标题：hnuoj 13377 Book Club（匈牙利算法） 内容由热心网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：https://it.en369.cn/jiaocheng/1758642661a2782214.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。