其实我最近一直在搞网络瘤，虽然并没有发博客
酒店之王
这道题并不难，
我们一眼就能看出是一道网络瘤（bushi），
建模也没有难度，
就是把每个人和他喜欢的菜连起来，
再和他喜欢的房子连起来，
燃鹅，
出现了一个小问题，
就是每个人可能在连线的过程中被重复利用。
其实我最初的解决方案是先见一个超级源，
再将每个人和超级源之间建一条边，
将人连接到他喜欢的房子，
再将他喜欢的房子连接到他喜欢的菜。
于是乎，
就有了下面的代码：
#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 2e6 + 5;
int n, p, q, cai[105][105], fang[105][105];
int tot = 1, to[maxn], cap[maxn], nxt[maxn], head[maxn];
int s, t, now[maxn], d[maxn], maxflow;
queue <int> qq;
void add(int x, int y, int z){
to[++tot] = y, cap[tot] = z, nxt[tot] = head[x], head[x] = tot;
}
bool BFS(){
memset(d, 0, sizeof(d));
while (qq.size()) qq.pop();
qq.push(s); d[s] = 1, now[s] = head[s];
while (qq.size()){
int x = qq.front(); qq.pop();
for (int i = head[x]; i; i = nxt[i]){
int y = to[i];
if (!d[y] && cap[i]){
qq.push(y);
d[y] = d[x] + 1;
now[y] = head[y];
if (y == t) return true;
}
}
}
return false;
}
int dinic(int x, int flow){
if (x == t || flow == 0) return flow;
int rest = flow, k;
int& i = now[x];
for (; i && rest; i = nxt[i]){
int y = to[i];
if (d[y] == d[x] + 1 && cap[i]){
k = dinic(y, min(rest, cap[i]));
if (!k) d[y] = 0;
cap[i] -= k;
cap[i ^ 1] += k;
rest -= k;
}
}
now[x] = i;
return flow - rest;
}
int main(){
scanf("%d%d%d", &n, &p, &q); s = 0, t = n + p + q + 1;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= p; j++)
scanf("%d", &fang[i][j]);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= q; j++)
scanf("%d", &cai[i][j]);
for (int i = 1; i <= n; i++){
add(s, i, 1); add(i, s, 0);
for (int j = 1; j <= p; j++)
if (fang[i][j]){
add(i, j + n, 1); add(j + n, i, 0);
for (int k = 1; k <=q; k++)
if (cai[i][k]){
add(j + n, k + n + p, 1); add(k + n + p, j + n, 0);
add(k + n + p, t, 1); add(t, k + n + p, 0);
}
}
}
int flow = 0;
while (BFS())
while (flow = dinic(s, 100)) maxflow += flow;
printf("%d", maxflow);
return 0;
}
这样居然可以拿到(40pts)！！！
其实这是一个错误的代码，
毕竟样例都没过（什么！？你问我样例都没过为什么要交？因为我觉得我做对了阿巴阿巴
尽管思路有可取之处。
为什么说这是错误的呢？
因为我们发现，
如果这样建边的话，
我们中间的节点（也就是每个房）其实可以用多次，
因为他没有点权。
什么！！！
没有点权？？？
那就加上呗！
bulubula
赛高！
新代码！！！
#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 2e6 + 5;
int n, p, q, cai[105][105], fang[105][105];
int tot = 1, to[maxn], cap[maxn], nxt[maxn], head[maxn];
int s, t, now[maxn], d[maxn], maxflow;
queue <int> qq;
void add(int x, int y, int z){
to[++tot] = y, cap[tot] = z, nxt[tot] = head[x], head[x] = tot;
}
bool BFS(){
memset(d, 0, sizeof(d));
while (qq.size()) qq.pop();
qq.push(s); d[s] = 1, now[s] = head[s];
while (qq.size()){
int x = qq.front(); qq.pop();
for (int i = head[x]; i; i = nxt[i]){
int y = to[i];
if (!d[y] && cap[i]){
qq.push(y);
d[y] = d[x] + 1;
now[y] = head[y];
if (y == t) return true;
}
}
}
return false;
}
int dinic(int x, int flow){
if (x == t || flow == 0) return flow;
int rest = flow, k;
int& i = now[x];
for (; i && rest; i = nxt[i]){
int y = to[i];
if (d[y] == d[x] + 1 && cap[i]){
k = dinic(y, min(rest, cap[i]));
if (!k) d[y] = 0;
cap[i] -= k;
cap[i ^ 1] += k;
rest -= k;
}
}
now[x] = i;
return flow - rest;
}
int main(){
scanf("%d%d%d", &n, &p, &q); s = 0, t = n + p + q + 1;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= p; j++)
scanf("%d", &fang[i][j]);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= q; j++)
scanf("%d", &cai[i][j]);
for (int i = 1; i <= n; i++){
add(s, i, 1); add(i, s, 0);
for (int j = 1; j <= p; j++)
if (fang[i][j]){
add(i, j + n, 1); add(j + n, i, 0);
for (int k = 1; k <=q; k++)
if (cai[i][k]){
add(j + t, k + n + p, 1); add(k + n + p, j + t, 0);
add(k + t + p, t, 1); add(t, k + t + p, 0);
}
}
}
for (int i = 1; i <= p; i++){
add(n + i, t + i, 1); add(t + i, n + i, 0);
}
for (int i = 1; i <= q; i++){
add(n + p + i, t + p + i, 1); add(t + p + i, n + p + i, 0);
}
int flow = 0;
while (BFS())
while (flow = dinic(s, 100)) maxflow += flow;
printf("%d", maxflow);
return 0;
}
这里我们把每道菜和房子加上了点权，（拆边
然后自信提交。
纳尼！！！
才(70pts)？？？
此时此刻……
我陷入了沉思……
突然！
很快啊！
我想到了一个非常严重的问题，
我的边可能被重复利用！
比如我将1号和他喜欢的菜还有房子连边，
其他人仍然可以用这条边！
所以这种建边方式也是错的。
如何避免边也被重复利用呢？
因为每道菜和房子都会被很多人连边，
所以我们不能让菜和房子连边，
（为了避免不必要的牺牲bushi
所以！！！
这里我们想到让人和菜还有房子分别连边，
这样的话，
我们就让超级源和超级汇分别连向房子和菜，
然后把人放在中间。
由于我真的是太激动了，
直接交了一发。
#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 1e6 + 5;
int n, p, q, cai[105][105], fang[105][105];
int tot = 1, to[maxn], cap[maxn], nxt[maxn], head[maxn];
int s, t, now[maxn], d[maxn], maxflow;
queue <int> qq;
void add(int x, int y, int z){
to[++tot] = y, cap[tot] = z, nxt[tot] = head[x], head[x] = tot;
}
bool BFS(){
memset(d, 0, sizeof(d));
while (qq.size()) qq.pop();
qq.push(s); d[s] = 1, now[s] = head[s];
while (qq.size()){
int x = qq.front(); qq.pop();
for (int i = head[x]; i; i = nxt[i]){
int y = to[i];
if (!d[y] && cap[i]){
qq.push(y);
d[y] = d[x] + 1;
now[y] = head[y];
if (y == t) return true;
}
}
}
return false;
}
int dinic(int x, int flow){
if (x == t || flow == 0) return flow;
int rest = flow, k;
int& i = now[x];
for (; i && rest; i = nxt[i]){
int y = to[i];
if (d[y] == d[x] + 1 && cap[i]){
k = dinic(y, min(rest, cap[i]));
if (!k) d[y] = 0;
cap[i] -= k;
cap[i ^ 1] += k;
rest -= k;
}
}
now[x] = i;
return flow - rest;
}
int main(){
scanf("%d%d%d", &n, &p, &q); s = 0, t = 501;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= p; j++)
scanf("%d", &fang[i][j]);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= q; j++)
scanf("%d", &cai[i][j]);
for (int i = 1; i <= n; i++){
for (int j = 1; j <= p; j++)
if (fang[i][j]){
add(j + 100, i, 1); add(i, j + 100, 0);
}
for (int j = 1; j <= q; j++)
if (cai[i][j]){
add(i, j + 200, 1); add(j + 200, i, 0);
}
}
for (int i = 1; i <= p; i++){
add(s, i + 100, 1); add(i + 100, s, 0);
}
for (int i = 1; i <= q; i++){
add(i + 200, t, 1); add(t, i + 200, 0);
}
int flow = 0;
while (BFS())
while (flow = dinic(s, 100)) maxflow += flow;
printf("%d", maxflow);
return 0;
}
然后嘞？
(60pts)！！！（居然还少了(10pts)？！
为什么呢？
因为一个人只能用一次，
所以每个人相当于有(1)的点权，
然后我们把每个人拆开，
将拆出来的两个人连边，
边权为(1)，
再跑一遍(dinic)，
这样就解决了。
代码：
#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 1e5 + 5;
int n, p, q, cai[105][105], fang[105][105];
int tot = 1, to[maxn], cap[maxn], nxt[maxn], head[maxn];
int s, t, now[maxn], d[maxn], maxflow;
queue <int> qq;
void add(int x, int y, int z){
to[++tot] = y, cap[tot] = z, nxt[tot] = head[x], head[x] = tot;
}
bool BFS(){
memset(d, 0, sizeof(d));
while (qq.size()) qq.pop();
qq.push(s); d[s] = 1, now[s] = head[s];
while (qq.size()){
int x = qq.front(); qq.pop();
for (int i = head[x]; i; i = nxt[i]){
int y = to[i];
if (!d[y] && cap[i]){
qq.push(y);
d[y] = d[x] + 1;
now[y] = head[y];
if (y == t) return true;
}
}
}
return false;
}
int dinic(int x, int flow){
if (x == t || flow == 0) return flow;
int rest = flow, k;
int& i = now[x];
for (; i && rest; i = nxt[i]){
int y = to[i];
if (d[y] == d[x] + 1 && cap[i]){
k = dinic(y, min(rest, cap[i]));
if (!k) d[y] = 0;
cap[i] -= k;
cap[i ^ 1] += k;
rest -= k;
}
}
now[x] = i;
return flow - rest;
}
int main(){
scanf("%d%d%d", &n, &p, &q); s = 0, t = 401;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= p; j++)
scanf("%d", &fang[i][j]);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= q; j++)
scanf("%d", &cai[i][j]);
for (int i = 1; i <= n; i++){
for (int j = 1; j <= p; j++)
if (fang[i][j]) add(j + 200, i, 1), add(i, j + 200, 0);
for (int j = 1; j <= q; j++)
if (cai[i][j]) add(i + 100, j + 300, 1), add(j + 300, i + 100, 0);
}
for (int i = 1; i <= n; i++) add(i, i + 100, 1), add(i + 100, i, 0);
for (int i = 1; i <= p; i++) add(s, i + 200, 1), add(i + 200, s, 0);
for (int i = 1; i <= q; i++) add(i + 300, t, 1), add(t, i + 300, 0);
int flow = 0;
while (BFS())
while (flow = dinic(s, 100)) maxflow += flow;
printf("%d", maxflow);
return 0;
}
是不是！
是不是经整理之后的代码好看多了！！！
哈哈哈哈哈！！！（憨批