TOPIC

PROBLEM 1056 - URI Fórum 1.0

URI Online Judge asked 8 years ago

URI Online Judge Fórum 1.0

MOD

This topic was solved and cannot recieve new replies.

  • Matheus Pimenta replied 6 years ago

    Hcb13, tem que considerar sim... mas você não precisa escrever alguma condição especial p/ isto. o único caso especial que vc precisa considerar, se for usar o algoritmo de emparelhamento máximo, é tomar cuidado com a presença do zero no conjunto A. o único múltiplo de zero é zero.

  • Paulo Felipe replied 4 years ago

    Alguém sabe explicar porque encontrar o lado bipartido mínimo não funciona para esse problema?

    Tentei pensar em casos de teste que não passam, mas não consegui.

    #include <bits/stdc++.h>
    #define MAX 100005
    #define INF 1<<30
    using namespace std;
    vector<int>graph[MAX];
    int color[MAX];
    int v1[MAX], v2[MAX];
    int n, m, tot;
    int bfs_bi_check(int ori);
    int main()
    {
        int t, x;
        scanf("%d", &t);
        for(int k = 1;k <= t;k++)
        {
            scanf("%d", &n);
            for(int i = 1;i <= n;i++)
                scanf("%d", &v1[i]);
            scanf("%d", &m);
            for(int i = 1;i <= m;i++)
            {
                scanf("%d", &v2[i]);
                for(int j = 1;j <= n;j++)
                {
                    if(v1[j] == 0)
                    {
                        if(v2[i] == 0)
                        {
                            graph[j].push_back(i+n);
                            graph[i+n].push_back(j);
                        }
                    }
                    else
                    {
                        x = v2[i]/v1[j];
                        if(x*v1[j] == v2[i])
                        {
                            graph[j].push_back(i+n);
                            graph[i+n].push_back(j);
                        }
                    }
                }
            }
            tot = n + m;
            for(int i = 1;i <= tot;i++)
                color[i] = INF;
            int ans = 0;
            for(int i = 1;i <= tot;i++)
                if(color[i] == INF)
                    ans += bfs_bi_check(i);
            printf("Case %d: %d\n", k, ans);
            for(int i = 1;i <= tot;i++)
                graph[i].clear();
        }
        return 0;
    }
    int bfs_bi_check(int ori)
    {
        queue<int>fila;
        int u, v, cont[2] = {};
        fila.push(ori);
        color[ori] = 0;
        cont[0]++;
        while(!fila.empty())
        {
            v = fila.front();
            fila.pop();
            for(int i=0;i<graph[v].size();i++)
            {
                u = graph[v][i];
                if(color[u] == INF)
                {
                    color[u] = 1 - color[v];
                    cont[color[u]]++;
                    fila.push(u);
                }
            }
        }
        return min(cont[0], cont[1]);
    }
  • Railton Thales replied 4 years ago

    "Algorithm is simple as that:

    1. Find unmatched vertex, mark it as not included in minimum vertex cover.
    2. Mark all matched neighbours of this vertex as included in minimum vertex cover.
    3. Treat all mates of vertexes from previous step as unmatched vertexes and repeat step 1.
    4. If recursion ended, repeat from step 1 (that is case of several connected components of graph).
    5. If there is no unmatched vertexes, take all remaining pairs and mark them any way you like (remember that one vertex in pair has to be included in minimum vertex cover, and other one has to be not included)."
  • Gabriel Duarte replied 4 years ago

    A resposta é 5, cuidado com o 0, qualquer número liga no 0, inclusive outro 0. O casamento nesse caso seria:

    0 0
    0 0
    0 0
    4 0
    8 16
    MOD
  • Paulo Henrique Tenório replied 5 years ago

    O toolkit esta devolvendo 5 para essa entrada

    1 5 0 0 0 4 8 6 0 0 0 0 0 16

    Não seria 4?, remoção dos 3 zeros de A e do 16 do B.

  • Marcos Bustamante replied 5 years ago

    Galera o toolkit está retornando 1 para essa entrada:

    1 2 1 2 1 0

    está correto? não deveria ser 0?

    Estou recebendo WA... estou resolvendo com grafo bipartido... alguém tem alguma entrada especial.

  • Hortênsia replied 6 years ago

    Olá, gostaria de saber se para a solução deveria se considerar casos em que A tem elementos iguais e B também, como no caso de teste abaixo:

    [list:3j6p5105]1 2 1 1 2 1 1[/list:u:3j6p5105]

  • Murilo Goncalves Pereira replied 7 years ago

    Ah certo, obrigado.

  • Cristhian Bonilha replied 7 years ago

    Entendi. Olha, é um algoritmo guloso, então acho que nem sempre ele vai fazer uma escolha boa. Eu bolei esse teste que faz ele falhar:

    1
    5 2 1 3 13 5
    4 10 12 39 65

    Se quiser um conselho, o algoritmo que usei foi o de Emparelhamento Máximo.

  • Murilo Goncalves Pereira replied 7 years ago

    A idéia não é exatamente essa. Eu sempre removo o vértice de grau máximo idependente de qual conjunto ele está, A ou B. Vou postar o código...

    #include <set>
    //#include <tr1/unordered_map>
    #include <map>
    #include <list>
    #include <stack>
    #include <cmath>
    #include <queue>
    #include <ctime>
    #include <cfloat>
    #include <vector>
    #include <string>
    #include <cstdio>
    #include <bitset>
    #include <climits>
    #include <cstdlib>
    #include <cstring>
    #include <cassert>
    #include <iomanip>
    #include <sstream>
    #include <utility>
    #include <iostream>
    #include <algorithm>
    
    using namespace std;
    //using namespace tr1;
    
    #define FOR(i, a, b) for(int i = a; i <= b; ++i)
    #define RFOR(i, b, a) for(int i = b; i >= a; --i)
    #define REP(i, N) for(int i = 0; i < N; ++i)
    #define RREP(i, N) for(int i = N-1; i >= 0; --i)
    #define FORIT(i, a) for( TI(a) i = a.begin(); i != a.end(); i++ )
    #define MAXN 1000010
    //#define INF 0x3F3F3F3F
    #define LINF 0x3F3F3F3FFFFFFFFFLL
    #define FILL(X, V) memset( X, V, sizeof(X) )
    #define TI(X) __typeof((X).begin())
    #define ALL(V) V.begin(), V.end()
    #define SIZE(V) int((V).size())
    #define pb push_back
    #define mp make_pair
    #define INF 0x3f3f3f3f
    #define LSOne(S) (S & (-S))
    
    typedef long long ll;
    typedef vector<int> vi;
    typedef pair<int, int> ii;
    typedef vector<ii> vii;
    typedef deque<int> di;
    typedef vector<vi> vv;
    map<int, vi> adj;
    map<int, int> degree;
    vi A, B;
    
    bool solved()
    {
        REP(i, B.size())
            if ( degree[B[i]] > 0)
                return false;
    
        return true;
    }
    
    int main()
    {
        ios::sync_with_stdio(false);
        int Cases, caso = 1;
        cin >> Cases;
        while ( Cases-- )
        {
            int n, m, aux;
            A.clear();
            B.clear();
            cin >> n;
            REP(i, n)
            {
                cin >> aux;
                A.pb(aux);
            }
    
            cin >> m;
            REP(i, m)
            {
                cin >> aux;
                B.pb(aux);
            }
    
            REP(i, n)
            {
                REP(j, m)
                {
                    if ( A[i] == 0 )
                    {
                        if ( B[j] == 0 )
                        {
                            adj[A[i]].pb(B[j]);
                            adj[B[j]].pb(A[i]);
                            degree[A[i]]++;
                            degree[B[j]]++;                     
                        }
                    }
                    else if ( B[j]%A[i] == 0 )
                    {
                        adj[A[i]].pb(B[j]);
                        adj[B[j]].pb(A[i]);
                        degree[A[i]]++;
                        degree[B[j]]++;
                    }
                }
            }
    
            int cont = 0;
            while ( !solved() )
            {
                cont++;
                int vertex, grau = 0;
                FORIT( it, degree )
                {
                    if ( (*it).second > grau )
                    {
                        vertex = (*it).first;
                        grau = (*it).second;
                    }
                }
    
                FORIT( it, adj[vertex] )
                {
                    degree[*it]--;
                }degree[vertex] = 0; adj[vertex].clear();
            }
    
            cout << "Case " << caso++ << ": " << cont << "\n";
        }   
        return 0;
    }
  • Cristhian Bonilha replied 7 years ago

    Isso funcionaria se o foco fosse sempre retirar os vértices de B.

    Digamos que um vértice v de B tenha cinco arestas com cinco vértices de A. A remoção desse vértice, que tem grau cinco, eliminaria todas as ligações e poderia ser resolvido com seu algoritmo.

    Agora digamos que há um vértice v de A que tem cinco arestas com cinco vértices de B. De acordo com seu algoritmo, eu removeria os cinco vértices de B, pois cada um deles tem grau 1, enquanto a melhor estratégia na verdade é remover aquele único vértice de A.

    Note que o objetivo é fazer o menor número de remoções possíveis.

  • Murilo Goncalves Pereira replied 7 years ago

    Alguém pode me dizer o que há de errado na idéia:

    int saida = 0;
    enquanto( Existe algum vértice em B com grau > 0 )
    {
    saida++;
    remove vértice de grau máximo;
    }
  • Cristhian Bonilha replied 7 years ago

    Era bem isso, agradeço a ajuda.

  • Fernando Fonseca replied 7 years ago

    Se você já tiver o emparelhamento máximo, basta uma DFS:

    http://en.wikipedia.org/wiki/K%C3%B6nig'stheorem(graph_theory)#Algorithm

  • Cristhian Bonilha replied 7 years ago

    Foi bem útil, agradeço.

    Mas se eu quisesse de fato descobrir quais são os vértices da cobertura mínima, conhece algum algoritmo pra isso?

  • Fernando Fonseca replied 7 years ago

    O teorema de Konig pode te ajudar.

  • Cristhian Bonilha replied 7 years ago

    Alguém recomenda algum algoritmo em específico para esse exercício?

  • Ramon de Oliveira replied 7 years ago

    Valeu rukzaper,

    estava esquecendo do caso 0 ser multiplo de 0, Obrigado.

  • Fernando Fonseca replied 7 years ago

    Você lidou com os casos onde 0 é um número da entrada? Mais especificamente, 0 é múltiplo de 0, mas nenhum outro número é múltiplo de 0.

  • Ramon de Oliveira replied 7 years ago

    Ola,

    alguem poderia me passar uns casos de teste "pegadinha" para este problema, ja gerei grandes arquivos de teste e joguei no toolkit para testar e passa em todos.

    Obrigado.