Definición de gráfico coincidente
Los problemas de personal se pueden expresar en el lenguaje de los gráficos. Supongamos ≤i≤m, 1≤j≤n, si y sólo si el trabajador está calificado para el trabajo yi y tiene una ventaja en G, entonces el problema de asignación de personal se convierte en un problema de encontrar la máxima coincidencia en G
El algoritmo húngaro se usa a menudo para encontrar la coincidencia máxima. Su idea básica es: para una coincidencia conocida M, a partir de M puntos insaturados seleccionados arbitrariamente en X, use el método de etiquetado para encontrar M cadenas de aumento. Si se encuentra la cadena aumentada de m, entonces m se puede aumentar; de lo contrario, comenzando desde otro punto m-insaturado en x, continúe encontrando la cadena m-aumentadora. Repita este proceso hasta que no haya ninguna cadena de aumento en G. La coincidencia en este momento es la coincidencia máxima de G. Este algoritmo a menudo se denomina algoritmo húngaro porque el método de etiquetado para encontrar cadenas de aumento presentado aquí fue propuesto por primera vez por el dentista húngaro Egerváry. .
Después de comprender este algoritmo, no es difícil escribir una solución al problema de asignación de personal. Antes de dar el programa, haga algunas suposiciones:
Para simplificar, suponga que el número de trabajadores es igual al número de puestos de trabajo, es decir, N=M y N≤100. Aquí, n también puede considerarse como |X| y |Y| del gráfico bipartito.
Los datos se leen desde la entrada del archivo. txt, con n y |E| al principio, y la siguiente línea |E| con dos números (I, J), que indica que el trabajador I está calificado para el trabajo J, que es el borde xiyj en el gráfico bipartito.
Los resultados se envían a un archivo de salida. TXT. La primera línea es el número máximo de coincidencia S, y cada una de las siguientes líneas S tiene dos números (I, J), lo que indica que el trabajador asignado I está realizando el trabajo J, es decir, el borde coincidente xiyj. Para el problema de asignación de personal anterior, si también se tiene en cuenta la eficiencia laboral de los trabajadores, se puede plantear el llamado problema de asignación: ¿Cómo asignar para maximizar la eficiencia general?
Igual que en la sección anterior, podemos construir un gráfico bipartito G. Si la eficiencia wij de los trabajadores que realizan el trabajo yi se considera como el peso en G, entonces el problema de asignación es equivalente al gráfico bipartito ponderado G. Encontrar una coincidencia completa máxima en un gráfico bipartito G
Desde el conocimiento de la programación lineal, la coincidencia de peso máxima de un gráfico bipartito G se puede obtener mejorando solo ligeramente el algoritmo húngaro. La idea básica es numerar los vértices del gráfico bipartito, luego construir un nuevo gráfico bipartito G' basado en los números y finalmente convertir la coincidencia de peso máximo de G en la coincidencia perfecta de G'.
El siguiente teorema es la base teórica de este algoritmo.
Teorema: Supongamos que M es una coincidencia perfecta de un gráfico ponderado (con peso no negativo) y un gráfico bipartito completo G = (V, e), donde M es un subconjunto de e. G Cualquier coincidencia perfecta M ' tiene la suma de los pesos de M aristas mayor que la suma de los pesos de M ' aristas, entonces M es la coincidencia de peso máxima de G.
El procedimiento para encontrar la El peso máximo coincidente se indica a continuación. En el archivo de entrada, hay n y |E| primero, y hay tres números (I, J, W) en la siguiente línea |E|, lo que indica que la eficiencia del trabajador I al realizar el trabajo J es W. El programa La producción incluye la selección de cada trabajador y el ingreso total final. Para otros supuestos, consulte los supuestos del algoritmo en la sección anterior. Este es un problema: FJOI-Problema del sobre
El Sr. John escribió n cartas por la noche y, en consecuencia, escribió n sobres para empaquetar las cartas y prepararlas para enviarlas por correo. Sin embargo, al día siguiente, el hijo de John, John Jr., sacó todas las letras N del sobre. Desafortunadamente, Little John no pudo volver a colocar la carta en el sobre correctamente.
Numere las n letras proporcionadas por Little John como 1, 2,...,n; y estos n sobres también están numerados como 1,2,...,n. Supongamos que Little John puede proporcionar un conjunto de información: la primera letra definitivamente no está en el sobre j. Programe para ayudar a Little John a colocar tantas letras en el sobre de la manera más correcta posible. donde n≤100.
Por ejemplo, si hay cuatro letras y la primera letra no está en los sobres 1, 2 y 3, y la segunda letra no está en los sobres 2 y 3, puedes determinar que la primera letra está en sobres 4, la segunda carta está en el sobre 1. Pero estas condiciones no son suficientes para determinar la posición de la tercera y cuarta letra.
Análisis:
Después de leer esta pregunta, siento que es exactamente igual que las preguntas de razonamiento lógico en las competencias de matemáticas de la escuela primaria. El método de las preguntas de razonamiento lógico suele ser el escritorio. método de tarea.
Tomemos el ejemplo anterior. Según las condiciones se puede obtener la siguiente información:
1 2 3 4
1 × × ×
2 × ×
三
p>Cuatro
Tabla 1
Dado que solo debe haber una √ en cada fila y columna, podemos estar seguros de que la primera letra es contenida en el sobre 4, por lo que podemos obtener:
1 2 3 4
1 × × × √
2 × × ×
3 ×
4 ×
Tabla 2
Luego se encuentra que hay 3 × s en la segunda fila, entonces el restante debe ser √ , entonces se puede concluir que la segunda carta está en el sobre 1:
1 2 3 4
1 × × × √
2 √ × × ×
3 × ×
4 × ×
Tabla 3
Ahora, las filas 3 y 4 solo tienen dos x, por lo que es imposible determinar en qué sobre están.
De esta manera obtenemos un algoritmo preliminar: crea una tabla bidimensional en el programa, primero completa varias × s de acuerdo con las condiciones y luego verifica todas las filas y columnas indeterminadas para ver si existen. son n – 1 × s, si no, finalice; de lo contrario, complete los espacios restantes √ y complete otras posiciones en las filas (columnas) llenas de √.
Aunque es fácil pensar en este método, también hay contraejemplos en su contra, como:
Un contraejemplo en el Gráfico 3
Los vértices en la parte superior la mitad de la figura representa "información"”, los vértices de la mitad inferior representan el “sobre”. Si la letra I se puede colocar en el sobre J, entonces conecte un borde entre la letra I y el sobre J. Debido a que el grado de cada vértice es mayor o igual a 2, es decir, hay al menos dos vacantes en cada fila y columna. Entonces el algoritmo anterior no puede hacer ninguna inferencia, pero ese no es el caso. Por ejemplo, la carta del medio sólo se puede colocar en el sobre del medio.
Es este contraejemplo el que nos hace necesitar encontrar otro camino. Un análisis más detallado muestra que la relación entre cartas y sobres es una correspondencia uno a uno, porque una carta solo se puede colocar en un sobre y un sobre solo puede contener una carta. Desde la perspectiva de la informática, esta correspondencia uno a uno también puede considerarse como la relación de coincidencia de un gráfico bipartito.
Supongamos X={x1, x2,...,xm}, Y={y1, y2,...,yn}, y construya un gráfico bipartito G=(X, Y, E) , si y solo si la letra I se puede colocar en el sobre J y hay un borde xiyj en G. De esta manera, cualquier esquema de asignación de letras puede considerarse como una combinación perfecta del gráfico G. Por ejemplo, lo anterior El gráfico tiene y solo las siguientes dos coincidencias perfectas:
Todas las coincidencias perfectas en la Figura 4
Debido a que el borde coincidente del medio aparece en dos coincidencias perfectas, consideramos que este borde coincidente está "determinado". ", en otras palabras, esta ventaja La relación representada también es cierta. Es fácil ver que si y sólo si todas las coincidencias exactas m de g tienen bordes coincidentes xiyj, es seguro que la letra I se puede poner en el sobre j.
De esta manera establecimos un nuevo modelo desde la perspectiva del emparejamiento. Entonces, ¿cómo resolver este modelo?
Por supuesto, es imposible para nosotros enumerar todas las coincidencias perfectas de G y luego encontrar la intersección de sus aristas; esto no es diferente de buscar. Aquí se necesita otra pequeña transformación de este modelo: encontramos que la condición "para todas las coincidencias perfectas m de G, hay una arista coincidente xiyj" es equivalente a "si hay una coincidencia perfecta en el gráfico G, pero elimina una en el gráfico G No hay coincidencia perfecta en el gráfico G' obtenido por la arista xiyj." Por ejemplo, un "borde clave" se elimina en la parte inferior izquierda, por lo que no hay una coincidencia exacta, mientras que un "borde no crítico" se elimina en la parte inferior derecha, por lo que hay una coincidencia exacta.
Ejemplo de recorte en la Figura 5
A primera vista, la complejidad temporal de este algoritmo todavía parece ser muy alta.
Debido a que hay como máximo n2 aristas en el gráfico G, encontrar una coincidencia perfecta requiere una complejidad de tiempo O (n3) al intentar eliminar aristas una a la vez. La complejidad total es tan alta como O (n5).
De hecho, primero podemos encontrar una M coincidente perfecta del gráfico G, por lo que solo debemos considerar los bordes coincidentes al eliminar los bordes (porque eliminar los bordes no coincidentes dará como resultado G', M sigue siendo G' combinación perfecta). De esta manera, con solo eliminar N aristas, la complejidad temporal se reduce a O (n4).
Después de un análisis más detallado, después de eliminar una ventaja, no es necesario volver a buscar una coincidencia completa, solo verifique si se puede encontrar una nueva cadena de aumento. De esta manera, la complejidad del tiempo se reduce aún más a O (n3). Pregunta: CTSC - Los problemas de Cupido
Con el continuo desarrollo de la sociedad, los sentimientos entre las personas se están volviendo cada vez más utilitarios. Recientemente, Cupido ha descubierto que el amor ya no es del todo puro. Este Cupido preocupado. Cada vez le resultaba más difícil encontrar hombres y mujeres adecuados, por lo que les disparó la flecha de Cupido. Entonces Cupido viajó hasta China y encontró al anciano bajo la luna, el dios oriental del amor, y le pidió consejo.
Bajo la luz de la luna, el anciano le dice a Cupido que el amor puro no existe, pero no lo ha encontrado. En Oriente la gente presta atención al destino. Mientras el Viejo bajo la Luna sean dos figuras de arcilla, una masculina y otra femenina, y haya un hilo rojo que las conecte, las personas que representan se amarán entre sí, sin importar dónde se encuentren. La flecha del amor de Cupido solo puede alcanzar a dos personas que estén muy cerca una de la otra, por lo que el rango de opciones es naturalmente mucho menor y no puedes encontrar tu verdadero destino.
Después de escuchar la explicación del anciano bajo la luna, Cupido de repente se dio cuenta. Tras regresar, modificó su arco con la última tecnología del mundo, aumentando considerablemente el alcance de la flecha de Cupido. De esta forma, las posibilidades de golpear a alguien aumentan mucho.
A la medianoche del día de San Valentín, Cupido comenzó su trabajo. Seleccionó un grupo de igual número de hombres y mujeres, sintió su destino y disparó flechas en secuencia para enamorarlos. Espera elegir el mejor método, de modo que todos los que elija reciban un disparo una vez y la suma del destino entre cada par de personas que reciban el disparo sea la mayor.
Por supuesto, no importa cómo Cupido modificó su arco y sus flechas, seguían teniendo defectos. En primer lugar, aunque se ha aumentado el alcance del arco y la flecha, después de todo todavía es limitado y no puede ser como el "matrimonio de las mil millas" como el anciano bajo la luna. En segundo lugar, no importa cómo se modifique, la trayectoria de la flecha solo puede ser una línea recta después de todo. En otras palabras, si hay otras personas en la línea que conecta a dos personas, entonces la flecha de Cupido debe dispararse hacia ellas. si el viejo está en la luna, entonces es un "squib".
Como mortal, tu tarea es utilizar ordenadores avanzados para encontrar la mejor solución para Cupido.
La primera línea del archivo de entrada es un entero positivo k, que indica el rango de la flecha de Cupido, y la segunda línea es un entero positivo n (n
El archivo de salida solo tiene un entero positivo, que representa cada par. La suma de los destinos de las personas que recibieron disparos. Este total debería ser el mayor.
Análisis:
Analicemos uno por uno:<. /p>
La flecha de Cupido tiene la característica de rango,
Hombres y mujeres, sus atributos incluyen nombre y posición,
La relación entre hombres y mujeres, esta relación es Su valor del destino,
La relación entre las flechas y las personas. Un hombre y una mujer si la distancia entre los dos no excede el alcance de la flecha y no hay obstrucción de otros, la pregunta es: Un. El plan de tiro con arco maximiza el destino de todos los hombres y mujeres que reciben el disparo.
Este problema es como encontrar el peso máximo coincidente en un gráfico bipartito. Debido a que hombres y mujeres pertenecen a dos conjuntos, no existe ninguna relación entre ellos. del mismo sexo, por lo que es una figura bipartita. Cuando los valores de destino se registran como pesos en los bordes, la suma de destino es máxima, que corresponde a la coincidencia de peso máxima en este gráfico bipartito. Cabe señalar que aunque el título no muestra ninguna descripción de la relación entre hombres y mujeres, el valor del destino entre las dos personas es 1, pero eso no significa que el diagrama bipartito obtenido sea un diagrama bipartito completo, porque en el proceso de. Al componer la imagen, también se deben considerar factores como el alcance de la flecha: si la distancia entre las dos personas excede la distancia de la flecha, si el objetivo está dentro de un cierto rango, está destinado a fallar a la otra parte. /p>
El problema surge en este momento, porque además de los requisitos del destino y el valor máximo, la pregunta también requiere que "todos los elegidos por Cupido deben disparar una vez".
Puedes pensar. que cuanto mayor sea el destino, a más personas dispares, mejor, pero este no es el caso: Por ejemplo:
Gráfico 6 Contraejemplo
Si necesitas igualar el peso máximo, Elige lados coincidentes AD, la suma del destino es 10.
Pero como todos tienen que ser fotografiados una vez, solo pueden elegir AC y BD, y la suma del destino es 2.
En otras palabras, para este ejemplo, la respuesta correcta debe ser 2 y el valor máximo de coincidencia de peso es 10. Esto muestra que esta pregunta es diferente de una simple coincidencia de peso máximo, porque la pregunta requiere un peso máximo y una coincidencia perfecta, lo que llamamos una coincidencia de peso máximo "perfecta".
Entonces, ¿no se puede resolver este problema utilizando la igualación de peso máximo? No se preocupe, revisemos el algoritmo para la coincidencia de peso máximo: convertimos el gráfico G en G' numerando los vértices, y luego convertimos la coincidencia de peso máximo de G en la coincidencia perfecta de G'; esto parece ser un resultado perfecto. match, pero ¿por qué no para el ejemplo anterior?
Resulta que para el ejemplo anterior, después del etiquetado, se agrega una nueva arista BC al nuevo gráfico G', y el peso de esta arista es 0. Las coincidencias perfectas en el gráfico G' son en realidad AD y BC, correspondientes al gráfico G, que es el borde AD.
Entonces, si establecemos el peso del borde de BC en -∞ de antemano y luego encontramos el peso máximo coincidente en el gráfico, no habrá más problemas.
De manera más general, si necesita una coincidencia de peso máximo "perfecta" de un gráfico bipartito, solo necesita establecer los pesos de los bordes que no están en el gráfico original en -∞. P: IPSC-Magic
Un mago famoso actúa en el escenario, seguido por una hermosa asistente. El mago primero conjuró varios conejos de su sombrero mágico, luego conjuró un ramo de flores de la bufanda de la asistente y finalmente encerró a la asistente en una caja aparentemente vacía. Luego, el mago elige un espectador con quien actuar: coloca N cartas sobre una mesa (todas las N cartas son diferentes en pares, N es un número impar). El mago pide voluntarios que vayan a la plataforma y elijan (N+1)/2 cartas. El resto de cartas desaparecen para siempre en el sombrero del mago. El mago agitó su mano sobre las cartas elegidas, luego seleccionó una de ellas y se la entregó al voluntario. El voluntario muestra la tarjeta que tiene en la mano al público y luego la esconde en su bolsillo. Después de que la asistente lo sacó de la caja, se acercó a la mesa, agitó las tarjetas restantes (N+1)/2-1 e inmediatamente le dijo al voluntario qué tarjetas había en su bolsillo.
¿A qué se debe esto? Veamos la siguiente tabla, que es el caso de N=5:
Las cartas elegidas por los voluntarios, las cartas elegidas por el mago y las cartas vistas por el asistente.
1,2,3 3 1,2
1,2,4 2 1,4
1,2,5 2 1,5p>
1,3,4 4 1,3
1,3,5 1 3,5
1,4,5 1 4,5
2,3,4 4 2,3
2,3,5 3 2,5
2,4,5 5 2,4
3,4,5 5 3,4
Tabla 4
Entre ellos, la carta elegida por el voluntario - la carta elegida por el mago = la carta vista por el asistente. La tabla contiene todas las posibilidades para que los voluntarios elijan tarjetas, y cada una es diferente. Las cartas que ve el asistente también son diferentes.
Primero el mago y su asistente deben recordar la mesa. De esta forma, cuando la asistente vea las cartas 2 y 4, podrá estar segura de que las cartas elegidas por el voluntario son la 2, 4 y 5, y que la carta elegida por el mago es la 5.
Ahora te diré el valor de n y te dejaré calcular esta tabla. donde n≤15.
Análisis:
Para facilitar el análisis, sea m el número de opciones para seleccionar (N+1)/2 tarjetas de N tarjetas. Obviamente, el número de opciones para seleccionar (n+1)/2-1 tarjetas de estas N tarjetas también es m.
Empecemos desde la perspectiva de la enumeración. Hay dos métodos de enumeración:
Para cada plan de selección de cartas del voluntario, se enumeran las cartas seleccionadas por el mago.
Para cada plan de selección de tarjeta del voluntario, el asistente correspondiente ve la tarjeta.
La opción 1 requiere m decisiones, cada decisión tiene n opciones; la opción 2 también requiere m decisiones, y cada decisión puede tener m opciones. Desde esta perspectiva, la opción 1 es mucho mejor. ,
Sin embargo, no existe una correspondencia uno a uno entre el "Plan de selección de tarjetas de voluntario" y el "Plan de selección de tarjetas de mago" que se muestra en el primer plan. Para los diferentes esquemas de selección de cartas de los voluntarios, el mago puede elegir la misma carta.
La relación que se muestra en el segundo plan es una relación uno a uno, porque la pregunta requiere que para diferentes planes de selección de tarjetas de voluntarios, el asistente debe ver tarjetas diferentes.
Como se mencionó anteriormente, desde la perspectiva de la ciencia de la información, la correspondencia uno a uno también puede considerarse como una relación de coincidencia de un gráfico bipartito. Por lo tanto, la segunda opción facilita que las personas consigan los partidos.
Supongamos Si y sólo si, la arista xiyj existe en g, entonces el problema original se transforma en encontrar una coincidencia perfecta del gráfico g.
El problema vuelve a aparecer. Primero, los vértices del gráfico bipartito llegan a 2M. Cuando N = 15, m está cerca de 8000 y la complejidad de coincidencia es O (M3). ¿Cómo podemos tolerar una complejidad tan alta?
Tenga en cuenta que este gráfico es un gráfico disperso con solo aristas MN. La complejidad de la coincidencia bipartita escasa también se puede expresar como O (|V|×|E|). Entonces, la complejidad del tiempo debería ser O (M2N), que es básicamente tolerable.
Además, debido a que este es un gráfico disperso, usamos una lista de adyacencia para almacenarlo, por lo que la complejidad del espacio es solo O (NM), lo cual también es tolerable.
Finalmente, este problema también se puede utilizar para lograr una mejor eficiencia, pero no es tan fácil de considerar como una coincidencia. El método de construcción específico no se proporciona aquí, los lectores pueden pensar en ello por sí mismos. Pregunta: OOPC - Montaña Misteriosa
La gente está persiguiendo a un animalito extraño. Justo cuando estaba a punto de alcanzarlo, la cosita saltó a una montaña misteriosa. Cómo se ven cuando miran hacia la montaña:
Diagrama de ejemplo del gráfico 7
La montaña consta de N+1 segmentos de línea. Cada punto final está numerado 0...N+1 de izquierda a derecha, es decir, X < x[i+1](0≤i≤n). Y y[0]=y[n+1]=0.
Según la experiencia, lo más probable es que esa cosita esté oculta en un punto final entre 1...n. Lo interesante es que todos pronto descubrieron que M es exactamente igual a N, por lo que decidieron elegir. Un punto para todos. Mira si se esconde ahí.
Al principio estaba al pie de la montaña, y la posición de la primera persona era (s, 0). Cada uno elige un punto intermedio (x, 0), camina hasta allí horizontalmente a velocidad W y sube directamente al destino a velocidad C. Como no son buenos en matemáticas, solo saben elegir el mejor número entero como la abscisa x del punto medio. Y obviamente, ninguna parte del recorrido puede estar por encima de montañas (no pueden volar).
Esta vez no querían volver a fallar, así que el capitán decidió buscar la manera de que la última persona llegara a su destino lo antes posible. ¿Qué deberían hacer?
Donde 1≤N≤100, 0≤x, y, s≤1000, 1 ≤ C
Entrada
La primera línea contiene un número entero N. Cada una de las líneas N + 2 posteriores contiene dos números enteros y yi, que representan las coordenadas del punto final correspondiente. Las siguientes n líneas contienen cada una tres números enteros ci, wi y si, que representan respectivamente la velocidad de ascenso, la velocidad de caminata y la posición inicial de la I-ésima persona.
Salida
Resulta la hora más temprana en la que la última persona llegó al destino, redondeada a dos decimales.
Entrada de valor de muestra
Tres
0 0
3 4
6 1
12 6
16 0
2 4 4
8 10 15
4 25 14
Salida de muestreo
1.43
Descripción de la muestra
En este ejemplo, la primera persona llega a (5.0) y luego sube al punto final 2. La segunda persona sube directamente; al punto final 3; la tercera persona llega a (4.0) y luego sube al punto final 1. Como se muestra en la siguiente figura:
Figura 8 Solución de muestra
Análisis:
Hay muchos datos complejos en la pregunta. Vamos a publicarlos primero. y analízalas una a una:
La persona, ***n, está relacionada con la abscisa inicial S, velocidad W, c.
Hay ***n cimas de montañas, relacionadas con las coordenadas X e y.
A partir de esta información podemos obtener la relación entre las personas y las montañas: t[I, J], que representa el tiempo más corto para que la persona I llegue a la montaña J.
Como se señala en el título, obviamente existe una correspondencia uno a uno entre una persona y una persona.
Por tanto, este problema puede considerarse desde la perspectiva de la coincidencia de gráficos bipartitos.
Entonces, ¿a qué tipo de combinación pertenece este tema? ¿Es una coincidencia máxima simple, una coincidencia de peso máximo o la coincidencia de peso máximo "perfecta" mencionada anteriormente?
En realidad no. Porque en general la coincidencia de peso máximo, la definición de un peso coincidente es la suma de todos los pesos en los bordes coincidentes, y en esta pregunta, un peso coincidente se refiere al peso máximo en los bordes coincidentes. La pregunta requiere que este valor máximo sea el mínimo, así que llamémoslo "coincidencia mínimo-máximo" por el momento.
Parece inconveniente solucionarlo directamente. Por otro lado, si se da un tiempo, podemos usar el algoritmo de coincidencia perfecta para juzgar si podemos completar todo el trabajo dentro de este tiempo.
Específicamente, para un gráfico bipartito G dado y un tiempo máximo t, podemos derivar un nuevo gráfico G' en el que el peso de todos los bordes no exceda t. Si hay una coincidencia perfecta, entonces todo el trabajo se puede completar en t tiempo; de lo contrario, no es posible.
De esta manera nació un algoritmo simple: aumentar t sucesivamente hasta encontrar una coincidencia completa. Dado que el número de aristas en el gráfico bipartito no excederá n2, T se puede aumentar en n2 como máximo. Cada vez que aumenta el valor de T, se necesita O (n2) tiempo para encontrar la cadena de aumento, por lo que la complejidad del tiempo total es. O(n4).
También podemos utilizar el método de búsqueda binaria para encontrar esta T, de modo que la complejidad temporal del algoritmo se pueda reducir a O (n3logN).