题解 P2055 【[ZJOI2009]假期的宿舍】

Ireliaღ

2019-05-15 16:49:46

Solution

**ISAP最大流** 二分图匹配,可以使用最大流 ## 建图 - 把每个人拆成入点和出点代表学生和房间,第$i$个人入点为$i$,出点为$n + i$,超级原点为$0$,超级会点为$2n + 1$ - 对于$\forall i \in [1, n]$,从他的入点向出点连接容量为$1$的边 - 对于$\forall i \in \text{{在校生}}$,由于他的房间可以被使用,从$n + i$向$2n + 1$连接容量为$1$的边 - 对于$\forall i \notin \text{在校生}$ 且 $i \notin \text{回家}$,由于$i$需要住宿,从$0$向$i$连接容量为$1$的边 - 对于$\forall i, j \in [1, n]$满足$i,j$互相认识,从$i$向$n + j$连接容量为$1$的边,从$j$向$n + i$连接容量为$1$的边 最后统计一下最大流是否等于所有需要住宿的学生即可 ## 代码 ISAP挺快的,懒得当前弧优化了 ```cpp // luogu-judger-enable-o2 // luogu-judger-enable-o2 #include <iostream> #include <queue> #include <cstring> using namespace std; const int MAXN = 55; const int MAXM = MAXN * MAXN * 4; const int MAXT = 25; const int INF = 0x3f3f3f3f; int T; namespace Graph{ int to[MAXM], val[MAXM], nxt[MAXM], head[MAXN << 1], cnt; int res, s, t, tot, dep[MAXN << 1], gap[MAXN << 1]; void Clear() { cnt = -1; memset(head, -1, sizeof(head)); } void AddEdge(int u, int v, int w) { cnt++; to[cnt] = v; val[cnt] = w; nxt[cnt] = head[u]; head[u] = cnt; cnt++; to[cnt] = u; val[cnt] = 0; nxt[cnt] = head[v]; head[v] = cnt; } void Bfs() { memset(dep, -1, sizeof(dep)); memset(gap, 0, sizeof(gap)); dep[t] = 0; gap[0]++; queue<int> q; q.push(t); while (!q.empty()) { int u = q.front(); q.pop(); for (int i = head[u]; ~i; i = nxt[i]) { int v = to[i]; if (dep[v] != -1) continue; dep[v] = dep[u] + 1; gap[dep[v]]++; q.push(v); } } } int Dfs(int u, int flow) { if (u == t) { res += flow; return flow; } int used = 0; for (int i = head[u]; ~i; i = nxt[i]) { int v = to[i]; if (val[i] && dep[v] == dep[u] - 1) { int mi = Dfs(v, min(val[i], flow - used)); if (mi) { val[i] -= mi; val[i ^ 1] += mi; used += mi; } if (used == flow) return used; } } gap[dep[u]]--; if (gap[dep[u]] == 0) dep[s] = tot + 1; dep[u]++; gap[dep[u]]++; return used; } void Isap() { res = 0; Bfs(); while (dep[s] <= tot) Dfs(s, INF); } } int main() { ios :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> T; while (T--) { Graph :: Clear(); int n, cnt = 0; cin >> n; bool flag[n + 1]; memset(flag, false, sizeof(flag)); Graph :: tot = n * 2 + 2; Graph :: s = 0; Graph :: t = n * 2 + 1; for (int i = 1; i <= n; i++) Graph :: AddEdge(i, n + i, 1); for (int i = 1; i <= n; i++) { int x; cin >> x; if (x == 1) Graph :: AddEdge(n + i, Graph :: t, 1), flag[i] = true; } for (int i = 1; i <= n; i++) { int x; cin >> x; if (x == 0 || !flag[i]) Graph :: AddEdge(Graph :: s, i, 1), cnt++; } for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { int x; cin >> x; if (x == 1) { Graph :: AddEdge(i, n + j, 1); Graph :: AddEdge(j, n + i, 1); } } } Graph :: Isap(); if (Graph :: res < cnt) cout << "T_T" << endl; else cout << "^_^" << endl; } return 0; } ```