【網絡流近期整理】【最小割模型】

To-do LIST

【bzoj2055】80人環遊世界有上下界的費用流

https://blog.csdn.net/u012288458/article/details/50748608

hdu 6118 度度熊的交易計劃（最小費用可行流）

https://blog.csdn.net/wang2147483647/article/details/77160903

hdu 4411 Arrest（費用流）

https://blog.csdn.net/kksleric/article/details/8009882

Pro1

F - Plug It In Gym - 101873F

Plug It In!

Adam just moved into his new apartment and simply placed everything into it at random. This

means in particular that he did not put any effort into placing his electronics in a way that each

one can have its own electric socket.

Since the cables of his devices have limited reach, not every device can be plugged into every

socket without moving it first. As he wants to use as many electronic devices as possible right

away without moving stuff around, he now tries to figure out which device to plug into which

socket. Luckily the previous owner left behind a plugbar which turns one electric socket into 3.

Can you help Adam figure out how many devices he can power in total?

Input

The input consists of:

• one line containing three integers m, n and k, where

– m (1 ≤ m ≤ 1 500) is the number of sockets;

– n (1 ≤ n ≤ 1 500) is the number of electronic devices;

– k (0 ≤ k ≤ 75 000) is the number of possible connections from devices to sockets.

• k lines each containing two integers xi and yi

indicating that socket xi can be used to

power device yi

Sockets as well as electronic devices are numbered starting from 1.

The plugbar has no cable, i.e. if it is plugged into a socket it simply triples it.

Output

Output one line containing the total number of electrical devices Adam can power.

Sample Input 1 Sample Output 1

3 6 8

1 1

1 2

1 3

2 3

2 4

3 4

3 5

3 6

GCPC 2017 Problem F: Plug It In! 11

Sample Input 2 Sample Output 2

4 5 11

1 1

1 2

1 3

2 1

2 2

2 3

3 1

3 2

3 3

4 4

4 5

Sample Input 3 Sample Output 3

3 5 7

1 1

1 2

2 2

2 3

2 4

3 4

3 5

有m個插座，n個電器，k個連結，每個插座都隻能連接配接一個電器，現在有一個插座能夠連接配接3個電器，問最多能給多少個電器充電。

建圖，把源點到插座的邊都記錄下來，先跑一遍最大流，然後儲存一下殘餘網路，枚舉能連接配接3個電器的那個插座，然後在儲存下來的殘餘網路上跑最大流即可。

注意此題的邊和點的數組設定要極為準确，既不能過大也不能過小。

Pro2： UVALive - 3487 Duopoly(最小割)

2015年08月31日 13:58:30 閱讀數：509更多

個人分類： ACM-圖論-網絡流

題目大意：有兩個公司A和B在申請一些資源

現在給出兩個公司所申請的内容，内容包括價錢和申請的資源

現在你做為官方，你隻能拒絕一個申請或者接受一個申請，同一個資源不能兩個公司都擁有，且申請的資源不能隻給部分

問：作為官方，你能得到的最大利益是多少

解題思路：這題的沖突在于，同一個資源不能兩家公司共享，既然如此的話，那就找出沖突的申請，讓他們之間連條線就可以了，容量為INF

設立源點，源點和A公司的申請相連接配接，容量為申請的價錢

設立彙點，彙點和B公司的申請相連接配接，容量為申請的價錢

然後找出沖突的申請，連線。因為隻有沖突的申請才能連線，且隻有連線的才能把流流到彙點，是以跑出來的最大流就是我們所需要的最小割

是以答案就是所有申請的價錢總和 - 最小割

參考部落格

坑點：标記數組沒有清空一直wa。

Pro3 Catering

bzoj 4108: [Wf2015]Catering （有源彙有上下界的費用流）

4108: [Wf2015]Catering

Time Limit: 4 Sec Memory Limit: 128 MB

Submit: 165 Solved: 58

[Submit][Status][Discuss]

Description

有一家裝備出租公司收到了按照時間順序排列的n個請求.

這家公司有k個搬運工.每個搬運工可以搬着一套裝備按時間順序去滿足一些請求.一個搬運工從第i個請求的位置把東西搬到第j個請求的位置需要一些費用.公司的編号是1,請求的編号是2到n+1.所有搬運工必需從公司出發.

求滿足所有請求所需的最小搬運費用.

Input

有可能有多組資料(我也不知道).

第一行兩個正整數n,k.

接下來n行,第i行有n-i+1個數.第j個數表示把裝備從i搬到i+j的花費.

Output

輸出一行一個整數表示最小花費.

Sample Input

1 1

Sample Output

HINT

n, k <= 100;

花費 <= 1,000,000

Source

鳴謝laekov提供譯文

[Submit][Status][Discuss]

題解：有源彙有上下界的費用流

建出原圖後重建，直接跑最小費用最大流即可。注意要權重限制總的路線數。

送出位址：

https://open.kattis.com/submissions/3003606

code：

wf2015 題解 https://tieba.baidu.com/p/3778682428?red_tag=1761530858

https://blog.csdn.net/Phenix_2015/article/details/51158707

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<queue>
#include<cstring>
#define N 50000
#define inf 1000000000
using namespace std;
int ans,n,m,tot,val[N];
int point[N],v[N],Next[N],remain[N],c[N],dis[N],can[N],last[N];
void add(int x,int y,int z,int k)
{
    tot++; Next[tot]=point[x]; point[x]=tot; v[tot]=y; remain[tot]=z; c[tot]=k;
    tot++; Next[tot]=point[y]; point[y]=tot; v[tot]=x; remain[tot]=; c[tot]=-k;
    //if (z)  cout<<x<<" "<<y<<" "<<z<<" "<<k<<endl;
}
int addflow(int s,int t)
{
    int now=t; int ans=inf;
    while (now!=s) {
        //cout<<now<<" ";
        ans=min(ans,remain[last[now]]);
        now=v[last[now]^];
    }
    //cout<<now<<endl;
    now=t;
    while (now!=s) {
        remain[last[now]]-=ans;
        remain[last[now]^]+=ans;
        now=v[last[now]^];
    }
    return ans;
}
bool spfa(int s,int t)
{
    for (int i=;i<=t;i++) dis[i]=inf,can[i]=;
    dis[s]=; can[s]=;
    queue<int> p; p.push(s);
    while (!p.empty()){
        int now=p.front(); p.pop();
        for (int i=point[now];i!=-;i=Next[i])
         if (remain[i]&&dis[v[i]]>dis[now]+c[i]){
            dis[v[i]]=dis[now]+c[i];
            last[v[i]]=i;
            if (!can[v[i]]) {
                can[v[i]]=;
                p.push(v[i]);
             }
         }
        can[now]=;
    }
    if (dis[t]==inf) return false;
    int mx=addflow(s,t);
    //cout<<dis[t]<<" "<<mx<<endl;
    ans+=mx*dis[t];
    return true;
}
void solve(int s,int t)
{
    while (spfa(s,t));
}
int main()
{
//  freopen("a.in","r",stdin);
//  freopen("my.out","w",stdout);
    while (scanf("%d%d",&n,&m)!=EOF) {
        tot=-;
        memset(point,-,sizeof(point));
        int t=*(n+)+;
        for (int i=;i<=n;i++) {
         int x; scanf("%d",&x);
         add(,i+,,x);
        }
        for (int i=;i<=n;i++)
         for (int j=i+;j<=n;j++){
          int x; scanf("%d",&x);
          add(i+n+,j+,,x);
        }
        for (int i=;i<=n;i++)
         add(i+,i+n+,,),add(i+n+,t,,);
        int S=t+; int T=t+;
        add(t,,inf,); add(,,m,); //add(S,1,1,0); add(0,T,1,0);

//        這裡轉換為無源彙的網絡流是通過增加一個點0來将源點和彙點連接配接起來的
//        或者改為 add(t,1,m,0); 
        for (int i=;i<=n+;i++)
         add(S,i+n,,),add(i,T,,);
        solve(S,T);
        printf("%d\n",ans);
    }
}

Pro1 code：

#include<bits/stdc++.h>
using namespace std;
const int MAXN = ;//點數的最大值
const int MAXM = ;//邊數的最大值
const int INF = ;
struct Edge
{
    int to,next,cap,flow;

} edge[],temp[]; //注意是 MAXM
int tol;
int head[],book[],n,m,k;
void init()
{
    tol = ;
    memset(head,-,sizeof(head));
}
void addedge(int u,int v,int w,int rw = )
{
    edge[tol].to = v;
    edge[tol].cap = w;
    edge[tol].flow = ;
    edge[tol].next = head[u];
    head[u] = tol++;

    edge[tol].to = u;
    edge[tol].cap = rw;
    edge[tol].flow = ;
    edge[tol].next = head[v];
    head[v] = tol++;
}
int Q[MAXN];
int dep[MAXN],cur[MAXN],sta[MAXN];
bool bfs(int s,int t,int n)
{
    int front = ,tail = ;
    memset(dep,-,sizeof(dep[])*(n+));
    dep[s] = ;
    Q[tail++] = s;
    while(front < tail)
    {
        int u = Q[front++];
        for(int i = head[u]; i != -; i = edge[i].next)
        {
            int v = edge[i].to;
            if(edge[i].cap > edge[i].flow && dep[v] == -)
            {
                dep[v] = dep[u] + ;
                if(v == t)return true;
                Q[tail++] = v;
            }
        }
    }
    return false;
}
int dinic(int s,int t,int n)
{
    int maxflow = ;
    while(bfs(s,t,n))
    {
        for(int i = ; i < n; i++)cur[i] = head[i];
        int u = s, tail = ;
        while(cur[s] != -)
        {
            if(u == t)
            {
                int tp = INF;
                for(int i = tail-; i >= ; i--)
                    tp = min(tp,edge[sta[i]].cap-edge[sta[i]].flow);
                maxflow += tp;
                for(int i = tail-; i >= ; i--)
                {
                    edge[sta[i]].flow += tp;
                    edge[sta[i]^].flow -= tp;
                    if(edge[sta[i]].cap-edge[sta[i]].flow == )
                        tail = i;
                }

                u = edge[sta[tail]^].to;
            }
            else if(cur[u] != - && edge[cur[u]].cap > edge[cur[u]].flow && dep[u] +  == dep[edge[cur[u]].to])
            {
                sta[tail++] = cur[u];
                u = edge[cur[u]].to;
            }
            else
            {
                while(u != s && cur[u] == -)
                    u = edge[sta[--tail]^].to;
                cur[u] = edge[cur[u]].next;
            }
        }
    }
    return maxflow;
}

int main()
{

    init();
    scanf("%d%d%d",&n,&m,&k);

    for(int i=; i<=n; i++)
    {
        //add_e(0,i,1);//
        addedge(,i,);
        book[i] =tol- ;

    }
    while(k--)
    {
        int u,v;
        scanf("%d%d",&u,&v);
        addedge(u,v+n,);
    }
    for(int i=; i<=m; i++)
    {
        addedge(n+i,n+m+,);

    }

    int ans2 = dinic(,m+n+,n+m+);
    memcpy(temp,edge,sizeof temp);
    int ans = ;
    for(int i=; i<=n; i++)
    {
        memcpy(edge,temp,sizeof temp);
      //  edge[book[i]].flow+=2;
        edge[book[i]].cap+=;
        ans = max(ans,dinic(,n+m+,n+m+));
    }
    printf("%d\n",ans2+ans);
    return ;
}

Pro2 code：

#include<bits/stdc++.h>
using namespace std;
const int MAXN = ;//點數的最大值
const int MAXM = ;//邊數的最大值
const int INF = ;
struct Edge
{
    int to,next,cap,flow;

} edge[]; //注意是 MAXM
int tol;
int head[],n,m,k;
void init()
{
    tol = ;
    memset(head,-,sizeof(head));
}
void addedge(int u,int v,int w,int rw = )
{
    edge[tol].to = v;
    edge[tol].cap = w;
    edge[tol].flow = ;
    edge[tol].next = head[u];
    head[u] = tol++;

    edge[tol].to = u;
    edge[tol].cap = rw;
    edge[tol].flow = ;
    edge[tol].next = head[v];
    head[v] = tol++;
}
int Q[MAXN];
int dep[MAXN],cur[MAXN],sta[MAXN];
bool bfs(int s,int t,int n)
{
    int front = ,tail = ;
    memset(dep,-,sizeof(dep[])*(n+));
    dep[s] = ;
    Q[tail++] = s;
    while(front < tail)
    {
        int u = Q[front++];
        for(int i = head[u]; i != -; i = edge[i].next)
        {
            int v = edge[i].to;
            if(edge[i].cap > edge[i].flow && dep[v] == -)
            {
                dep[v] = dep[u] + ;
                if(v == t)return true;
                Q[tail++] = v;
            }
        }
    }
    return false;
}
int dinic(int s,int t,int n)
{
    int maxflow = ;
    while(bfs(s,t,n))
    {
        for(int i = ; i < n; i++)cur[i] = head[i];
        int u = s, tail = ;
        while(cur[s] != -)
        {
            if(u == t)
            {
                int tp = INF;
                for(int i = tail-; i >= ; i--)
                    tp = min(tp,edge[sta[i]].cap-edge[sta[i]].flow);
                maxflow += tp;
                for(int i = tail-; i >= ; i--)
                {
                    edge[sta[i]].flow += tp;
                    edge[sta[i]^].flow -= tp;
                    if(edge[sta[i]].cap-edge[sta[i]].flow == )
                        tail = i;
                }

                u = edge[sta[tail]^].to;
            }
            else if(cur[u] != - && edge[cur[u]].cap > edge[cur[u]].flow && dep[u] +  == dep[edge[cur[u]].to])
            {
                sta[tail++] = cur[u];
                u = edge[cur[u]].to;
            }
            else
            {
                while(u != s && cur[u] == -)
                    u = edge[sta[--tail]^].to;
                cur[u] = edge[cur[u]].next;
            }
        }
    }
    return maxflow;
}
int booka[],bookb[];
int price[],price2[];
int vis[][];
int main()
{

    int T;
    cin>>T;
    int y = ;
    int top =;

    while(T--)

    {
        if(top)top =;
        else printf("\n");
        y++;

        init();
        cin>>n;
        memset(vis,,sizeof vis);
        memset(booka,,sizeof booka);
        memset(bookb,,sizeof bookb);
        //memset(vis,0,sizeof vis);
        int Max = -;
        int a,b;
        int sum  =;
            string tmp;
         //

       //   getline(cin,tmp);
        for(int i=; i<=n; i++)
        {

//            getline(cin,tmp);
//            stringstream p(tmp);
            cin>>price[i];
           //   cout<<a<<" " ;
            sum+=price[i];
            char ch =;
            while(ch!='\n'&&scanf("%d%c",&b,&ch)==)
            {
                 //    cout<<b<<" " ;
                Max=  max(Max,b);
                booka[b] = i;
            }
           // cout<<endl;
        }
          //getline(cin,tmp);
          cin>>m;
        for(int i=; i<=m; i++)
        {
            //string tmp;
            //getline(cin,tmp);
            //stringstream p(tmp);
            cin>>price2[i];
            sum+=price2[i];
           // cout<<a<<" " ;
           char ch =;
            while(ch!='\n'&&scanf("%d%c",&b,&ch)==)
            {
               // cout<<b<<" " ;
                Max=  max(Max,b);
                bookb[b] = i;
            }
          //  cout<<endl;
        }
        for(int i=; i<=n; i++)
        {
            addedge(,i,price[i]);
        }
        for(int i=; i<=m; i++)
        {
            addedge(n+i,n+m+,price2[i]);
        }
        for(int i=; i<=Max; i++)
        {
            if(!booka[i]||!bookb[i]||vis[booka[i]][bookb[i]])continue;
            vis[booka[i]][bookb[i]] = ;
            addedge(booka[i],bookb[i]+n,);
        }
        int ans = dinic(,n+m+,n+m+);
        printf("Case %d:\n",y);
        cout<<sum-ans<<endl;

    }

    return ;
}

【網絡流近期整理】【最小割模型】

Pro1

繼續閱讀

POJ 2987 Firing 最小割(最大權閉合子圖)Firing

POJ 2987 Firing(最大權閉合圖)

POJ 2987 最大權閉合子圖

poj 2987 Firing (最大流、最大權閉合圖)

POJ 2987 Firing (最大權閉合圖，最小割)

POJ2987_Firing_最大權閉合圖

poj 2516 Minimum Cost

Poj 1511- Invitation Cards(Spfa+鄰接表)

日記（周六&&差分限制）

#1394 : 網絡流四·最小路徑覆寫

bzoj 3681: Arietta

Android 亂碼

POJ - 3436 ACM Computer Factory(最大流，拆點)

HDU5294 Tricks Device（最大流+SPFA） 2015 Multi-University Training Contest 1Tricks Device

POJ 3680

uva Monkeys in the Emei Mountain(區間模型)