首页 > 其他分享 >POI2005 KOS-Dicing

POI2005 KOS-Dicing

时间:2024-04-04 17:11:34浏览次数:27  
标签:dep return POI2005 flow ret int KOS Dicing define

网络流 #二分 #POI #Year2005

考虑二分答案,用 \(Dinic\) 来 \(check\)

具体来说,就是对每一个人限制流量,然后检查能不能把所有场全部流满

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define ull unsigned long long
#define ALL(a) (a).begin(), (a).end()
#define pb push_back
#define mk make_pair
#define pii pair<int, int>
#define pis pair<int, string>
#define sec second
#define fir first
#define sz(a) int((a).size())
#define Yes cout << "Yes" << endl
#define YES cout << "YES" << endl
#define No cout << "No" << endl
#define NO cout << "NO" << endl
#define debug(x) cerr << #x << ": " << x << endl
#define double long double
#define mms(arr, n) memset(arr, n, sizeof(arr))
#define rep(i, a, n) for (int i = (a); i <= (n); ++i)
#define per(i, n, a) for (int i = (n); i >= (a); --i)
int max(int a, int b) {
    if (a > b)
        return a;
    return b;
}
int min(int a, int b) {
    if (a < b)
        return a;
    return b;
}
const int INF = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1000000007;
const int N = 2e5 + 10;

struct MF {
    struct edge {
        int v, nxt, cap, flow;
    } e[N];

    int fir[N], cnt = 0;

    int n, S, T;
    int maxflow = 0;
    int dep[N], cur[N];

    void init() {
        // cerr << "flag" << endl;
        memset(fir, -1, sizeof(fir));
        cnt = 0;
    }

    void addedge(int u, int v, int w) {
        e[cnt] = { v, fir[u], w, 0 };
        fir[u] = cnt++;
        e[cnt] = { u, fir[v], 0, 0 };
        fir[v] = cnt++;
    }

    bool bfs() {
        queue<int> q;
        memset(dep, 0, sizeof(int) * (n + 1));

        dep[S] = 1;
        q.push(S);
        while (q.size()) {
            int u = q.front();
            q.pop();
            for (int i = fir[u]; ~i; i = e[i].nxt) {
                int v = e[i].v;
                if ((!dep[v]) && (e[i].cap > e[i].flow)) {
                    dep[v] = dep[u] + 1;
                    q.push(v);
                }
            }
        }
        return dep[T];
    }

    int dfs(int u, int flow) {
        if ((u == T) || (!flow))
            return flow;

        int ret = 0;
        for (int &i = cur[u]; ~i; i = e[i].nxt) {
            int v = e[i].v, d;
            if ((dep[v] == dep[u] + 1) && (d = dfs(v, min(flow - ret, e[i].cap - e[i].flow)))) {
                ret += d;
                e[i].flow += d;
                e[i ^ 1].flow -= d;
                if (ret == flow)
                    return ret;
            }
        }
        return ret;
    }

    void dinic() {
        while (bfs()) {
            memcpy(cur, fir, sizeof(int) * (n + 1));
            maxflow += dfs(S, INF);
            // cerr << maxflow << endl;
        }
    }
} mf;

// bool st;
int n, m;
pii a[N];
// bool en;

bool check(int x) {
    mf.init();
    mf.n = n + m + 1;
    mf.S = 0;
    mf.maxflow = 0;
    mf.T = n + m + 1;
    for (int i = 1; i <= n; i++) mf.addedge(0, i, x);
    for (int i = 1; i <= m; i++) {
        mf.addedge(a[i].first, i + n, 1);
        mf.addedge(a[i].second, i + n, 1);
        mf.addedge(i + n, n + m + 1, 1);
    }
    mf.dinic();
    return mf.maxflow >= m;
}

void solve() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) cin >> a[i].first >> a[i].second;
    int l = 0, r = m;
    while (l < r) {
        int mid = l + r >> 1;
        if (check(mid))
            r = mid;
        else
            l = mid + 1;
    }
    cout << l << endl;
}

signed main() {
    // freopen(".in","r",stdin);
    // freopen(".out","w",stdout);
    // cerr<<(&en-&st)/1024.0/1024.0<<endl;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int testcase = 1;
    // cin >> testcase;
    while (testcase--) solve();
    return 0;
}

标签:dep,return,POI2005,flow,ret,int,KOS,Dicing,define
From: https://www.cnblogs.com/xiaruize/p/18114352

相关文章

  • POI2005 KOS-Dicing
    网络流#二分考虑二分答案,用\(Dinic\)来\(check\)具体来说,就是对每一个人限制流量,然后检查能不能把所有场全部流满#include<bits/stdc++.h>usingnamespacestd;#defineintlonglong#defineullunsignedlonglong#defineALL(a)(a).begin(),(a).end()#definepb......
  • POI2005 KOS-Dicing
    网络流#二分考虑二分答案,用\(Dinic\)来\(check\)具体来说,就是对每一个人限制流量,然后检查能不能把所有场全部流满#include<bits/stdc++.h>usingnamespacestd;#defineintlonglong#defineullunsignedlonglong#defineALL(a)(a).begin(),(a).end()#definepb......
  • [POI2005] SZA-Template
    本想尝试一下朴素算法能得多少分,没想到直接过了……亲手构造了n=80000的全a数据,确定程序的复杂度的确是错的考虑通过KMP算法构建的“失配树”,大概可以用双向链表维护前驱后继点击查看代码#include<bits/stdc++.h>usingnamespacestd;intne[500005],n;boolpd(intj){......
  • OSCP(扩展篇靶机SickOS1.2)
    第一步:nmap、nikto、dirb   第二步:利用curl实现文件上传http://192.168.107.149/test/检查一下是否发现了任何可用的可利用的http方法curl-v-XOPTIONShttp://192.168.107.149/test/ 包括了PUT用法让我们尝试上传shellcurl-v-XPUT-d'<?phpsystem($_GET......
  • OSCP(扩展篇靶机SickOS1.1)
    第一步:nmap和niktonikto:https://zhuanlan.zhihu.com/p/124246499 8080http-proxy我们是利用3128查看nikto是否存在可利用的漏洞nikto-h192.168.107.148--useproxy192.168.107.148:3128扫描目标时,部分目标部署了防护设备,为避免暴露ip可以使用代理进行扫描,nikto支持......
  • Kosaraju 算法学习笔记(求强连通分量)
    写起来简单无比,不比Tarjan香?方法按照[1...n]的顺序在反图(边方向相反)上dfs一遍,出栈时将节点存入数组q[1...n]中按照q[n...1]的顺序在原图上dfs一遍,每次遍历就是一个新的强联通分量为什么是正确的?核心在于封死连通分量往外走的路。如果原图u-->v有一条边,且u和v不在同一个......
  • 【倍增】P3422 [POI2005]LOT-A Journey to Mars 题解
    P3422一道有点意思的题。看到是一个环,先破环为链,即\(a_{n+i}=a_i,b_{n+i}=b_i\),此时就只需要跳到\(x+n\)而无需判环了。如果顺时针走:令\(sum_i=\sum\limits_{j=1}^{i}{a_j-b_j}\),当能从\(x\)跳到\(x+n\)时,有\[sum_{x-1}\lesum_x,sum_{x-1}\lesum_{x+1},\dot......
  • [COCI2011-2012#6] KOŠARE
    Problem有\(N\)个箱子、\(M\)种礼物,第\(i\)个箱子里有\(K_i\)种礼物。需要选出一些箱子,要求每一种礼物至少出现在一个箱子中。求可行的方案数\(mod\)\(10^9+7\)。Input输入第一行,包含正整数\(N(1\leN\le10^6)\)和\(M(1\leM\le20)\)。接下来的\(N\)......
  • 题解 [POI2005] SZA-Template
    题目链接充分暴露出对\(border\)结合\(dp\)理解的不足。先来推结论,一个字符串的印章一定是其\(border\),因为只有这样才可能兼顾首尾,但是他的\(border\)不一定是其印章,两个条件不能互推。设\(dp_i\)表示前\(i\)个字符串的最小印章长度。现在考虑如何转移。\(dp_i\)......
  • Inspur KOS 龙蜥衍生版面向智慧新媒体转型的探索与实践 | 龙蜥案例
    编者按:日前,龙蜥社区理事单位浪潮信息正式对外发布基于龙蜥操作系统(Anolis OS)的服务器操作系统 Inspur KOS,并基于InspurKOS推出可视化迁移方案C2K,该方案能够将用户应用安全可靠地切换到InspurKOS,满足用户CentOS迁移替代需求。本案例为InspurKOS在传媒产业中的应用实践......