描述 Description
幼儿园里有 n 个小朋友打算通过投票来决定睡不睡午觉。对他们来说，这个问题并不是很重要，于是他们决定发扬谦让精神。虽然每个人都有自己的主见，但是为了照顾一下自己朋友的想法，他们也可以投和自己本来意愿相反的票。我们定义一次投票的冲突数为好朋友之间发生冲突的总数加上和所有和自己本来意愿发生冲突的人数。 我们的问题就是，每位小朋友应该怎样投票，才能使冲突数最小？
输入格式 InputFormat
第一行只有两个整数 n，m，保证有 2≤n≤300，1≤m≤n(n-1)/2。其中 n 代表总人数，m 代表好朋友的对数。文件第二行有 n 个整数，第 i 个整数代表第 i 个小朋友的意愿，当它为 1 时表示同意睡觉，当它为 0 时表示反对睡觉。接下来文件还有 m 行，每行有两个整数 i，j。表示 i，j 是一对好朋友，我们保证任何两对 i，j 不会重复。
输出格式 OutputFormat
只需要输出一个整数，即可能的最小冲突数。
样例输入 SampleInput
9 6
1 1 1 1 1 0 1 0 0
7 9
4 3
1 8
2 7
6 3
3 2
样例输出 SampleOutput
3
源点与同意的人建边容量无限，反对的人与汇点建边容量无限，互相是朋友的人建边容量一，求最小割。
#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;
const int inf = 0x7fffffff / 27.11;
const int maxn = 305;
const int maxm = 3 * maxn * maxn;
int i, j, t, n, m, l, r, k, z, y, x;
struct edge
{
int to, fl, nx;
} e[maxm];
int head[maxn], dis[maxn], used[maxn], cur[maxn];
int cnt, num;
deque <int> q;
inline void ins(int u, int v, int f)
{
e[cnt] = (edge)
{
v, f, head[u]
}; head[u] = cnt++;
e[cnt] = (edge)
{
u, 0, head[v]
}; head[v] = cnt++;
}
inline bool bfs(int s, int t, int tim)
{
int i, u, v;
while (!q.empty()) q.pop_front();
dis[s] = 0; used[s] = tim;
q.push_back(s);
while (!q.empty())
{
u = q.front(); q.pop_front();
for (i = head[u]; i != -1; i = e[i].nx)
{
v = e[i].to;
if (used[v] != tim && e[i].fl > 0)
{
used[v] = tim;
dis[v] = dis[u] + 1;
q.push_back(v);
}
}
}
return (used[t] == tim);
}
int dfs(int u, int t, int flow)
{
int v, d, f = flow;
if (u == t) return flow;
for (int &i = cur[u]; i != -1 && f > 0; i = e[i].nx)
{
v = e[i].to;
if (dis[v] == dis[u] + 1 && e[i].fl > 0)
{
d = dfs(v, t, min(f, e[i].fl));
e[i].fl -= d; e[i ^ 1].fl += d;
f -= d;
}
}
return flow - f;
}
inline void dinic(int s, int t)
{
int ans = 0;
while (bfs(s, t, ++num))
{
memcpy(cur, head, sizeof(head));
ans += dfs(s, t, inf);
}
printf("%d\n", ans);
}
int main()
{
cnt = num = 0;
memset(head, -1, sizeof(head));
scanf("%d%d", &n, &m);
for (i = 1; i <= n; i++)
{
scanf("%d", &x);
if (x == 1) ins(0, i, 1);
else ins(i, n + 1, 1);
}
for (i = 1; i <= m; i++)
{
scanf("%d%d", &x, &y);
ins(x, y, 1);
ins(y, x, 1);
}
dinic(0, n + 1);
return 0;
}