ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила
вернуться в форум

Обсуждение задачи 1109. Конференция

WA1 ?
Послано Nibir338 10 фев 2017 14:44
Why i'm getting WA#1?

#include<bits/stdc++.h>
using namespace std;

int capacities[2002][2002];
int flowPassed[2002][2002];
vector<int> graph[2002];
int parentsList[2002];
int currentPathCapacity[2002];

int bfs(int startNode, int endNode)
{
    memset(parentsList, -1, sizeof(parentsList));
    memset(currentPathCapacity, 0, sizeof(currentPathCapacity));

    queue<int> q;
    q.push(startNode);

    parentsList[startNode] = -2;
    currentPathCapacity[startNode] = 999;

    while(!q.empty())
    {
        int currentNode = q.front();
        q.pop();

        for(int i=0; i<graph[currentNode].size(); i++)
        {
            int to = graph[currentNode][i];
            if(parentsList[to] == -1)
            {
                if(capacities[currentNode][to] - flowPassed[currentNode][to] > 0)
                {
                    parentsList[to] = currentNode;
                    currentPathCapacity[to] = min(currentPathCapacity[currentNode],
                    capacities[currentNode][to] - flowPassed[currentNode][to]);
                    if(to == endNode)
                    {
                        return currentPathCapacity[endNode];
                    }
                    q.push(to);
                }
            }
        }
    }
    return 0;
}

int edmondsKarp(int startNode, int endNode)
{
    int maxFlow = 0;
      while(true)
    {
        int flow = bfs(startNode, endNode);
        if (flow == 0)
        {
            break;
        }
        maxFlow += flow;
        int currentNode = endNode;
        while(currentNode != startNode)
        {
            int previousNode = parentsList[currentNode];
            flowPassed[previousNode][currentNode] += flow;
            flowPassed[currentNode][previousNode] -= flow;
            currentNode = previousNode;
        }
    }
    return maxFlow;
}

int main()
{
    long int m,n,k,x;

    cin>>m>>n>>k;
    x=m+n;
    for(int i=0;i<k;i++)
    {
        int a,b;
        cin>>a>>b;
        graph[a].push_back(m+b);
        graph[m+b].push_back(a);
        capacities[a][m+b]=1;
    }
    for(int i=0;i<m;i++) {graph[0].push_back(i+1);capacities[0][i+1]=1;}
    for(int i=0;i<n;i++) {graph[m+i+1].push_back(x+1);capacities[m+i+1][x+1]=1;}
    int y=edmondsKarp(0,x+1);
    int p=(m-y+1)/2;
    p=p+(n-y+1)/2;
    cout<<(y+p)<<endl;

}