題目大意:有N頭牛,F種食物,D種飲料,每種食物和飲料都只有一
現在給出每頭牛所喜愛的食物和飲料,問最多有多少頭牛能同時得到自己喜歡的食物和飲料
解題思路:將牛拆成兩點,權值為1,一條和喜歡的食物相連,權值為1,另一條和喜歡的飲料相連,權值為1
然後將所有食物和超級源點相連,權值為1
將所有的飲料喝超級匯點相連,權值為1
ISAP
#include
#include
#include
#include
#include
using namespace std;
#define N 1010
#define INF 0x3f3f3f3f
struct Edge {
int from, to, cap, flow;
Edge() {}
Edge(int from, int to, int cap, int flow): from(from), to(to), cap(cap), flow(flow) {}
};
struct ISAP {
int p[N], num[N], cur[N], d[N];
int t, s, n, m;
bool vis[N];
vector G[N];
vector edges;
void init(int n) {
this->n = n;
for (int i = 0; i <= n; i++) {
G[i].clear();
d[i] = INF;
}
edges.clear();
}
void AddEdge(int from, int to, int cap) {
edges.push_back(Edge(from, to, cap, 0));
edges.push_back(Edge(to, from, 0, 0));
int m = edges.size();
G[from].push_back(m - 2);
G[to].push_back(m - 1);
}
bool BFS() {
memset(vis, 0, sizeof(vis));
queue Q;
d[t] = 0;
vis[t] = 1;
Q.push(t);
while (!Q.empty()) {
int u = Q.front();
Q.pop();
for (int i = 0; i < G[u].size(); i++) {
Edge &e = edges[G[u][i] ^ 1];
if (!vis[e.from] && e.cap > e.flow) {
vis[e.from] = true;
d[e.from] = d[u] + 1;
Q.push(e.from);
}
}
}
return vis[s];
}
int Augment() {
int u = t, flow = INF;
while (u != s) {
Edge &e = edges[p[u]];
flow = min(flow, e.cap - e.flow);
u = edges[p[u]].from;
}
u = t;
while (u != s) {
edges[p[u]].flow += flow;
edges[p[u] ^ 1].flow -= flow;
u = edges[p[u]].from;
}
return flow;
}
int Maxflow(int s, int t) {
this->s = s; this->t = t;
int flow = 0;
BFS();
if (d[s] > n)
return 0;
memset(num, 0, sizeof(num));
memset(cur, 0, sizeof(cur));
for (int i = 0; i < n; i++)
if (d[i] < INF)
num[d[i]]++;
int u = s;
while (d[s] <= n) {
if (u == t) {
flow += Augment();
u = s;
}
bool ok = false;
for (int i = cur[u]; i < G[u].size(); i++) {
Edge &e = edges[G[u][i]];
if (e.cap > e.flow && d[u] == d[e.to] + 1) {
ok = true;
p[e.to] = G[u][i];
cur[u] = i;
u = e.to;
break;
}
}
if (!ok) {
int Min = n;
for (int i = 0; i < G[u].size(); i++) {
Edge &e = edges[G[u][i]];
if (e.cap > e.flow)
Min = min(Min, d[e.to]);
}
if (--num[d[u]] == 0)
break;
num[d[u] = Min + 1]++;
cur[u] = 0;
if (u != s)
u = edges[p[u]].from;
}
}
return flow;
}
};
//cow 1 -- 2 * n
//food 2 * n + 1 --- 2 * n + f
//drink 2 * n + f + 1 --- 2 * n + f + d
//start 0
//sink 2 * n + f + d + 1
ISAP isap;
int n, f, d;
void init() {
int s = 0, t = 2 * n + d + f + 1;
isap.init(t);
for (int i = 1; i <= f; i++) {
isap.AddEdge(0, 2 * n + i, 1);
}
for (int i = 1; i <= d; i++) {
isap.AddEdge(2 * n + f + i, t, 1);
}
int fi, di, x;
for (int i = 1; i <= n; i++) {
scanf(%d%d, &fi, &di);
isap.AddEdge(i, n + i, 1);
for (int j = 0; j < fi; j++) {
scanf(%d, &x);
isap.AddEdge(2 * n + x, i, 1);
}
for (int j = 0; j < di; j++) {
scanf(%d, &x);
isap.AddEdge(n + i, 2 * n + f + x, 1);
}
}
int flow = isap.Maxflow(s, t);
printf(%d
, flow);
}
int main() {
while (scanf(%d%d%d, &n, &f, &d) != EOF) {
init();
}
return 0;
}
Dinic
#include
#include
#include
#include
#include
using namespace std;
#define N 1010
#define INF 0x3f3f3f3f
struct Edge{
int from, to, cap, flow;
Edge() {}
Edge(int from, int to, int cap, int flow) : from(from), to(to), cap(cap), flow(flow) {}
};
struct Dinic{
int n, m, s, t;
vector edges;
vector G[N];
bool vis[N];
int d[N], cur[N];
void init(int n) {
this->n = n;
for (int i = 0; i <= n; i++) {
G[i].clear();
}
edges.clear();
}
void AddEdge(int from, int to, int cap) {
edges.push_back(Edge(from, to, cap, 0));
edges.push_back(Edge(to, from, 0, 0));
int m = edges.size();
G[from].push_back(m - 2);
G[to].push_back(m - 1);
}
bool BFS() {
memset(vis, 0, sizeof(vis));
queue Q;
Q.push(s);
vis[s] = 1;
d[s] = 0;
while (!Q.empty()) {
int u = Q.front();
Q.pop();
for (int i = 0; i < G[u].size(); i++) {
Edge &e = edges[G[u][i]];
if (!vis[e.to] && e.cap > e.flow) {
vis[e.to] = true;
d[e.to] = d[u] + 1;
Q.push(e.to);
}
}
}
return vis[t];
}
int DFS(int x, int a) {
if (x == t || a == 0)
return a;
int flow = 0, f;
for (int i = cur[x]; i < G[x].size(); i++) {
Edge &e = edges[G[x][i]];
if (d[x] + 1 == d[e.to] && (f = DFS(e.to, min(a, e.cap - e.flow))) > 0) {
e.flow += f;
edges[G[x][i] ^ 1].flow -= f;
flow += f;
a -= f;
if (a == 0)
break;
}
}
return flow;
}
int Maxflow(int s, int t) {
this->s = s; this->t = t;
int flow = 0;
while (BFS()) {
memset(cur, 0, sizeof(cur));
flow += DFS(s, INF);
}
return flow;
}
};
Dinic dinic;
//cow 1 -- 2 * n
//food 2 * n + 1 --- 2 * n + f
//drink 2 * n + f + 1 --- 2 * n + f + d
//start 0
//sink 2 * n + f + d + 1
int n, f, d;
void init() {
int s = 0, t = 2 * n + d + f + 1;
dinic.init(t);
for (int i = 1; i <= f; i++) {
dinic.AddEdge(0, 2 * n + i, 1);
}
for (int i = 1; i <= d; i++) {
dinic.AddEdge(2 * n + f + i, t, 1);
}
int fi, di, x;
for (int i = 1; i <= n; i++) {
scanf(%d%d, &fi, &di);
dinic.AddEdge(i, n + i, 1);
for (int j = 0; j < fi; j++) {
scanf(%d, &x);
dinic.AddEdge(2 * n + x, i, 1);
}
for (int j = 0; j < di; j++) {
scanf(%d, &x);
dinic.AddEdge(n + i, 2 * n + f + x, 1);
}
}
int flow = dinic.Maxflow(s, t);
printf(%d
, flow);
}
int main() {
while (scanf(%d%d%d, &n, &f, &d) != EOF) {
init();
}
return 0;
}
EK
#include
#include
#include
#include
#include
using namespace std;
#define N 1010
#define INF 0x3f3f3f3f
struct Edge{
int from, to, cap, flow;
Edge() {}
Edge(int from, int to, int cap, int flow): from(from), to(to), cap(cap), flow(flow){}
};
struct EK{
vector G[N];
vector edges;
int s, t, n, m, p[N];
bool vis[N];
void init(int n) {
this->n = n;
for (int i = 0; i <= n; i++)
G[i].clear();
edges.clear();
}
void AddEdge(int from, int to, int cap) {
edges.push_back(Edge(from, to, cap, 0));
edges.push_back(Edge(to, from, 0, 0));
m = edges.size();
G[from].push_back(m - 2);
G[to].push_back(m - 1);
}
bool BFS() {
queue q;
memset(vis, 0, sizeof(vis));
vis[s] = 1;
q.push(s);
while (!q.empty()) {
int u = q.front();
q.pop();
for (int i = 0; i < G[u].size(); i++) {
Edge &e = edges[G[u][i]];
if (!vis[e.to] && e.cap > e.flow) {
vis[e.to] = true;
p[e.to] = G[u][i];
if (e.to == t)
return true;
q.push(e.to);
}
}
}
return false;
}
int Augment() {
int flow = INF, u = t;
while (u != s) {
Edge &e = edges[p[u]];
flow = min(flow, e.cap - e.flow);
u = e.from;
}
u = t;
while (u != s) {
edges[p[u]].flow += flow;
edges[p[u] ^ 1].flow -= flow;
u = edges[p[u]].from;
}
return flow;
}
int Maxflow(int s, int t) {
this->s = s; this->t = t;
int flow = 0;
while (BFS()) {
flow += Augment();
}
return flow;
}
};
EK ek;
//cow 1 -- 2 * n
//food 2 * n + 1 --- 2 * n + f
//drink 2 * n + f + 1 --- 2 * n + f + d
//start 0
//sink 2 * n + f + d + 1
int n, f, d;
void init() {
int s = 0, t = 2 * n + d + f + 1;
ek.init(t);
for (int i = 1; i <= f; i++) {
ek.AddEdge(0, 2 * n + i, 1);
}
for (int i = 1; i <= d; i++) {
ek.AddEdge(2 * n + f + i, t, 1);
}
int fi, di, x;
for (int i = 1; i <= n; i++) {
scanf(%d%d, &fi, &di);
ek.AddEdge(i, n + i, 1);
for (int j = 0; j < fi; j++) {
scanf(%d, &x);
ek.AddEdge(2 * n + x, i, 1);
}
for (int j = 0; j < di; j++) {
scanf(%d, &x);
ek.AddEdge(n + i, 2 * n + f + x, 1);
}
}
int flow = ek.Maxflow(s, t);
printf(%d
, flow);
}
int main() {
while (scanf(%d%d%d, &n, &f, &d) != EOF) {
init();
}
return 0;
}