题意：两个队伍，有一些边相连，问最大组对数以及最多女生数量
分析：费用流模板题，设置两个超级源点和汇点，边的容量为１，费用为男生数量．建边不能重复建边否则会Ｔ．ｚｋｗ费用流在稠密图跑得快，普通的最小费用最大流也能过，只是相对来说慢了点．
#include <bits/stdc++.h> const int N = 5e2 + 5;
const int INF = 0x3f3f3f3f;
struct Min_Cost_Max_Flow {
struct Edge {
int from, to, cap, flow, cost;
};
std::vector<Edge> edges;
std::vector<int> G[N];
bool vis[N];
int d[N], p[N], a[N];
int n, m; void init(int n) {
this->n = n;
for (int i=0; i<=n; ++i) {
G[i].clear ();
}
edges.clear ();
}
void add_edge(int from, int to, int cap, int cost) {
edges.push_back ((Edge) {from, to, cap, 0, cost});
edges.push_back ((Edge) {to, from, 0, 0, -cost});
m = edges.size ();
G[from].push_back (m - 2);
G[to].push_back (m - 1);
}
bool SPFA(int s, int t, int &flow, int &cost) {
memset (d, INF, sizeof (d));
memset (vis, false, sizeof (vis));
memset (p, -1, sizeof (p));
d[s] = 0; vis[s] = true; p[s] = 0; a[s] = INF; std::queue<int> que; que.push (s);
while (!que.empty ()) {
int u = que.front (); que.pop ();
vis[u] = false;
for (int i=0; i<G[u].size (); ++i) {
Edge &e = edges[G[u][i]];
if (e.cap > e.flow && d[e.to] > d[u] + e.cost) {
d[e.to] = d[u] + e.cost;
p[e.to] = G[u][i];
a[e.to] = std::min (a[u], e.cap - e.flow);
if (!vis[e.to]) {
vis[e.to] = true;
que.push (e.to);
}
}
}
} if (d[t] == INF) {
return false;
}
flow += a[t];
cost += d[t] * a[t];
int u = t;
while (u != s) {
edges[p[u]].flow += a[t];
edges[p[u]^1].flow -= a[t];
u = edges[p[u]].from;
}
return true;
}
void run(int s, int t, int &flow, int &cost) {
flow = cost = 0;
while (SPFA (s, t, flow, cost)); printf ("%d %d\n", flow, 2 * flow - cost);
for (int i=0; i<edges.size (); i+=2) {
if (edges[i].from == s || edges[i].to == t || edges[i].flow == 0) {
continue;
}
printf ("%d %d\n", edges[i].from, edges[i].to);
}
}
};
Min_Cost_Max_Flow mcmf;
char group[N], sex[N];
bool list[N];
int n, m; int main() {
int T; scanf ("%d", &T);
while (T--) {
scanf ("%d", &n);
scanf ("%s", group + 1);
scanf ("%s", sex + 1); mcmf.init (n + 1);
int s = 0, t = n + 1;
for (int i=1; i<=n; ++i) {
if (group[i] == '0') {
mcmf.add_edge (s, i, 1, 0);
} else {
mcmf.add_edge (i, t, 1, 0);
}
int m; scanf ("%d", &m);
memset (list, false, sizeof (list));
for (int j=1; j<=m; ++j) {
int v; scanf ("%d", &v);
list[v] = true;
}
if (group[i] == '1') {
continue;
}
int cost = (sex[i] == '1');
for (int j=1; j<=n; ++j) {
if (list[j] || group[i] == group[j]) {
continue;
}
mcmf.add_edge (i, j, 1, cost + (sex[j] == '1'));
}
}
int flow, cost;
mcmf.run (s, t, flow, cost);
} return 0;
}