最大流，二分

题意：

图片说明

分析：

这一题，我刚拿到手是蒙B的。我的第一反应也是最小费用最大流，但是想了一会也是不知道该如何表示X^2这个万恶的东西。
迫不得已，展开别的思路：

我们这样建图：
源点S与1~n相连，取cap = 1 无cost
1~n与n+1 ~ n+m 按照数据相连 cap = 1,无cost
n+1 ~ n+m 与t 相连，无cost, cap待定

观察函数 X^2 导数2X x越大他增的越厉害。这是常识

那么，在我们建的图中，最终在n+1~n+m向t汇聚时，我们要尽量避免某一条路径的x特别的大。
因为总值我们是知道的为n
那么最好他们都是相等的，为 n/m 这样最小！！

即便无法相等，我们也要尽量使得n能够均摊到每一条路径上。

这时我想到了二分法。
我们在 n+1 ~ n+m 与t相连边的cap上二分。
如果当前的cap能够使得最大流为n。
那么我就减小cap，遏制特别突出的，使他们均摊。
如果当前cap不能够使得最大流为n <n
那么我就增加cao，稍微放宽一点。

这样我们得到了边缘状态：res
即cap为res时最大流为n，cap为res-1时最大流<n

似乎，res就是正解。
我们在遍历每一个n+1 ~ n+m的边，看当前边通过的流量(其反边的cap)然后平方和相加就行了.

但是，这其实是有疏漏的。
我们注意到当res-1时，所有的流通路径都是绷紧的，大家都尽己所能地传送。
这时候毫无疑问时完美均摊的。
但是最大流没达标，所以我们cap+1变为res.
但是这样做之后，我们就无法保证后面的这些路径那些是绷紧的那些是松弛的。
比如：
n=11
res-1 = 3
第一条路经流量：2
第二条路径流量：2
第三条路径流量：3
第四条路径流量：3

放宽变为res=4
第一条路经流量：1
第二条路径流量：2
第三条路径流量：4
第四条路径流量：4

我们发现第一条路经竟然减1了，而这减的1加到了第四条路径上了。
我们很明显就知道这样是不划算的，
正确的应该是：
第一条路经流量：2
第二条路径流量：2
第三条路径流量：4
第四条路径流量：3
如此才对。

那么我们如何操作呢。
很简单，我们不去计算res的情况，我们去计算res-1时的情况。
看当前最大流与n相差多少，假设为cnt
那么我们在遍历n+1~n+m与 t 的边时，如果发现其流量为res-1且cnt>0
那么我们就把这条边的流量加一再平方相加，然后cnt-=1

此为正解！！

代码如下：

#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
const int inf = 2e9;
const int max_n = 55;
const int max_m = 55*55;
int n, m;

struct edge
{
    int to, cap, rev, next;
}E[max_m * 2];
int head[max_n * 2];
int cnt = 1;
void add(int from, int to, int cap) {
    E[cnt].to = to;
    E[cnt].cap = cap;
    E[cnt].rev = cnt + 1;
    E[cnt].next = head[from];
    head[from] = cnt++;
    E[cnt].to = from;
    E[cnt].cap = 0;
    E[cnt].rev = cnt - 1;
    E[cnt].next = head[to];
    head[to] = cnt++;
}
void init() {
    fill(head, head + max_n * 2, false);
    cnt = 1;
}

int iter[max_n * 2];
int dist[max_n * 2];
bool searchpath(int s, int t) {
    fill(dist, dist + max_n * 2, -1);
    queue<int> que;dist[s] = 0;
    que.push(s);
    while (!que.empty()) {
        int u = que.front();que.pop();
        for (int i = head[u];i;i = E[i].next) {
            edge& e = E[i];
            if (dist[e.to] != -1 || e.cap == 0)continue;
            dist[e.to] = dist[u] + 1;
            que.push(e.to);
        }
    }return dist[t] != -1;
}

int matchpath(int u, int t, int f) {
    if (u == t)return f;
    for (int& i = iter[u];i;i = E[i].next) {
        edge& e = E[i];
        if (dist[e.to] <= dist[u] || e.cap <= 0)continue;
        int d = matchpath(e.to, t, min(e.cap, f));
        if (d > 0) {
            e.cap -= d;
            E[e.rev].cap += d;
            return d;
        }
    }return false;
}

int dinic(int s, int t) {
    int flow = 0;int f;
    while (searchpath(s, t)) {
        for (int i = 1;i < max_n * 2;i++)iter[i] = head[i];
        while (f = matchpath(s, t, inf))
            flow += f;
    }return flow;
}

int a[max_n], b[max_n];

int check(int mid,int type = 0) {
    init();
    int start = n + m + 1;
    int ed = start + 1;
    for (int i = 1;i <= n;i++) {
        add(start, i, 1);
        add(i, a[i] + n, 1);
        add(i, b[i] + n, 1);
    }for (int i = 1;i <= m;i++)
        add(i + n, ed, mid);
    return n - dinic(start, ed);
}
int ef(int tot) {
    int left = 1;int right = tot;
    while (left < right) {
        int mid = (left + right) >> 1;
        if (check(mid) == 0)right = mid;
        else left = mid + 1;
    }
    int acnt = check(right - 1);
    int res = 0;
    for (int i = 1;i <= m;i++) {
        if (!head[i + n])continue;
        edge& e = E[head[i + n]];
        if (E[e.rev].cap == right - 1 && acnt) {
            res += 2 * E[e.rev].cap + 1;
            acnt--;
        }
        res += E[e.rev].cap * E[e.rev].cap;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(0);
    cin >> n >> m;
    for (int i = 1;i <= n;i++)cin >> a[i] >> b[i];
    cout << ef(n) << endl;
}

Birthday

最大流，二分

题意：

分析：

代码如下：