20分匈牙利求助
查看原帖
20分匈牙利求助
306954
芊枫Thomitics楼主2020/8/14 16:48

WA了八个点

#include <bits/stdc++.h>

using namespace std;

inline long long read()
{
    long long x = 0;
    int f = 1;
    char ch = getchar();
    while (ch < '0' || ch>'9')
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9')
    {
        x = (x << 1) + (x << 3) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}
void write(const long long& x)
{
    if (!x)
    {
        putchar('0');
        return;
    }
    char f[100];
    long long tmp = x;
    if (tmp < 0)
    {
        tmp = -tmp;
        putchar('-');
    }
    long long s = 0;
    while (tmp > 0)
    {
        f[s++] = tmp % 10 + '0';
        tmp /= 10;
    }
    while (s > 0)
    {
        putchar(f[--s]);
    }
}

bool visit[1090];
int head[50090];
int nxt[50090];
int ver[50090];
int match[1090];
int answer;
int cnt_edges=1;

int totM, totN, totE;

void add_edge(int x,int y)
{
    nxt[++cnt_edges]=x;
    head[x]=cnt_edges;
    ver[cnt_edges]=y;
}

bool dfs(int x)
{
    for (int i = head[x], y; i; i = nxt[i])
        if (!visit[y = ver[i]])
        {
            visit[y] = true;
            if (!match[y] || dfs(match[y]))
            {
                match[y] = x;
                return true;
            }
        }
    return false;
}

int main()
{
    totN = read();
    totM = read();
    totE = read();
    int x;
    int y;
    for (int i = 1; i <= totE; i++)
    {
        x = read();
        y = read();
        if (x > totN || y > totM)
        {
            continue;
        } else
        {
            add_edge(x, y);
        }
    }
    for (int i = 1; i <= totN; i++)
    {
        memset(visit, 0, sizeof(visit));
        if (dfs(i))
        {
            answer++;
        }
    }
    write(answer);
    return 0;
} //LikiBlaze Code
2020/8/14 16:48
加载中...