首页 > 其他分享 >P1402 酒店之王题解

P1402 酒店之王题解

时间:2024-07-15 10:51:43浏览次数:15  
标签:dep return P1402 题解 之王 rest next int limit

考虑使用网络流。

分为 \(6\) 层。

第一层为源点。

第二层为所有菜的点。

第三层和第四层都表示人。(限制只能选择一个)。

第五层为房子。

第六层为汇点。

#include <bits/stdc++.h>

#define int long long

using namespace std;

const int N = 410, M = 101000, INF = 0x3f3f3f3f3f3f3f3f;

int n, m, S, T;

struct edge {
    int to, next, w;
} e[M];

int head[N], idx = 1;

void add(int u, int v, int w) {
    // cout << u << ' ' << v << ' ' << w << endl;
    idx++, e[idx].to = v, e[idx].next = head[u], e[idx].w = w, head[u] = idx;
    idx++, e[idx].to = u, e[idx].next = head[v], e[idx].w = 0, head[v] = idx;
}

int dep[N];

bool bfs() {
    queue<int> q;
    q.push(S);
    memset(dep, 0x3f, sizeof(dep));
    dep[S] = 1;

    while (q.size()) {
        int t = q.front();
        q.pop();

        for (int i = head[t]; i; i = e[i].next) {
            int to = e[i].to;
            if (dep[to] > dep[t] + 1 && e[i].w) {
                dep[to] = dep[t] + 1;
                q.push(to);
            }
        }
    }
    return dep[T] < INF;
}

int dinic(int u, int limit) {
    if (u == T) return limit;
    int rest = limit;
    for (int i = head[u]; i && rest; i = e[i].next) {
        int to = e[i].to;
        if (dep[to] == dep[u] + 1 && e[i].w) {
            int k = dinic(to, min(rest, e[i].w));
            if (!k) dep[to] = INF;
            rest -= k;
            e[i].w -= k;
            e[i ^ 1].w += k;
        }
    }
    return limit - rest;
}

int p, q;

signed main() {
    // freopen("a.in", "r", stdin);

    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    S = 0, T = N - 1;
    cin >> n >> p >> q;
  
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= p; j++) {
            int x;
            cin >> x;
            if (x) add(j, i + 100, 1);
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= q; j++) {
            int x;
            cin >> x;
            if (x) add(i + 200, j + 300, 1);
        }
    }

    for (int i = 1; i <= 100; i++) add(i + 100, i + 200, 1);
 
    for (int i = 1; i <= 100; i++) add(S, i, 1);
    for (int i = 301; i <= 400; i++) add(i, T, 1);

    int maxflow = 0, flow = 0;
    while (bfs()) while (flow = dinic(S, INF)) maxflow += flow;
    cout << maxflow << '\n';
    return 0;
}

标签:dep,return,P1402,题解,之王,rest,next,int,limit
From: https://www.cnblogs.com/Yuan-Jiawei/p/18302726

相关文章

  • AE莫名的小问题解决办法和基础的操作快捷键分享
    更多macOS实用教程,小白教学点击这里!AdobeAfterEffects,简称AE,是由Adobe公司开发的视频剪辑和设计软件。它是一款用于动画、视觉效果和电影合成的二维半动画软件,广泛应用于电影、电视和网络视频创作。AfterEffects主要用于创建动态图像和视觉特效,被誉为制作动态影像设计不可或......
  • 题解 P5270 无论怎样神树大人都会删库跑路
    题解P5270无论怎样神树大人都会删库跑路题意已经说得很清楚了,我们直接开始讲题。首先考虑一次只插入一个字符。问题只在于我们想要判断最后几个字符是否组成相同,即判断两个可重集合是否相等。这个需求很像字符串哈希的目的(快速判断两个字符串是否相等)。但集合怎么哈希呢?需求......
  • 【力扣 709】转换成小写字母 C++题解(字符串)
    给你一个字符串s,将该字符串中的大写字母转换成相同的小写字母,返回新的字符串。示例1:输入:s=“Hello”输出:“hello”示例2:输入:s=“here”输出:“here”示例3:输入:s=“LOVELY”输出:“lovely”提示:1<=s.length<=100s由ASCII字符集中的可打印字符组......
  • 【力扣 58】最后一个单词的长度 C++题解(字符串)
    给你一个字符串s,由若干单词组成,单词前后用一些空格字符隔开。返回字符串中最后一个单词的长度。单词是指仅由字母组成、不包含任何空格字符的最大子字符串。示例1:输入:s=“HelloWorld”输出:5解释:最后一个单词是“World”,长度为5。示例2:输入:s="flymetot......
  • 【MX-J1-T2】『FLA - III』Ilumina 题解
    题目传送门【MX-J1-T2】『FLA-III』Ilumina思路硬导题。因为\(c=\lfloor\frac{b}{m}\rfloor\),那么\(b\)一定可以表示为\(c\timesm+x\),其中\(0\lex\lem-1\)。又因为\(b=\lfloor\frac{a}{n}\rfloor\),那么\(a\)一定可以表示为\(b\timesn+y\),其中\(0\ley\len......
  • 题解:P10765 「CROI · R2」在相思树下 I
    在发布求救信号后,@我就在这里253发了题解。#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongintt,ans;voidsolve(){ intn,k,x,ans; scanf("%lld%lld",&n,&k); ans=1; intpre=1,behind=n; for(inti=0;i<k;i++......
  • 题解 P1007 独木桥
    link题意\(N\)个人在长度为\(L\)独木桥上走动,桥上的坐标为\(1,2,\cdots,L\),你不知道他们的方向。他们的速度都为\(1\)。当两个人相遇时,他们就分别转身,继续行走。(转身不花费时间)当某人来到\(0\)或\(L+1\)的位置,他就离开了独木桥。给定\(N\)、\(L\)和\(......
  • 2021杭电多校10 D.Pty hates prime numbers题解
    前言暑期第三次组队赛是选的21年杭电多校10,遗憾爆0,被对面队打爆,赛后狠狠补题。这道题的题解,以及网上搜到的其他题解看了好久没看懂,在问了队里大腿多次后,总算磨出来了,这里讲一下我的理解。题意多次询问,每次给定\(n\)和\(k\),如果一个数的质因数里包括前\(k\)个质数,则这个数......
  • NSIS 之 NsDialogs 常见问题解答
    如何启用/禁用控件使用标准NSIS EnableWindow 命令。NSDialogs允许您弹出通过 ${NSD_Create*} 创建的控件的 hwnd (句柄)。EnableWindow 将 hwnd 作为其参数之一。通过它,您可以轻松启用/禁用控件。  !include"nsDialogs.nsh"!include"winmessages.nsh"!incl......
  • 题解:AT_abc362_d [ABC362D] Shortest Path 3
    一句话题意:给定一个带点权的有权无向连通图,求点1到所有其它点的最短路径。首先,只有1一个起点,所以是单源最短路,又因为最大是\(2\times10^5\),所以是优先队列(堆)优化过后的Dijkstra。所以,我们只需要解决点权的问题就好了。一种显而易见的想法是把与这条边的边权加上起终点......