先丢板子。。

Dinic

const int maxn = 1010;const int maxm = 100100;const int inf = 0x3f3f3f3f;int head[maxn], cnt, dis[maxn];struct edge{    int to, next, cap;} E[maxm];void init(){    memset(head, -1, sizeof head);    cnt = 0;}void add(int u, int v, int c){    E[cnt].to = v;    E[cnt].cap = c;    E[cnt].next = head[u];    head[u] = cnt++;    E[cnt].to = u;    E[cnt].cap = 0;    E[cnt].next = head[v];    head[v] = cnt++;}int bfs(int s, int t){    memset(dis, 0, sizeof dis);    dis[s] = 1;    queue
     
       que;    que.push(s);    while (!que.empty())    {        int u = que.front();        que.pop();        for (int i = head[u]; ~i; i = E[i].next)        {            int v = E[i].to;            if (!dis[v] && E[i].cap)            {                dis[v] = dis[u] + 1;                if (v == t) return 1;                que.push(v);            }        }    }    return 0;}int dfs(int u, int a, int t){    if (u == t) return a;    int ret = 0;    for (int i = head[u]; ~i; i = E[i].next)    {        if (!a) break;        int v = E[i].to;        if (dis[v] == dis[u] + 1 && E[i].cap)        {            int f = dfs(v, min(a, E[i].cap), t);            if (f > 0)            {                E[i].cap -= f;                E[i ^ 1].cap += f;                a -= f;                ret += f;            }            else            {                dis[v] = -1;            }        }    }    return ret;}int maxflow(int s, int t){    int ret = 0;    while (bfs(s, t))    {        ret += dfs(s, inf, t);    }    return ret;}
     

 

ISAP

const int maxn = 1010;const int maxm = 100100;const int inf = 0x3f3f3f3f;int head[maxn], cnt, dis[maxn], pre[maxn], cur[maxn], num[maxn];struct edge{    int from, to, next, cap;} E[maxm];void init(){    memset(head, -1, sizeof head);    cnt = 0;}void add(int u, int v, int c){    E[cnt].to = v;    E[cnt].from = u;    E[cnt].next = head[u];    E[cnt].cap = c;    head[u] = cnt++;    E[cnt].to = u;    E[cnt].from = v;    E[cnt].next = head[v];    E[cnt].cap = 0;    head[v] = cnt++;}void bfs(int s, int t){    memset(dis, inf, sizeof dis);    dis[t] = 0;    queue
     
       que;    que.push(t);    while (!que.empty())    {        int u = que.front();        que.pop();        for (int i = head[u]; ~i; i = E[i].next)        {            int v = E[i].to;            if (dis[v] == inf && E[i].cap == 0)            {                dis[v] = dis[u] + 1;                que.push(v);            }        }    }}int augment(int s, int t){    int ret = inf;    pre[s] = -1;    for (int i = pre[t]; ~i; i = pre[E[i].from])        ret = min(ret, E[i].cap);    for (int i = pre[t]; ~i; i = pre[E[i].from])    {        E[i].cap -= ret;        E[i ^ 1].cap += ret;    }    return ret;}int maxflow(int s, int t, int n){    bfs(s, t);    memcpy(cur, head, sizeof head);    memset(num, 0, sizeof num);    for (int i = 1; i <= n; i++) if (dis[i] != inf) num[dis[i]]++;    int ret = 0, x = s;    while (dis[s] < n)    {        if (x == t)        {            ret += augment(s, t);            x = s;        }        int ok = 0;        for (int &i = cur[x]; ~i; i = E[i].next)        {            int v = E[i].to;            if (dis[v] == dis[x] - 1 && E[i].cap)            {                pre[v] = i;                x = v;                ok = 1;                break;            }        }        if (!ok)        {            int mmin = n - 1;            for (int i = head[x]; i != -1; i = E[i].next)                if (E[i].cap)                    mmin = min(mmin, dis[E[i].to]);            if (--num[dis[x]] == 0) break;            num[dis[x] = mmin + 1]++;            cur[x] = head[x];            if (x != s) x = E[pre[x]].from;        }    }    return ret;}
     

MCMF（最大流最小费用

int head[maxm], cnt;struct edge{    int from, to, next, cap, flow, fee;} E[maxn];void init(){    memset(head, -1, sizeof head);    cnt = 0;}void add(int u, int v, int c, int f){    E[cnt].from = u;    E[cnt].to = v;    E[cnt].next = head[u];    E[cnt].flow = 0;    E[cnt].cap = c;    E[cnt].fee = f;    head[u] = cnt++;    E[cnt].from = v;    E[cnt].to = u;    E[cnt].next = head[v];    E[cnt].flow = 0;    E[cnt].cap = 0;    E[cnt].fee = -f;    head[v] = cnt++;}int dis[maxm], inq[maxm], pre[maxm], minflow[maxm];bool spfa(int s, int t, int &flow, int &fee){    memset(inq, 0, sizeof inq);    memset(dis, inf, sizeof dis);    queue
     
       que;    que.push(s);    dis[s] = 0;    inq[s] = 1;    pre[s] = -1;    minflow[s] = inf;    while (!que.empty())    {        int u = que.front();        que.pop();        inq[u] = 0;        for (int i = head[u]; i != -1; i = E[i].next)        {            int v = E[i].to;            if (E[i].cap > E[i].flow && dis[v] > dis[u] + E[i].fee)            {                dis[v] = dis[u] + E[i].fee;                pre[v] = i;                minflow[v] = min(minflow[u], E[i].cap - E[i].flow);                if (!inq[v])                {                    inq[v] = 1;                    que.push(v);                }            }        }    }    if (dis[t] == inf) return false;    for (int i = pre[t]; i != -1; i = pre[E[i].from])    {        E[i].flow += minflow[t];        E[i ^ 1].flow -= minflow[t];    }    flow += minflow[t];    fee += minflow[t] * dis[t];    return true;}void mcmf(int s, int t, int &flow, int &fee){    flow = fee = 0;    while (spfa(s, t, flow, fee));}
     

常用方法：

最大流=最小割

超级源、超级汇：在要控制整个网络的流量时

拆点：一个点只能经过一次时 可以将这个点拆成两个之间容量为1的点

然后数组大小要注意，要开两倍的

 

eg

拆点：POJ 3281

每个奶牛都有喜欢的饮料和食物，最多可以让多少的奶牛得到满足

 

把每个奶牛拆成两个点 左边连食物，右边连饮料，两个点之间连容量为1的边，表示只能经过1

然后跑最大流

int main(){    int N, F, D;    scanf("%d %d %d", &N, &F, &D);    init();    for(int i = 1; i <= N; i++) add(100+i, 200+i, 1);    for(int i = 1; i <= F; i++) add(0, i, 1);    for(int i = 1; i <= D; i++) add(300+i, 500, 1);    for(int i = 1; i <= N; i++)    {        int ff, dd;        scanf("%d %d", &ff, &dd);        for(int j = 1; j <= ff; j++)        {            int x;            scanf("%d", &x);            add(x, 100+i, 1);        }        for(int j = 1; j <= dd; j++)        {            int x;            scanf("%d", &x);            add(200+i, 300+x, 1);        }    }    printf("%d\n", maxflow(0, 500));    return 0;}

 

拆边：HDU 3667

要从1向N运送K的货物，一条从u向v的路最多运c的货物，运x货物要花ai*x^2的费用，求运送K的货物的最小费用

在一条路上运1要花a，运2要花4a，运3要花9a

因此可以拆成费用为a, 3a, 5a的边 

如果选两条的话肯定选a+3a就是4a惹~

然后跑最大流最小费用就可以啦

-1的情况就是流过的流量不等于K

int main(){    int m, k;    while(~scanf("%d %d %d", &n, &m, &k))    {        init();        for(int i = 0; i < m; i++)        {            int u, v, a, c;            scanf("%d %d %d %d", &u, &v, &a, &c);            for(int j = 1; j <= c; j++)                add(u, v, 1, a * (2 * j - 1));        }        int flow, fee;        add(0, 1, k, 0);        mcmf(0, n, flow, fee);        if(flow != k) printf("-1\n");        else printf("%d\n", fee);    }    return 0;}

 

BZOJ 1834

给定一张有向图，每条边都有一个容量C和一个扩容费用W。这里扩容费用是指将容量扩大1所需的费用。

求： 

1、在不扩容的情况下，1到N的最大流； 

2、将1到N的最大流增加K所需的最小扩容费用。

 

第1问就是跑最大流

第2问在第一问的基础上，添加容量为inf的边，（这时原来的边费用为0），超级源点控制流量，然后跑最小费用

int main(){    int n, m, k;    scanf("%d %d %d", &n, &m, &k);    init();    for(int i = 0; i < m; i++)    {        scanf("%d %d %d %d", &U[i], &V[i], &C, &W[i]);        add(U[i], V[i], C, 0);    }    printf("%d ", maxflow(1, n, n));    for(int i = 0; i < m; i++) add(U[i], V[i], inf, W[i]);    add(0, 1, k, 0);    int flow, fee;    mcmf(0, n, flow, fee);    printf("%d\n", fee);    return 0;}

 

二分 POJ 2391

n个田野里用不同数量的牛，每个田野能容纳一定数量的牛，田野之间有无向边，走过每条边需要一定时间

所有牛一起移动，问把所有牛都安置到田野中最少要多长时间，如果不能安置则输出-1

着实心情复杂的一道题

先用floyd求出每两个点之间到达的最短时间

二分时间，每次把这段时间里能到达的边选上来建图

1.注意要开longlong

2.用没优化的ISAP会TLE 改成Dinic过。。

3.拆点时1~n, n+1~2n, 2n+1（超级源）, 2n+2（超级汇）

4.注意再建边时容量是inf而不是floyd求出的dist，dist只是判断这条边能不能走

5.数组大小。。嘤嘤嘤

int main(){    LL n, P, sumn = 0;    scanf("%lld %lld", &n, &P);    for(LL i = 1; i <= n; i++)    {        scanf("%lld %lld", &now[i], &hold[i]);        sumn += now[i];    }    memset(dist, 0x3f, sizeof(dist));    for(LL i = 1; i <= n; i++) dist[i][i] = 0;    for(LL i = 0; i < P; i++)    {        LL x, y;        LL w;        scanf("%lld %lld %lld", &x, &y, &w);        dist[x][y] = dist[y][x] = min(w, dist[x][y]);    }    for(LL k = 1; k <= n; k++)        for(LL i = 1; i <= n; i++)            for(LL j = 1; j <= n; j++)                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);    LL l = 0, r = 200000000010LL, mid;    while(l < r)    {        mid = (l + r) >> 1;        init();        for(LL i = 1; i <= n; i++)        {            add(2*n+1, i, now[i]);            add(i+n, 2*n+2, hold[i]);        }        for(LL i = 1; i <= n; i++)            for(LL j = 1; j <= n; j++)                if(dist[i][j] <= mid) add(i, j+n, maxn);        LL ans = maxflow(2*n+1, 2*n+2);        if(ans < sumn) l = mid + 1;        else r = mid;    }    if(r == 200000000010LL) printf("-1\n");    else printf("%lld\n", r);    return 0;}

 

 

HDU 6214

求最小割最少有多少条边

先保证是最小割，再保证最少边，这种双关键字的比较通常有一种比较常用的套路，就是给第一关键字乘一个大系数再加上第二个关键字，以此为key。

对于这个题，可以让每条边的原始流量乘以一个大常数（例如1e6）再+1作为新的流量，跑一遍最大流后再对那个大常数取模即为答案。

get了。。神奇

int main(){    int T;    scanf("%d", &T);    while(T--)    {        int n, m, s, t;        scanf("%d %d %d %d", &n, &m, &s, &t);        init();        for(int i = 0; i < m; i++)        {            int u, v, w;            scanf("%d %d %d", &u, &v, &w);            add(u, v, w*10000+1);        }        int res = maxflow(s, t, n);        printf("%d\n", res % 10000);    }    return 0;}