学了好久文化课, 来刷(被)水题啦(虐)

转变模型中某些东西代表的含义通常会有惊喜

懵逼的 题目

qwq

扯淡的 题解

最多的最少 显然要二分

然后判定的时候可以用网络流, 发现如果只用点表示参赛的人的话, 没办法去掉一个人和他对手打一架, 他的对手又来打他的情况

昊哥: 你sb吧, 用一排点表示每一场比赛不就行了

我: Orzzz

来给每一个人向起点连上容量位最多赢的次数(二分出来的)的边, 每一个人向他参加的每一场比赛连边, 每一场比赛向终点连边, 然后跑最大流看是否满流即可

沙茶的 代码

/**************************************************************
    Problem: 1532
    User: Cansult
    Language: C++
    Result: Accepted
    Time:2008 ms
    Memory:21940 kb
****************************************************************/

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#define INF (0x7fffffff)
#define MAXN (100000 + 5)
#define MAXM (500000 + 5)
#define rev(i) ((((i) - 1) ^ 1) + 1)
#define cbh(i) ((i) + 10000)
using namespace std;
int s = 0, t = MAXN - 1;
struct edg
{
    int from, to, next, cap, flow;
}b[MAXM << 1];
int g[MAXN], cntb, n, m, dis[MAXN];
void adn(int from, int to, int cap)
{
    b[++cntb].next = g[from];
    b[cntb].from = from, b[cntb].to = to, b[cntb].cap = cap, b[cntb].flow = 0;
    g[from] = cntb;
}
bool bfs()
{
    queue<int> q;
    q.push(s);
    memset(dis, 0, sizeof(dis));
    dis[s] = 1;
    while (!q.empty())
    {
        int dq = q.front();
        q.pop();
        for (int i = g[dq]; i; i = b[i].next)
            if (b[i].cap > b[i].flow && !dis[b[i].to])
            {
                dis[b[i].to] = dis[dq] + 1;
                q.push(b[i].to);
            }
    }
    return dis[t] > 0;
}
int dinic(int dq, int maxf)
{
    if (dq == t || !maxf)
        return maxf;
    int re = 0;
    for (int i = g[dq]; i; i = b[i].next)
        if (b[i].cap > b[i].flow && dis[dq] + 1 == dis[b[i].to])
        {
            int zl = dinic(b[i].to, min(maxf, b[i].cap - b[i].flow));
            re += zl;
            maxf -= zl;
            b[i].flow += zl;
            b[rev(i)].flow -= zl;
        }
    return re;
}
int solve()
{
    int re = 0;
    while (bfs())
        re += dinic(s, INF);
    return re;
}
void ef()
{
    int le = 0, ri = m + 1, ans;
    while (le < ri)
    {
        int mi = (le + ri) >> 1;
        for (int i = 1; i <= cntb; i++)
            b[i].flow = 0;
        for (int i = g[s]; i; i = b[i].next)
            b[i].cap = mi;
        if (solve() >= m)
            ans = mi, ri = mi;
        else
            le = mi + 1;
    }
    printf("%d\n", ans);
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1, srx, sry; i <= m; i++)
    {
        scanf("%d%d", &srx, &sry);
        adn(srx, cbh(i), 1);
        adn(cbh(i), srx, 0);
        adn(sry, cbh(i), 1);
        adn(cbh(i), sry, 0);
        adn(cbh(i), t, 1);
        adn(t, cbh(i), 0);
    }
    for (int i = 1; i <= n; i++)
        adn(s, i, 1), adn(i, s, 0);
    ef();
    return 0;
}

By 合格考求过的 Cansult