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

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

Why WA4?
Послано JamesBond_007 25 окт 2016 14:22
#include <iostream>
#include <vector>
#include <set>
using namespace std;
set < pair <int, int> > S;
set < pair <int, int> > :: iterator it;
vector <int> A[1111], B[1111];
int n, k, m, x[1111], y[1111], res, X[1111], Y[1111];
bool used[111111];
void cut_x(int v){
    for (int i = 0; i < k; i ++){
        if(!used[i] && X[i] == v && y[Y[i]] > 1){used[i] = true; y[Y[i]] --; res --;}
    }
}
void cut_y(int v){
    for (int i = 0; i < k; i ++){
        if(!used[i] && Y[i] == v && x[X[i]] > 1){used[i] = true; x[X[i]] --; res --;}
    }
}
int main(){
    cin >> n >> m >> k;
    res = k;
    for (int i = 0; i < k; i ++){
        int u, v;
        cin >> X[i] >> Y[i];
        A[X[i]].push_back(Y[i]);
        B[Y[i]].push_back(X[i]);
        x[X[i]] ++; y[Y[i]] ++;
    }
    for (int i = 1; i <= n; i ++)
        S.insert(make_pair(x[i], i));
    for (it = S.begin(); it != S.end(); it ++){
        pair <int, int> v = *it;
        if(v.first == 1){
            cut_y(A[v.second][0]);
        }else{
            cut_x(v.second);
        }
    }
    cout << res;
}
Re: Why WA4?
Послано JamesBond_007 25 окт 2016 14:23
Help me?
Re: Why WA4?
Послано Freopen 18 апр 2017 10:20
Bipartite graph
Re: Why WA4?
Послано Husayn Hasanov 8 дек 2017 16:23
Your idea has bug you have to think again clearly!