# Hihocoder1393 网络流三·二分图多重匹配（最大流）

## 2018 年 08 月 01 日 • 阅读: 1589 • 图论 • 阅读设置

• 时间限制:10000ms
• 单点时限:1000ms
• 内存限制:256MB

### 样例输入

2
4 3
1 2 2
1 2 1 2
2 2 1 3
1 1 2
1 2 2 3
4 3
2 2 2
1 2 1 2
2 2 1 3
1 1 2
1 2 2 3

### 样例输出

Yes
No

### 链接

http://hihocoder.com/problemset/problem/1393

### 代码

StatusAccepted
Time16ms
Memory1024kB
Length2679
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;
const int maxn = 210;

int n, m;
struct Edge
{
int u, v, cap;
Edge() {}
Edge(int u, int v, int cap): u(u), v(v), cap(cap) {}
}edge[maxn*maxn];

int R, S, T;
vector <int> E[maxn]; //边集
int dis[maxn];
int current[maxn];

void addedge(int u, int v, int cap)
{
E[u].push_back(R);
edge[R++] = Edge(u, v, cap); // 正向边
E[v].push_back(R);
edge[R++] = Edge(v, u, 0); // 方向边容量为0
// 正向边下标通过异或就得到反向边下标, 2 ^ 1 == 3 ; 3 ^ 1 == 2，R从0开始
}

int bfs()
{
memset(dis, 0x3f, sizeof(dis)); // 初始化为0x3f3f3f3f
queue <int> Q;
Q.push(S);
dis[S] = 0;
while (!Q.empty())
{
int u = Q.front();
Q.pop();
for (int i = 0; i < E[u].size(); ++i)
{
Edge &e = edge[E[u][i]];
if (e.cap > 0 && dis[e.v] == 0x3f3f3f3f)
{
dis[e.v] = dis[u] + 1;
Q.push(e.v);
}
}
}
return dis[T] < 0x3f3f3f3f; // 返回是否能够到达汇点
}

int dinic(int u, int maxflow)
{
if (u == T)
return maxflow;
for (int i = current[u]; i < E[u].size(); ++i) // 当前弧优化，保存u点增广到了第几条边
{
current[u] = i;
Edge &e = edge[E[u][i]];
if (dis[e.v] == dis[u] + 1 && e.cap > 0)
{
int flow = dinic(e.v, min(maxflow, e.cap));
if (flow)
{
e.cap -= flow; // 正向边流量减少
edge[E[u][i] ^ 1].cap += flow; // 方向边流量增加
return flow;
}
}
}
return 0;
}

int DINIC()
{
int ans = 0;
while (bfs())
{
int flow;
memset(current, 0, sizeof(current)); // bfs后清空当前弧数组
while (flow = dinic(S, 0x3f3f3f3f)) // 一次bfs可以进行多次增广
ans += flow;
}
return ans;
}

int main()
{
int t, u, cap, k;
scanf("%d", &t);
while (t--)
{
scanf("%d%d", &n, &m);
R = 0, S = 0, T = n + m + 1; // 边序号，源点，汇点
for (int i = 0; i <= T; ++i)
E[i].clear();
memset(edge, 0, sizeof(edge));
int sum = 0;
for (int i = 1; i <= m; ++i)
{
scanf("%d", &cap);
sum += cap;
}
for (int i = 1; i <= n; ++i)
{
scanf("%d%d", &cap, &k);
for (int j = 0; j < k; ++j)
{
scanf("%d", &u);
}
}
if (DINIC() == sum) // 符合要求
printf("Yes\n");
else
printf("No\n");
}
return 0;
}

The end.
2018-08-01 星期三

### 提示：二分图多重匹配

s-A[i]：这一类边的流量表示了A[i]参加的项目数量。

A[i]-B[j]：这一类边的流量表示了A[i]是否参加项目B[j]，若参加则流量为1，否则流量为0。

B[j]-t：这一类边的流量表示了参加比赛项目B[j]的选手数量。