Problème

Description

Dans une maternelle, \(n\) enfants décident de voter pour déterminer s'ils feront une sieste. Pour eux, cette question n'est pas très importante, alors ils décident d'adopter un esprit d'humilité. Bien que chacun ait ses propres préférences, pour faire attention aux opinions de leurs amis, ils peuvent voter contre leur propre inclination. Nous définissons le nombre de conflits d'un vote comme la somme des conflits entre amis et du nombre d'enfants qui votent contre leur propre préférence.

Notre problème est de déterminer comment chaque enfant devrait voter pour minimiser le nombre total de conflits.

Format d'entrée

La première ligne du fichier contient deux entiers \(n,m\), avec \(2\le n\le 300,1\le m\le \frac{n(n-1)}{2}\). Ici, \(n\) représente le nombre total d'enfants et \(m\) le nombre de paires d'amis. La deuxième ligne contient \(n\) entiers, où le \(i\)-ème entier représente la préférence du \(i\)-ème enfant : \(1\) signifie en faveur de la sieste, \(0\) signifie contre. Les \(m\) lignes suivantes contiennent chacune deux entiers \(i\) et \(j\), indiquant que \(i\) et \(j\) sont amis. Nous garantissons qu'aucune paire ne sera répétée.

Format de sortie

Il suffit d'afficher un entier : le nombre minimal de conflits possible.

Exemple

Entrée 1

3 3
1 0 0
1 2
1 3
3 2

Sortie 1

1

Plage

\(2\le n\le 300, 1\le m\le n(n - 1) / 2\)

Algorithme

Flux réseau

Approche

Nous commençons par créer un point source \(S\) et un puits \(T\). Ensuite, nous connectons tous les enfants en faveur de la sieste à \(S\), et les autres à \(T\), avec une capacité de \(1\). Nous connectons ensuite chaque paire d'amis avec une arête ayant une capacité de \(1\).

Si le coût de suppression d'une arête est \(1\), on peut voir que le problème revient à trouver le coût minimal pour rendre \(S\) et \(T\) non connectés. En effet, s'ils restent connectés, cela signifie qu'il existe toujours des conflits entre amis qui n'ont pas été résolus ou comptabilisés.

Supprimer une arête entre un enfant et son ami signifie que cet enfant ne va pas à l'encontre de sa préférence. Au contraire, s'il coupe la connexion avec le point source ou le puits, cela signifie qu'il a fait un compromis avec ses amis.

Selon le théorème du flux maximal égal au coupe minimal, nous pouvons simplement calculer le flux maximal sur le graphe construit.

Code

#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
#define LL long long
#define parcours(x, i, v) for (int i = tete[x], v = vers[i]; i; v = vers[i = suiv[i]])
#define inline __inline__ __attribute__((always_inline))
inline LL lire() {
  LL x = 0, w = 1;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') w = -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = (x << 3) + (x << 1) + ch - '0';
    ch = getchar();
  }
  return x * w;
}
const int Max_n = 305, Max_m = Max_n * Max_n << 1, inf = 1e9;
int n, m, S, T, resultat;
int compteur = 1, tete[Max_n], courant[Max_n], suiv[Max_m], vers[Max_m], capacite[Max_m];
int niveau[Max_n], flot_actuel[Max_n], flux_noeud[Max_n];
void ajouter_arete(int u, int v, int C) {
  compteur++;
  suiv[compteur] = tete[u], vers[compteur] = v, capacite[compteur] = C;
  tete[u] = compteur;
}
queue<int> file;
bool construire() {
  for (int i = 1; i <= n + 2; i++) courant[i] = tete[i], niveau[i] = -1, flot_actuel[i] = 0;
  file.push(S), niveau[S] = 0, flot_actuel[S] = 1e9;
  while (!file.empty()) {
    int x = file.front();
    file.pop();
    parcours(x, i, v) if (niveau[v] == -1 && capacite[i]) niveau[v] = niveau[x] + 1, file.push(v);
  }
  return niveau[T] != -1;
}
void dfs(int x) {
  if (x == T) {
    flux_noeud[x] = flot_actuel[x], resultat += flux_noeud[x];
    return;
  }
  for (int i = courant[x], v = vers[i]; i; v = vers[i = suiv[i]])
    if (niveau[v] == niveau[x] + 1 && capacite[i]) {
      courant[x] = i, flot_actuel[v] = min(flot_actuel[x], capacite[i]), dfs(v);
      capacite[i] -= flux_noeud[v], flot_actuel[x] -= flux_noeud[v];
      capacite[i ^ 1] += flux_noeud[v], flux_noeud[x] += flux_noeud[v];
      flux_noeud[v] = 0;
    }
}
int main() {
#ifndef ONLINE_JUDGE
  freopen("probleme.in", "r", stdin);
  freopen("probleme.out", "w", stdout);
#endif
  n = lire(), m = lire(), S = n + 1, T = n + 2;
  for (int i = 1; i <= n; i++)
    if (!lire())
      ajouter_arete(S, i, 1), ajouter_arete(i, S, 0);
    else
      ajouter_arete(i, T, 1), ajouter_arete(T, i, 0);
  int u, v;
  while (m--) {
    u = lire(), v = lire();
    ajouter_arete(u, v, 1), ajouter_arete(v, u, 0);
    ajouter_arete(u, v, 0), ajouter_arete(v, u, 1);
  }
  while (construire()) dfs(S);
  cout << resultat;
}