• 网络流总结 五万字符详解（56226字符）

    前言

    网络流在解题思想与特性中，十分类似于动态规划，二者模板少，网络流难在构造图，动态规划难在构造转移方程，一旦构造正确，一切便迎刃而解

    最大流模板

    【模板】网络最大流 - 洛谷

    1. #include
    2. using namespace std;
    3.  
    4. typedef long long int ll;
    5. typedef struct
    6. {
    7.     int b,e;
    8.     ll val;
    9. } xinxi;
    10. xinxi s[101010];
    11. int f[101010],nex[101010],len=2,n,m,dep[101010],st,ed;
    12. void add(int x,int y,ll z)
    13. {
    14.     s[len].b=x;
    15.     s[len].e=y;
    16.     s[len].val=z;
    17.     nex[len]=f[x];
    18.     f[x]=len;
    19.     len++;
    20.  
    21.  
    22. }
    23.  
    24. queue<int>Q;
    25. bool bfs()
    26. {
    27.     memset(dep,0,sizeof(dep));
    28.     Q.push(st);
    29.     dep[st]=1;
    30.     while(!Q.empty())
    31.     {
    32.         int u=Q.front();
    33.         Q.pop();
    34.  
    35.         for(int i=f[u]; i!=-1; i=nex[i])
    36.         {
    37.             int v=s[i].e;
    38.             if(dep[v]==0&&s[i].val)
    39.             {
    40.                 dep[v]=dep[u]+1;
    41.                 Q.push(v);
    42.             }
    43.         }
    44.     }
    45.     return dep[ed];
    46. }
    47. ll dfs(int now,ll flow)
    48. {
    49.     if(now==ed)
    50.         return flow;
    51.     ll out=0;
    52.     int x=f[now];
    53.     while(x!=-1)
    54.     {
    55.         int j=s[x].e;
    56.  
    57.         if(dep[j]==dep[now]+1&&s[x].val)
    58.         {
    59.             ll temp=dfs(j,min(flow,s[x].val));
    60.             s[x].val-=temp;
    61.             s[x^1].val+=temp;
    62.             flow-=temp;
    63.             out+=temp;
    64.         }
    65.         
    66.         if(!flow)
    67.             break;
    68.         x=nex[x];
    69.  
    70.     }
    71.     if(!out)
    72.         dep[now] = 0;
    73.     return out;
    74.  
    75.  
    76. }
    77. int main()
    78. {
    79.  
    80.  
    81.     memset(f,-1,sizeof(f));
    82.  
    83.     cin>>n>>m>>st>>ed;
    84.  
    85.     for(int i=1; i<=m; i++)
    86.     {
    87.         int x,y;
    88.         ll z;
    89.         cin>>x>>y>>z;
    90.         add(x,y,z);
    91.         add(y,x,0);
    92.     }
    93.  
    94.  
    95.     ll ans=0;
    96.     while(bfs())
    97.     {
    98.         ans+=dfs(st,1e18);
    99.     }
    100.  
    101.     cout<
    102.  
    103.  
    104.     return 0;
    105. }

    费用流模板

    【模板】最小费用最大流 - 洛谷

    1. # include
    2. # include
    3. # include
    4. using namespace std;
    5. int n,m,st,ed,len=2;
    6. typedef long long int  ll;
    7. typedef struct
    8. {
    9.     int b,e;
    10.     ll flow,dis;
    11. } xinxi;
    12. xinxi s[101010];
    13. int f[101010],nex[101010]， pre[101010],vis[101010];
    14. ll dis[101010],minn[101010]，mincost, maxflow;
    15. queue<int>q;
    16. void add(int x,int y,ll flow,ll dis)
    17. {
    18.     s[len].b=x;
    19.     s[len].e=y;
    20.     s[len].flow=flow;
    21.     s[len].dis=dis;
    22.  
    23.     nex[len]=f[x];
    24.     f[x]=len;
    25.     len++;
    26. }
    27. ll inf=1e18;
    28. bool SPFA()
    29. {
    30.     for(int i=1; i<=n; i++)
    31.     {
    32.         vis[i]=0;
    33.         dis[i]=inf;
    34.     }
    35.     q.push(st);
    36.     minn[st]=inf;
    37.     dis[st]=0;
    38.     vis[st]=1;
    39.  
    40.     while(!q.empty())
    41.     {
    42.         int now=q.front();
    43.         q.pop();
    44.         vis[now]=0;
    45.         int x=f[now];
    46.         while(x!=-1)
    47.         {
    48.             int j=s[x].e;
    49.             if(s[x].flow==0)
    50.             {
    51.                 x=nex[x];
    52.                 continue;
    53.             }
    54.             if(dis[j]>dis[now]+s[x].dis)
    55.             {
    56.                 dis[j]=dis[now]+s[x].dis;
    57.                 minn[j]=min(minn[now],s[x].flow);
    58.  
    59.                 pre[j]=x;
    60.  
    61.                 if(!vis[j])
    62.                 {
    63.                     vis[j]=1;
    64.                     q.push(j);
    65.                 }
    66.             }
    67.             x=nex[x];
    68.         }
    69.     }
    70.  
    71.     return (dis[ed]!=inf);
    72.  
    73. }
    74.  
    75. void work()
    76. {
    77.     while(SPFA())
    78.     {
    79.         int x=ed;
    80.  
    81.         maxflow+=minn[ed];
    82.         mincost+=minn[ed]*dis[ed];
    83.         int i;
    84.         while(x!=st)
    85.         {
    86.             i=pre[x];
    87.             s[i].flow-=minn[ed];
    88.             s[i^1].flow+=minn[ed];
    89.             x=s[i^1].e;
    90.         }
    91.     }
    92. }
    93. int main ()
    94. {
    95.     memset(f,-1,sizeof(f));
    96.     cin>>n>>m>>st>>ed;
    97.  
    98.     for(int i=1; i<=m; i++)
    99.     {
    100.         int x,y;
    101.         ll flow,diss;
    102.         cin>>x>>y>>flow>>diss;
    103.  
    104.         add(x,y,flow,diss);
    105.         add(y,x,0,-diss);
    106.     }
    107.  
    108.     work();
    109.  
    110.     cout<" "<
    111.     return 0;
    112.  
    113. }
    114.

    最大流

    经典样例 最大流模型题 

    1459 -- Power Network

    题目英文解释非常繁琐，大致意思是 给m个点 ,np个发电站 ，nc个用户，n条边

    np个发电站 给出每个发电站提供的最大流量

    nc个用户，表示每个用户能接受的最大流量

    n个边给出了发电站与用户之间的连接关系，以及最多能够输送的电量

    求出某种方式连边下，用户获得的流量最大值

    建图方式

    一 超级源点向发电站连接发电站发电量的边

    二 发电站向用户连接能够输送的电量

    三 用户向汇点连接用户能够最多接受的上限

    1. #include
    2. # include
    3. # include
    4. using namespace std;
    5.  
    6. typedef long long int ll;
    7.  
    8. int n,n1,n2,m;
    9.  
    10. typedef struct
    11. {
    12.    int b,e,flow;
    13. }xinxi;
    14.  
    15. xinxi s[101010];
    16. int f[101010],nex[101010],len=2;
    17.  
    18. void add(int x,int y,int z)
    19. {
    20.     s[len].b=x;
    21.     s[len].e=y;
    22.     s[len].flow=z;
    23.  
    24.     nex[len]=f[x];
    25.     f[x]=len;
    26.     len++;
    27. }
    28. int id1[101010],flow1[101010],id2[101010],flow2[101010];
    29.  
    30.  
    31. int dep[101010];
    32. queue<int>q;
    33.  
    34. bool bfs()
    35. {
    36.     memset(dep,0,sizeof(dep));
    37.  
    38.     while(!q.empty())
    39.         q.pop();
    40.  
    41.     dep[0]=1;
    42.     q.push(0);
    43.  
    44.     while(!q.empty())
    45.     {
    46.  
    47.         int now=q.front();
    48.  
    49.  
    50.         q.pop();
    51.  
    52.         int x=f[now];
    53.  
    54.         while(x!=-1)
    55.         {
    56.             int j=s[x].e;
    57.  
    58.             if(s[x].flow&&!dep[j])
    59.             {
    60.                 dep[j]=dep[now]+1;
    61.  
    62.                 q.push(j);
    63.             }
    64.             x=nex[x];
    65.         }
    66.     }
    67.  
    68.     return dep[n+1];
    69. }
    70.  
    71. ll dfs(int now,ll flow)
    72. {
    73.     if(now==n+1)
    74.         return flow;
    75.  
    76.     ll out=0;
    77.  
    78.     int x=f[now];
    79.     while(x!=-1)
    80.     {
    81.         int j=s[x].e;
    82.  
    83.         if(s[x].flow&&dep[j]==dep[now]+1)
    84.         {
    85.             ll res=dfs(j,min((ll)s[x].flow,flow));
    86.  
    87.             s[x].flow-=res;
    88.             s[x^1].flow+=res;
    89.             flow-=res;
    90.             out+=res;
    91.  
    92.         }
    93.         if(flow==0)
    94.             break;
    95.  
    96.         x=nex[x];
    97.     }
    98.  
    99.     if(out==0)
    100.         dep[now]=0;
    101.  
    102.     return out;
    103.  
    104. }
    105. int main()
    106. {
    107.  
    108.  
    109.   while(scanf("%d%d%d%d",&n,&n1,&n2,&m)!=EOF)
    110.   {
    111.  
    112.       int x,y,z;
    113.       memset(f,-1,sizeof(f));
    114.       memset(nex,0,sizeof(nex));
    115.  
    116.       len=2;
    117.  
    118.       for(int i=1;i<=m;i++)
    119.       {
    120.           scanf(" (%d,%d)%d",&x,&y,&z);
    121.           x++;
    122.           y++;
    123.           add(x,y,z);
    124.           add(y,x,0);
    125.       }
    126.  
    127.       for(int i=1;i<=n1;i++)
    128.       {
    129.           scanf(" (%d)%d",&x,&y);
    130.           x++;
    131.           id1[i]=x;
    132.           flow1[i]=y;
    133.       }
    134.  
    135.       for(int i=1;i<=n2;i++)
    136.       {
    137.           scanf(" (%d)%d",&x,&y);
    138.           x++;
    139.           id2[i]=x;
    140.           flow2[i]=y;
    141.       }
    142.  
    143.       for(int i=1;i<=n1;i++)
    144.       {
    145.           add(0,id1[i],flow1[i]);
    146.           add(id1[i],0,0);
    147.       }
    148.  
    149.       for(int i=1;i<=n2;i++)
    150.       {
    151.           add(id2[i],n+1,flow2[i]);
    152.           add(n+1,id2[i],0);
    153.       }
    154.  
    155.       int ans=0;
    156.       while(bfs())
    157.       {
    158.           ans+=dfs(0,1e9);
    159.  
    160.       }
    161.  
    162.       cout<
    163.   }
    164.  
    165.     return 0;
    166. }

    最大流拆点与路径输出 例题二

    最小路径覆盖问题 - 洛谷

    最小路径覆盖就是用最少的路径数覆盖住全部点，一个点只能被一个路径覆盖一次，无法重复覆盖

    是最大流的经典模型，结论为 

    最小路径覆盖数 =总点数-最大流

    建图方式

    一，每个点进行拆点操作，主点与超级源点相连，副点与超级汇点相连

    二，存在一条有向边u-v时，u的主点，连接v的副点

    三，每条边的流量都是1，每个点只能经过一次对应S到每个点的流量只有1，也就强制了每个点只能最多连接对面一个，同理，对面一个点也只能最多接受1个

    流量意义

    不难发现，一旦我们的超级汇点接受到1的流量，必定是新连接了两个点，左集点可能有指向它的点，但左集点一定没有指向的点，右集点对应的主点可能有指出的点，但该点一定没有指向它的点，即左集点代表了一个路径的结尾，右集点代表了一个路径的开头，一旦连接（流量+1），那么路径数必定减1，这样，初始时为n个路径，最终答案为 n-flow

    残留网络对答案输出的意义

    此类题目，残留网络中流量为0的边是我们重点关注的，一旦残流网络中有流量为0的边，也就意味着该边被流过一次，左集点指向了右集点，根据这一结论，设置前驱后继即可

    1. #include
    2. using namespace std;
    3.  
    4. typedef long long int ll;
    5.  
    6. int n,m,st,ed,dep[101010],f[101010],nex[101010],len=2, pre[101010],last[101010];
    7. queue<int>q;
    8. typedef struct
    9. {
    10.     int b,e;
    11.     ll flow;
    12.     ll init;
    13.  
    14. } xinxi;
    15. xinxi s[101010];
    16.  
    17. void add(int x,int y,ll flow)
    18. {
    19.     s[len].b=x;
    20.     s[len].e=y;
    21.     s[len].flow=flow;
    22.     nex[len]=f[x];
    23.     f[x]=len;
    24.     len++;
    25. }
    26. bool BFS()
    27. {
    28.     for(int i=0; i<=2*n+1; i++)
    29.     {
    30.         dep[i]=0;
    31.     }
    32.  
    33.     while(!q.empty())
    34.         q.pop();
    35.     dep[st]=1;
    36.  
    37.     q.push(st);
    38.  
    39.     while(!q.empty())
    40.     {
    41.         int now=q.front();
    42.  
    43.         q.pop();
    44.  
    45.         int x=f[now];
    46.  
    47.         while(x!=-1)
    48.         {
    49.             int j=s[x].e;
    50.  
    51.             if(s[x].flow&&dep[j]==0)
    52.             {
    53.                 dep[j]=dep[now]+1;
    54.  
    55.                 q.push(j);
    56.             }
    57.  
    58.             x=nex[x];
    59.         }
    60.     }
    61.  
    62.     return dep[ed];
    63. }
    64.  
    65. ll dfs(int now, ll flow)
    66. {
    67.     if(now==ed)
    68.         return flow;
    69.  
    70.     ll out=0;
    71.  
    72.     int x=f[now];
    73.  
    74.     while(x!=-1)
    75.     {
    76.         int j=s[x].e;
    77.  
    78.         if(s[x].flow&&dep[j]==dep[now]+1)
    79.         {
    80.             ll res=dfs(j,min(s[x].flow,flow));
    81.  
    82.             s[x].flow-=res;
    83.  
    84.             s[x^1].flow+=res;
    85.  
    86.             flow-=res;
    87.  
    88.             out+=res;
    89.         }
    90.         if(!flow)
    91.             break;
    92.  
    93.         x=nex[x];
    94.     }
    95.  
    96.     if(!out)
    97.         dep[now]=0;
    98.     return out;
    99.  
    100. }
    101.  
    102. int main()
    103. {
    104.  
    105.  
    106.     memset(f,-1,sizeof(f));
    107.  
    108.     cin>>n>>m;
    109.  
    110.     st=0;
    111.     ed=2*n+1;
    112.  
    113.     for(int i=1; i<=m; i++)
    114.     {
    115.         int x,y;
    116.         cin>>x>>y;
    117.  
    118.         add(x,y+n,1);
    119.  
    120.         add(y+n,x,0);
    121.  
    122.     }
    123.  
    124.     for(int i=1; i<=n; i++)
    125.     {
    126.         add(0,i,1);
    127.  
    128.         add(i,0,0);
    129.     }
    130.  
    131.     for(int i=n+1; i<=n*2; i++)
    132.     {
    133.         add(i,ed,1);
    134.         add(ed,i,0);
    135.     }
    136.  
    137.     ll ans=0;
    138.     while(BFS())
    139.     {
    140.         ans+=dfs(st,1e18);
    141.     }
    142.  
    143.  
    144.  
    145.     for(int i=2; i
    146.     {
    147.         if(s[i].b>=1&&s[i].b<=n&&s[i].e>=n+1&&s[i].e<=2*n&&s[i].flow==0)
    148.         {
    149.             pre[s[i].e-n]=s[i].b;
    150.             last[s[i].b]=s[i].e-n;
    151.  
    152.         }
    153.     }
    154.  
    155.     for(int i=1; i<=n; i++)
    156.     {
    157.         if(!pre[i])
    158.         {
    159.             int now=i;
    160.  
    161.             while(now)
    162.             {
    163.                 cout<" ";
    164.  
    165.                 now=last[now];
    166.             }
    167.  
    168.             cout<
    169.         }
    170.     }
    171.  
    172.     cout<
    173.     return 0;
    174. }

     最大流拆点与路径输出 例题三

      ​​​​​​魔术球问题 - 洛谷

    建图要点

    一，球拆点，具有和为平方数的点进行左右集的有向边连接

    二，动态加点，每次循环新加入一个球，并且补全超级源点超级汇点与该点的联系，补全之前左集点与该点的联系

    三，仍旧是残量网络的前驱后继路径输出

    流量与柱子数关系

    这是前两个球放入的情况，可以看出，流量在两次操作之后一直是0，代表我们不得不开辟两个柱子来存储小球

     当我们加入球3时，意外发现流量+1，这就意味着，我们原来的球1向球3连接了一条边并且成功流过去，也就是球3没有占据新的柱子，而是压在了球1

    同理，在加入球4的时候没有流量获得，故新加柱子3，在放入球5的时候，获得流量加1

    1. #include
    2. using namespace std;
    3. typedef long long int ll;
    4. int n,m,st,ed,f[101010],nex[101010],len=2,dep[10100],book[1000000+10],pre[101010],last[101010];
    5. ll ans;
    6. typedef struct
    7. {
    8.     int b,e;
    9.     ll val;
    10. } xinxi;
    11.  
    12. xinxi s[101010];
    13.  
    14. void add(int x,int y,ll z)
    15. {
    16.     s[len].b=x;
    17.     s[len].e=y;
    18.     s[len].val=z;
    19.  
    20.     nex[len]=f[x];
    21.     f[x]=len;
    22.     len++;
    23. }
    24. queue<int>q;
    25.  
    26. bool bfs()
    27. {
    28.  
    29.     memset(dep,0,sizeof(dep));
    30.  
    31.     while(!q.empty())
    32.         q.pop();
    33.  
    34.     dep[st]=1;
    35.     q.push(st);
    36.  
    37.     while(!q.empty())
    38.     {
    39.         int now=q.front();
    40.  
    41.         q.pop();
    42.  
    43.         int x=f[now];
    44.  
    45.         while(x!=-1)
    46.         {
    47.             int j=s[x].e;
    48.  
    49.             if(s[x].val&&!dep[j])
    50.             {
    51.                 dep[j]=dep[now]+1;
    52.                 q.push(j);
    53.             }
    54.  
    55.             x=nex[x];
    56.         }
    57.     }
    58.  
    59.     return dep[ed];
    60. }
    61.  
    62. ll dfs(int now, ll flow)
    63. {
    64.     if(now==ed)
    65.         return flow;
    66.  
    67.     ll out=0;
    68.  
    69.     int x=f[now];
    70.  
    71.     while(x!=-1)
    72.     {
    73.         int j=s[x].e;
    74.  
    75.         if(s[x].val&&dep[j]==dep[now]+1)
    76.         {
    77.             ll res=dfs(j,min(s[x].val,flow));
    78.  
    79.             s[x].val-=res;
    80.             s[x^1].val+=res;
    81.  
    82.             flow-=res;
    83.             out+=res;
    84.         }
    85.         if(!flow)
    86.             break;
    87.         x=nex[x];
    88.     }
    89.  
    90.     if(out==0)
    91.         dep[now]=0;
    92.  
    93.     return out;
    94.  
    95.  
    96. }
    97.  
    98. int main()
    99. {
    100.  
    101.     memset(f,-1,sizeof(f));
    102.  
    103.     for(int i=1; i*i<=1000000; i++)
    104.     {
    105.         book[i*i]=1;
    106.     }
    107.     int nn,num=1,nown=0;
    108.     cin>>nn;
    109.  
    110.  
    111.     st=0;
    112.     ed=5000;
    113.  
    114.     while(1)
    115.     {
    116.  
    117.         add(st,num,1);
    118.         add(num,st,0);
    119.  
    120.         add(num+ed,ed,1);
    121.         add(ed,num+ed,0);
    122.  
    123.         for(int i=1; i<=num-1; i++)
    124.         {
    125.             if(book[i+num])
    126.             {
    127.                 add(num,i+ed,1);
    128.  
    129.                 add(i+ed,num,0);
    130.             }
    131.         }
    132.  
    133.         int temp=0;
    134.  
    135.         while(bfs())
    136.         {
    137.             temp+=dfs(st,1e18);
    138.  
    139.         }
    140.  
    141.         if(temp==0)
    142.             nown++;
    143.  
    144.         if(nown>nn)
    145.         {
    146.             break;
    147.  
    148.         }
    149.  
    150.         ans+=temp;
    151.  
    152.         num++;
    153.  
    154.     }
    155.  
    156.  
    157.     num--;
    158.     cout<
    159.  
    160.     for(int i=2; i
    161.     {
    162.         if(s[i].b>=1&&s[i].b<=num&&s[i].e>=num+1&&s[i].e<=num+ed&&s[i].val==0)
    163.         {
    164.             pre[s[i].e-ed]=s[i].b;
    165.             last[s[i].b]=s[i].e-ed;
    166.  
    167.         }
    168.     }
    169.  
    170.     for(int i=1; i<=num; i++)
    171.     {
    172.         if(!pre[i])
    173.         {
    174.             int now=i;
    175.  
    176.             while(now)
    177.             {
    178.                 cout<" ";
    179.  
    180.                 now=last[now];
    181.             }
    182.  
    183.             cout<
    184.  
    185.         }
    186.     }
    187.  
    188.  
    189.     return 0;
    190.  
    191.  
    192. }

    拆点控流 例题四

    众所周知，网络流对于流量的控制体现于边权，而遇到严格控制点经过次数的模型，我们需要将点拆为正副点相连的边，边权为允许使用的次数

    如图，点1会被经历无数次，而点2有了瓶颈限制，故只能经历1次

    仅依靠边权控流的谬误性

    下图中，蓝色点给予红色点各一点流量，红色点给予黄色点各一点流量，而红色点被流经两次，可见仅靠边权控流是不够的

     最长不下降子序列问题 - 洛谷​​​​​​

    建图要点

    一，为了严格把控每个点的使用次数，我们必须把每个点都拆解成正副点

    二，为了严格控制最长不下降子序列的长度，我们让超级原点连接dp[i]为1的点，dp[i]为最长不下降子序列长度的点连接超级汇点，其余各点，严格按照dp值相差1，位置前后关系，大小关系进行连边

    三，我们超级汇点接受的流量，是由超级原点出发，途径大小严格递增，位置前后关系有序， dp值逐位加1的流量路径而得的，故其正确性可以保证

    针对第三问，只需要在拆点而成的1，n两点，撤销流量限制，并且取消超级原点提供给位置1，超级汇点接受位置n的流量限制即可（在位置n能够连接超级汇点的前提下）

    1. #include
    2. using namespace std;
    3.  
    4. typedef long long int ll;
    5.  
    6. typedef struct
    7. {
    8.     int b,e;
    9.     ll val;
    10. }xinxi;
    11. xinxi s[101010];
    12. int f[101010],nex[101010],len=2,n,m, dep[101010];
    13.  
    14. void add(int x,int y,ll z)
    15. {
    16.     s[len].b=x;
    17.     s[len].e=y;
    18.     s[len].val=z;
    19.     nex[len]=f[x];
    20.     f[x]=len;
    21.     len++;
    22.  
    23.  
    24. }
    25. queue<int>q;
    26.  
    27. bool  bfs()
    28. {
    29.     memset(dep,0,sizeof(dep));
    30.  
    31.     dep[st]=1;
    32.  
    33.     while(!q.empty())
    34.         q.pop();
    35.  
    36.     q.push(st);
    37.  
    38.     while(!q.empty())
    39.     {
    40.         int now=q.front();
    41.  
    42.         q.pop();
    43.  
    44.         int x=f[now];
    45.  
    46.         while(x!=-1)
    47.         {
    48.             int j=s[x].e;
    49.  
    50.             if(s[x].val&&!dep[j])
    51.             {
    52.                 dep[j]=dep[now]+1;
    53.                 q.push(j);
    54.             }
    55.  
    56.             x=nex[x];
    57.         }
    58.     }
    59.  
    60.     return dep[ed];
    61. }
    62.  
    63. ll dfs(int now,ll flow)
    64. {
    65.     if(now==ed)
    66.         return flow;
    67.  
    68.     int x=f[now];
    69.  
    70.     ll out=0;
    71.     while(x!=-1)
    72.     {
    73.         int j=s[x].e;
    74.  
    75.         if(s[x].val&&dep[j]==dep[now]+1)
    76.         {
    77.             ll res=dfs(j,min(s[x].val,flow));
    78.  
    79.             s[x].val-=res;
    80.  
    81.             s[x^1].val+=res;
    82.  
    83.             flow-=res;
    84.  
    85.             out+=res;
    86.  
    87.         }
    88.  
    89.         if(!flow)
    90.             break;
    91.         x=nex[x];
    92.  
    93.     }
    94.  
    95.     if(!out)
    96.         dep[now]=0;
    97.  
    98.     return out;
    99. }
    100.  
    101. int a[1010],dp[1010];
    102.  
    103. int main()
    104. {
    105.  
    106. memset(f,-1,sizeof(f));
    107.  
    108.   cin>>n;
    109.   
    110.   if(n==1)
    111.   {
    112.       cout<<1<1<1<
    113.       
    114.       return 0;
    115.   }
    116.  
    117.   for(int i=1;i<=n;i++)
    118.   {
    119.       cin>>a[i];
    120.  
    121.       dp[i]=1;
    122.   }
    123.  
    124.   st=0;
    125.   ed=5000;
    126.  
    127.   for(int i=2;i<=n;i++)
    128.   {
    129.       for(int j=1;j
    130.       {
    131.           if(a[i]>=a[j])
    132.           dp[i]=max(dp[i],dp[j]+1);
    133.       }
    134.   }
    135. int maxx=0;
    136.   for(int i=1;i<=n;i++)
    137.   {
    138.       maxx=max(maxx,dp[i]);
    139.       if(dp[i]==1)
    140.       {
    141.           add(st,i,1);
    142.  
    143.           add(i,st,0);
    144.       }
    145.   }
    146.  
    147.   for(int i=1;i<=n;i++)
    148.   {
    149.       if(dp[i]==maxx)
    150.       {
    151.           add(i+n,ed,1);
    152.  
    153.           add(ed,i+n,0);
    154.       }
    155.   }
    156.  
    157.   for(int i=1;i<=n;i++)
    158.   {
    159.       add(i,i+n,1);
    160.       add(i+n,i,0);
    161.   }
    162.   for(int i=1;i<=n;i++)
    163.   {
    164.  
    165.       for(int j=1;j
    166.       {
    167.           if(a[i]>=a[j]&&dp[i]==dp[j]+1)
    168.           {
    169.               //建立
    170.               add(j+n,i,1);
    171.  
    172.               add(i,j+n,0);
    173.           }
    174.       }
    175.   }
    176.  
    177.   cout<
    178.  
    179.   ll ans=0;
    180.   while(bfs())
    181.   {
    182.       ans+=dfs(st,1e18);
    183.   }
    184.  
    185.   cout<
    186.  
    187.   add(st,1,1e18);
    188.  
    189.   add(1,1+n,1e18);
    190.  
    191.   add(n,n+n,1e18);
    192.   if(dp[n]==maxx)
    193.   add(n,ed,1e18);
    194.  
    195.   while(bfs())
    196.   {
    197.       ans+=dfs(st,1e18);
    198.   }
    199.  
    200.   cout<
    201.  
    202.  
    203.     return 0;
    204. }

    拆点控流

    例题五

    [CQOI2015]网络吞吐量 - 洛谷

    与上一题不同的是，本题的路径是基于最短路的，故先筛选出来最短路径的边，进行连边即可

    建图要点

    一，超级原点与1号点之间是无穷权值，n号点与超级汇点之间也是无穷权值，二者不需要拆点，因为容量并无限制

    二，具有容量限制的点必须拆点，边权即为容量限制

    三，其余路径的流量统一设置为无穷，因为可以经过一个节点的次数是任意的，在拆点限流的情况下，其余路径的流量足够大即可

    1. #include
    2. using namespace std;
    3.  
    4. typedef long long int ll;
    5.  
    6. ll edge[1010][1010],inf=1e18,dis[1010],st,ed, n,m,dep[2020];
    7.  
    8. queue<int>q;
    9.  
    10. struct node
    11. {
    12.     int id;
    13.  
    14.     ll dis;
    15.  
    16.     friend bool operator<(node a, node b)
    17.     {
    18.         return a.dis>b.dis;
    19.     }
    20. };
    21.  
    22. priority_queueqq;
    23.  
    24. bool book[1010];
    25.  
    26. void work()
    27. {
    28.     for(int i=1; i<=n; i++)
    29.     {
    30.         dis[i]=inf;
    31.     }
    32.  
    33.     dis[1]=0;
    34.  
    35.     struct node head;
    36.  
    37.     head.id=1;
    38.     head.dis=0;
    39.  
    40.  
    41.     qq.push(head);
    42.  
    43.     while(!qq.empty())
    44.     {
    45.         struct node now=qq.top();
    46.         qq.pop();
    47.  
    48.         if(book[now.id])
    49.             continue;
    50.  
    51.         book[now.id]=1;
    52.  
    53.         for(int i=1; i<=n; i++)
    54.         {
    55.             if(edge[now.id][i]!=inf)
    56.             {
    57.                 if(dis[i]>dis[now.id]+edge[now.id][i])
    58.                 {
    59.                     dis[i]=dis[now.id]+edge[now.id][i];
    60.  
    61.                     struct node tail;
    62.  
    63.                     tail.dis=dis[i];
    64.  
    65.                     tail.id=i;
    66.  
    67.                     qq.push(tail);
    68.                 }
    69.             }
    70.         }
    71.     }
    72.  
    73. }
    74.  
    75.  
    76. typedef struct
    77. {
    78.     int b,e;
    79.     ll val;
    80. } xinxi;
    81. xinxi s[101010];
    82. int f[101010],nex[101010],len=2;
    83.  
    84. void add(int x,int y,ll z)
    85. {
    86.     s[len].b=x;
    87.     s[len].e=y;
    88.     s[len].val=z;
    89.     nex[len]=f[x];
    90.     f[x]=len;
    91.     len++;
    92.  
    93. }
    94.  
    95. bool  bfs()
    96. {
    97.     memset(dep,0,sizeof(dep));
    98.  
    99.     dep[st]=1;
    100.  
    101.     while(!q.empty())
    102.         q.pop();
    103.  
    104.     q.push(st);
    105.  
    106.     while(!q.empty())
    107.     {
    108.         int now=q.front();
    109.  
    110.         q.pop();
    111.  
    112.         int x=f[now];
    113.  
    114.         while(x!=-1)
    115.         {
    116.             int j=s[x].e;
    117.  
    118.             if(s[x].val&&!dep[j])
    119.             {
    120.                 dep[j]=dep[now]+1;
    121.                 q.push(j);
    122.             }
    123.  
    124.             x=nex[x];
    125.         }
    126.     }
    127.  
    128.     return dep[ed];
    129. }
    130.  
    131. ll dfs(int now,ll flow)
    132. {
    133.     if(now==ed)
    134.         return flow;
    135.  
    136.     int x=f[now];
    137.  
    138.  
    139.     ll out=0;
    140.  
    141.     while(x!=-1)
    142.     {
    143.         int j=s[x].e;
    144.  
    145.         if(s[x].val&&dep[j]==dep[now]+1)
    146.         {
    147.             ll res=dfs(j,min(s[x].val,flow));
    148.  
    149.             s[x].val-=res;
    150.  
    151.             s[x^1].val+=res;
    152.  
    153.             flow-=res;
    154.  
    155.             out+=res;
    156.  
    157.         }
    158.  
    159.         if(!flow)
    160.             break;
    161.         x=nex[x];
    162.  
    163.     }
    164.  
    165.     if(!out)
    166.         dep[now]=0;
    167.  
    168.     return out;
    169. }
    170.  
    171. ll val[101010];
    172. int main()
    173. {
    174.  
    175.  
    176.     memset(f,-1,sizeof(f));
    177.     cin>>n>>m;
    178.  
    179.     st=0;
    180.     ed=2*n+1;
    181.  
    182.     for(int i=1; i<=n; i++)
    183.     {
    184.         for(int j=1; j<=n; j++)
    185.         {
    186.             edge[i][j]=inf;
    187.         }
    188.     }
    189.     for(int i=1; i<=m; i++)
    190.     {
    191.         int x,y;
    192.         ll z;
    193.         cin>>x>>y>>z;
    194.  
    195.         edge[x][y]=min(edge[x][y],z);
    196.  
    197.         edge[y][x]=min(edge[y][x],z);
    198.     }
    199.  
    200.  
    201.     work();
    202.  
    203.  
    204.  
    205.     for(int i=1; i<=n; i++)
    206.     {
    207.         cin>>val[i];
    208.     }
    209.  
    210.  
    211.     add(st,1,inf);
    212.  
    213.     add(1,st,0);
    214.  
    215.     add(n+n,ed,inf);
    216.  
    217.     add(ed,n+n,0);
    218.  
    219.  
    220.     for(int i=1; i<=n; i++)
    221.     {
    222.         if(i!=1&&i!=n)
    223.         {
    224.             add(i,i+n,val[i]);
    225.  
    226.             add(i+n,i,0);
    227.  
    228.         }
    229.  
    230.         else
    231.         {
    232.             add(i,i+n,inf);
    233.  
    234.             add(i+n,i,0);
    235.         }
    236.  
    237.     }
    238.  
    239.     for(int i=1; i<=n; i++)
    240.     {
    241.         for(int j=1; j<=n; j++)
    242.         {
    243.             if(dis[i]+edge[i][j]==dis[j])
    244.             {
    245.                 add(i+n,j,inf);
    246.  
    247.                 add(j,i+n,0);
    248.             }
    249.         }
    250.     }
    251.  
    252.  
    253.     ll ans=0;
    254.     while(bfs())
    255.     {
    256.         ans+=dfs(st,1e18);
    257.     }
    258.  
    259.     cout<
    260.     return 0;
    261. }

    拆点控流 



    [SCOI2007] 蜥蜴 - 洛谷

    仍旧是拆点，石柱就是点，L就是起始点，其高度就是容量，也就是能支持跳跃的次数，终点就是最终能够跳出去的点，注意inf的边，也就是我们控流之后无所谓的边，都设置成inf即可 

    1. #include
    2. using namespace std;
    3.  
    4. typedef long long int ll;
    5.  
    6. int n,m,d,st,ed,a[100][100],num=0,id[100][100],f[101010],nex[101010],len=2,dep[101010];
    7. char mp[100][100];
    8. ll inf=1e18;
    9.  
    10. typedef struct
    11. {
    12.     int b,e;
    13.     ll val;
    14. } xinxi;
    15. xinxi s[101010];
    16.  
    17. void add(int x,int y,ll z)
    18. {
    19.     s[len].b=x;
    20.     s[len].e=y;
    21.     s[len].val=z;
    22.     nex[len]=f[x];
    23.     f[x]=len;
    24.     len++;
    25. }
    26. queue<int>q;
    27. bool bfs()
    28. {
    29.     memset(dep,0,sizeof(dep));
    30.  
    31.     while(!q.empty())
    32.         q.pop();
    33.  
    34.     dep[st]=1;
    35.  
    36.     q.push(st);
    37.  
    38.     while(!q.empty())
    39.     {
    40.         int now=q.front();
    41.         q.pop();
    42.         int x=f[now];
    43.         while(x!=-1)
    44.         {
    45.             int j=s[x].e;
    46.  
    47.             if(s[x].val&&!dep[j])
    48.             {
    49.                 dep[j]=dep[now]+1;
    50.                 q.push(j);
    51.             }
    52.             x=nex[x];
    53.         }
    54.     }
    55.  
    56.     return dep[ed];
    57. }
    58.  
    59. ll dfs(int now,ll flow)
    60. {
    61.     if(now==ed)
    62.         return flow;
    63.  
    64.     int x=f[now];
    65.  
    66.     ll out=0;
    67.     while(x!=-1)
    68.     {
    69.         int j=s[x].e;
    70.  
    71.         if(s[x].val&&dep[j]==dep[now]+1)
    72.         {
    73.             ll res=dfs(j,min(flow,s[x].val));
    74.  
    75.             s[x].val-=res;
    76.  
    77.             s[x^1].val+=res;
    78.  
    79.             flow-=res;
    80.  
    81.             out+=res;
    82.         }
    83.  
    84.         if(!flow)
    85.             break;
    86.         x=nex[x];
    87.     }
    88.  
    89.     if(!out)
    90.         dep[now]=0;
    91.  
    92.     return out;
    93. }
    94. int main()
    95. {
    96.  
    97.     st=0;
    98.     memset(f,-1,sizeof(f));
    99.     cin>>n>>m>>d;
    100.  
    101.     for(int i=1; i<=n; i++)
    102.     {
    103.         for(int j=1; j<=m; j++)
    104.         {
    105.             char ch;
    106.             cin>>ch;
    107.             a[i][j]=ch-'0';
    108.             if(a[i][j])
    109.             {
    110.                 num++;
    111.                 id[i][j]=num;
    112.             }
    113.         }
    114.     }
    115.  
    116.     ed=num*2+3;
    117.     int cnt=0;
    118.  
    119.     for(int i=1; i<=n; i++)
    120.     {
    121.         for(int j=1; j<=m; j++)
    122.         {
    123.             cin>>mp[i][j];
    124.  
    125.             if(mp[i][j]=='L')
    126.             {
    127.                 add(st,id[i][j],1);
    128.                 cnt++;
    129.                 add(id[i][j],st,0);
    130.             }
    131.         }
    132.     }
    133.  
    134.     for(int i=1; i<=n; i++)
    135.     {
    136.         for(int j=1; j<=m; j++)
    137.         {
    138.             if(a[i][j])
    139.             {
    140.                 if(i-d<=0||i+d>n||j-d<=0||j+d>m)
    141.                 {
    142.                     add(id[i][j]+num,ed,inf);
    143.                     add(ed,id[i][j]+num,0);
    144.                 }
    145.             }
    146.         }
    147.     }
    148.  
    149.     for(int i=1; i<=n; i++)
    150.     {
    151.         for(int j=1; j<=m; j++)
    152.         {
    153.             if(a[i][j])
    154.             {
    155.                 add(id[i][j],id[i][j]+num,a[i][j]);
    156.                 
    157.                 add(id[i][j]+num,id[i][j],0);
    158.             }
    159.         }
    160.     }
    161.  
    162.     for(int i=1; i<=n; i++)
    163.     {
    164.         for(int j=1; j<=m; j++)
    165.         {
    166.             if(a[i][j])
    167.             {
    168.                 for(int ii=1; ii<=n; ii++)
    169.                 {
    170.                     for(int jj=1; jj<=m; jj++)
    171.                     {
    172.                         if(i==ii&&j==jj)
    173.                             continue;
    174.                             
    175.                         if(d*d>=(ii-i)*(ii-i)+(jj-j)*(jj-j)&&a[ii][jj])
    176.                         {
    177.                             add(id[i][j]+num,id[ii][jj],inf);
    178.                             
    179.                             add(id[ii][jj],id[i][j]+num,0);
    180.                         }
    181.                     }
    182.                 }
    183.             }
    184.         }
    185.     }
    186.  
    187.  
    188.     ll ans=0;
    189.  
    190.     while(bfs())
    191.     {
    192.         ans+=dfs(st,1e18);
    193.     }
    194.  
    195.     cout<
    196.     return 0;
    197. }

     二分图的网络流解法

     飞行员配对方案问题 - 洛谷

    建图要点

    一，一一对应的特性不仅体现在边权是1，而且是只有左右集，否则就会出现一配对多的情况

    二，残流网络为0的边就是配对关系，输出即可 

     

    1. #include
    2. using namespace std;
    3.  
    4. typedef long long int ll;
    5.  
    6. typedef struct
    7. {
    8.     int b,e;
    9.     ll val;
    10. } xinxi;
    11.  
    12. xinxi s[101010];
    13. int f[101010],nex[101010],len=2,pre[101010],last[101010],n,m,st,ed, dep[101010];
    14.  
    15. void add(int x,int y,ll z)
    16. {
    17.     s[len].b=x;
    18.     s[len].e=y;
    19.     s[len].val=z;
    20.     nex[len]=f[x];
    21.     f[x]=len;
    22.     len++;
    23. }
    24.  
    25. queue<int>q;
    26.  
    27. bool bfs()
    28. {
    29.     memset(dep,0,sizeof(dep));
    30.  
    31.     while(!q.empty())
    32.         q.pop();
    33.  
    34.     q.push(st);
    35.  
    36.     dep[st]=1;
    37.  
    38.     while(!q.empty())
    39.     {
    40.         int now=q.front();
    41.         q.pop();
    42.  
    43.         int x=f[now];
    44.  
    45.  
    46.         while(x!=-1)
    47.         {
    48.  
    49.             int j=s[x].e;
    50.  
    51.             if(s[x].val&&!dep[j])
    52.             {
    53.                 dep[j]=dep[now]+1;
    54.                 q.push(j);
    55.             }
    56.  
    57.             x=nex[x];
    58.  
    59.         }
    60.     }
    61.  
    62.     return dep[ed];
    63. }
    64.  
    65. ll dfs(int now, ll flow)
    66. {
    67.     if(now==ed)
    68.         return flow;
    69.  
    70.     ll out=0;
    71.  
    72.     int x=f[now];
    73.     while(x!=-1)
    74.     {
    75.         int j=s[x].e;
    76.  
    77.         if(s[x].val&&dep[j]==dep[now]+1)
    78.         {
    79.             ll res=dfs(j,min(flow,s[x].val));
    80.  
    81.             s[x].val-=res;
    82.  
    83.             s[x^1].val+=res;
    84.  
    85.  
    86.             flow-=res;
    87.  
    88.             out+=res;
    89.  
    90.         }
    91.  
    92.         if(!flow)
    93.             break;
    94.         x=nex[x];
    95.     }
    96.  
    97.     if(!out)
    98.         dep[now]=0;
    99.  
    100.     return out;
    101. }
    102.  
    103. int main()
    104. {
    105.  
    106.  
    107.  
    108.     memset(f,-1,sizeof(f));
    109.  
    110.     cin>>m>>n;
    111.  
    112.     int x,y;
    113.  
    114.     ed=n+1;
    115.  
    116.     while(cin>>x>>y)
    117.     {
    118.  
    119.         if(x==-1)
    120.             break;
    121.  
    122.         add(x,y,1);
    123.         add(y,x,0);
    124.  
    125.     }
    126.  
    127.     for(int i=1; i<=m; i++)
    128.     {
    129.         add(st,i,1);
    130.         add(i,st,0);
    131.     }
    132.  
    133.     for(int i=m+1; i<=n; i++)
    134.     {
    135.         add(i,ed,1);
    136.         add(ed,i,0);
    137.  
    138.     }
    139.  
    140.     ll ans=0;
    141.  
    142.  
    143.     while(bfs())
    144.     {
    145.         ans+=dfs(st,1e18);
    146.     }
    147.  
    148.     cout<
    149.  
    150.     for(int i=2;i
    151.     {
    152.         if(s[i].b>=1&&s[i].b<=m&&s[i].e>m&&s[i].e<=n&&s[i].val==0)
    153.         {
    154.             pre[s[i].e]=s[i].b;
    155.             last[s[i].b]=s[i].e;
    156.         }
    157.     }
    158.  
    159.     for(int i=1;i<=m;i++)
    160.     {
    161.         if(pre[i]==0&&last[i])
    162.         {
    163.             cout<" "<
    164.         }
    165.     }
    166.  
    167.  
    168.     return 0;
    169. }

    网络流对于匹配问题相对于二分图的灵活性

    圆桌问题 - 洛谷

    建图要点

    一，超级原点连接人员不仅为人员点提供了人数，更限制了每个人员所能流出的边数

    二，每种人员对每个餐桌都连容量为1的边，保证了一个餐桌不会出现同种人员

    三，餐桌对超级汇点连接容量是C的边，保证了餐桌不会超过容量

    至于是否可行，只需判断S流出的是否被T全部接收即可，答案输出由残流网络确定即可

    1. #include
    2. using namespace std;
    3.  
    4. typedef long long int ll;
    5. int n,m, r[10010],c[10010],st,ed;
    6.  
    7. typedef struct
    8. {
    9.     int b,e;
    10.     ll val;
    11. } xinxi;
    12.  
    13. xinxi s[101010];
    14. int f[101010],nex[101010],len=2;
    15.  
    16. void add(int x,int y,ll z)
    17. {
    18.     s[len].b=x;
    19.     s[len].e=y;
    20.     s[len].val=z;
    21.     nex[len]=f[x];
    22.     f[x]=len;
    23.  
    24.     len++;
    25. }
    26.  
    27. queue<int>q;
    28.  
    29. int dep[101010];
    30.  
    31. bool bfs()
    32. {
    33.     memset(dep,0,sizeof(dep));
    34.  
    35.     while(!q.empty())
    36.         q.pop();
    37.  
    38.     q.push(st);
    39.     dep[st]=1;
    40.  
    41.     while(!q.empty())
    42.     {
    43.         int now=q.front();
    44.         q.pop();
    45.  
    46.         int x=f[now];
    47.  
    48.         while(x!=-1)
    49.         {
    50.             int j=s[x].e;
    51.  
    52.             if(s[x].val&&!dep[j])
    53.             {
    54.                 dep[j]=dep[now]+1;
    55.                 q.push(j);
    56.             }
    57.  
    58.             x=nex[x];
    59.         }
    60.     }
    61.  
    62.     return dep[ed];
    63. }
    64.  
    65. ll dfs(int now, ll flow)
    66. {
    67.     if(now==ed)
    68.         return flow;
    69.  
    70.     ll out=0;
    71.  
    72.     int x=f[now];
    73.  
    74.     while(x!=-1)
    75.     {
    76.         int j=s[x].e;
    77.  
    78.         if(s[x].val&&dep[j]==dep[now]+1)
    79.         {
    80.             ll res=dfs(j,min(flow,s[x].val));
    81.  
    82.             s[x].val-=res;
    83.  
    84.             s[x^1].val+=res;
    85.  
    86.             flow-=res;
    87.  
    88.             out+=res;
    89.         }
    90.  
    91.         x=nex[x];
    92.     }
    93.  
    94.     if(!out)
    95.         dep[now]=0;
    96.     return out;
    97.  
    98. }
    99.  
    100.  
    101. vector<int>v[10010];
    102. int main()
    103. {
    104.  
    105.  
    106.     cin>>n>>m;
    107.  
    108.     m+=n;
    109.     memset(f,-1,sizeof(f));
    110.  
    111.     ed=m+1;
    112.  
    113.     int sum=0;
    114.     for(int i=1; i<=n; i++)
    115.     {
    116.         cin>>r[i];
    117.  
    118.         sum+=r[i];
    119.         add(st,i,r[i]);
    120.         add(i,st,0);
    121.     }
    122.  
    123.     for(int i=1; i<=m-n; i++)
    124.     {
    125.         cin>>c[i];
    126.  
    127.         add(i+n,ed,c[i]);
    128.         add(ed,i+n,0);
    129.     }
    130.  
    131.     for(int i=1; i<=n; i++)
    132.     {
    133.         for(int j=n+1; j<=m; j++)
    134.         {
    135.             add(i,j,1);
    136.             add(j,i,0);
    137.         }
    138.     }
    139.  
    140.     ll ans=0;
    141.  
    142.     while(bfs())
    143.     {
    144.         ans+=dfs(st,1e18);
    145.     }
    146.  
    147.     if(ans==sum)
    148.     {
    149.         cout<<1<
    150.  
    151.         for(int i=2; i
    152.         {
    153.             if(s[i].val==0&&s[i].b>=1&&s[i].b<=n&&s[i].e>n&&s[i].e<=m)
    154.             {
    155.                 v[s[i].b].push_back(s[i].e-n);
    156.             }
    157.         }
    158.  
    159.         for(int i=1; i<=n; i++)
    160.         {
    161.             for(auto it:v[i])
    162.             {
    163.                 cout<" ";
    164.             }
    165.  
    166.             cout<
    167.         }
    168.     }
    169.     else
    170.     {
    171.         cout<<0;
    172.     }
    173.  
    174.  
    175.  
    176.     return 0;
    177. }

    其他例题

     Fox And Dinner - 洛谷

    圆环上任意相连两点之和都是质数，任意一点权值都是大于等于2的，这也就意味着，任意相邻两点 之和一定是奇数，考虑左集为偶数，右集为奇数

    这样，我们便把模型转化为，一个偶数必须有两个奇数与之相连且和为质数，一个奇数必须有两个偶数与之相连且和为质数。

    判断无解的情况时，显然偶数与奇数必须是数量相同的，另外，S流出的全部流量T要全部接入，这样才能保证每个偶数都有两个奇数与之相邻，任意奇数都有两个偶数与之相邻。

    至于答案输出，在残流网络上寻找偶数到奇数且流量为0的边，进行双向连边操作，然后对于每一个点找环并标记即可，当前是奇数，那么下一个就是偶数，偶数同理，严格按照这种方式遍历，我们一定会标记出来一个合法的环

    1. #include
    2. using namespace std;
    3.  
    4. typedef long long int ll;
    5.  
    6.  
    7. bool check(int x)
    8. {
    9.     if(x==2)
    10.         return 1;
    11.  
    12.     for(int i=2; i*i<=x; i++)
    13.     {
    14.         if(x%i==0)
    15.             return 0;
    16.     }
    17.  
    18.     return 1;
    19. }
    20.  
    21. int L[1010],R[1010],len1=0,len2=0, n,st,ed;
    22. typedef struct
    23. {
    24.     int b,e;
    25.     ll val;
    26. } xinxi;
    27. xinxi s[101010];
    28. int f[101010],nex[101010],len=2;
    29.  
    30. void add(int x,int y,ll z)
    31. {
    32.     s[len].b=x;
    33.     s[len].e=y;
    34.     s[len].val=z;
    35.     nex[len]=f[x];
    36.     f[x]=len;
    37.     len++;
    38. }
    39.  
    40. queue<int>q;
    41. int dep[101010];
    42. bool bfs()
    43. {
    44.     memset(dep,0,sizeof(dep));
    45.  
    46.     while(!q.empty())
    47.         q.pop();
    48.  
    49.     dep[st]=1;
    50.  
    51.     q.push(st);
    52.  
    53.     while(!q.empty())
    54.     {
    55.         int now=q.front();
    56.         q.pop();
    57.  
    58.         int x=f[now];
    59.  
    60.         while(x!=-1)
    61.         {
    62.             int j=s[x].e;
    63.  
    64.             if(s[x].val&&!dep[j])
    65.             {
    66.                 dep[j]=dep[now]+1;
    67.  
    68.                 q.push(j);
    69.             }
    70.  
    71.             x=nex[x];
    72.         }
    73.     }
    74.  
    75.     return dep[ed];
    76.  
    77. }
    78.  
    79.  
    80. ll dfs(int now, ll flow)
    81. {
    82.     if(now==ed)
    83.         return flow;
    84.  
    85.     ll out=0;
    86.     int x=f[now];
    87.  
    88.     while(x!=-1)
    89.     {
    90.         int j=s[x].e;
    91.  
    92.         if(s[x].val&&dep[j]==dep[now]+1)
    93.         {
    94.             ll res=dfs(j,min(flow,s[x].val));
    95.  
    96.             s[x].val-=res;
    97.  
    98.             s[x^1].val+=res;
    99.  
    100.             flow-=res;
    101.  
    102.             out+=res;
    103.         }
    104.  
    105.         if(!flow)
    106.             break;
    107.         x=nex[x];
    108.     }
    109.  
    110.     if(!out)
    111.         dep[now]=0;
    112.  
    113.     return out;
    114. }
    115.  
    116. vector<int>v[1010],work[1010];
    117. int cnt=0,vis[101010], pre[1010],book1[1010],book2[1010];
    118. void getans(int now,int type)
    119. {
    120.     vis[now]=1;
    121.  
    122.  
    123.     work[cnt].push_back(now);
    124.  
    125.     for(auto it:v[now])
    126.     {
    127.         if(vis[it]==0)
    128.         {
    129.             if(type==1)
    130.             {
    131.                 if(book2[it])
    132.                 {
    133.                     getans(it,0);
    134.                 }
    135.             }
    136.  
    137.             else
    138.             {
    139.                 if(book1[it])
    140.                 {
    141.                     getans(it,1);
    142.                 }
    143.             }
    144.         }
    145.     }
    146. }
    147.  
    148. int main()
    149. {
    150.  
    151.  
    152.     cin>>n;
    153.  
    154.     for(int i=1; i<=n; i++)
    155.     {
    156.         cin>>pre[i];
    157.         if(pre[i]&1)
    158.         {
    159.             len1++;
    160.  
    161.             L[len1]=i;
    162.  
    163.             book1[i]=1;
    164.         }
    165.         else
    166.         {
    167.             len2++;
    168.  
    169.             R[len2]=i;
    170.  
    171.             book2[i]=1;
    172.         }
    173.     }
    174.  
    175.  
    176.     if(len1!=len2)
    177.     {
    178.         cout<<"Impossible";
    179.  
    180.         return 0;
    181.     }
    182.     st=0;
    183.     memset(f,-1,sizeof(f));
    184.     for(int i=1; i<=len1; i++)
    185.     {
    186.         add(st,L[i],2);
    187.  
    188.         add(L[i],st,0);
    189.     }
    190.  
    191.     ed=n+1;
    192.  
    193.  
    194.     for(int i=1; i<=len2; i++)
    195.     {
    196.         add(R[i],ed,2);
    197.  
    198.         add(ed,R[i],0);
    199.     }
    200.  
    201.     for(int i=1; i<=len1; i++)
    202.     {
    203.         for(int j=1; j<=len2; j++)
    204.         {
    205.             if(check(pre[L[i]]+pre[R[j]]))
    206.             {
    207.                 add(L[i],R[j],1);
    208.  
    209.                 add(R[j],L[i],0);
    210.             }
    211.         }
    212.     }
    213.  
    214.     ll ans=0;
    215.  
    216.     while(bfs())
    217.     {
    218.         ans+=dfs(st,1e18);
    219.  
    220.     }
    221.  
    222.     if(ans!=len2*2)
    223.     {
    224.         cout<<"Impossible";
    225.  
    226.         return 0;
    227.     }
    228.  
    229.  
    230.     memset(vis,0,sizeof(vis));
    231.  
    232.  
    233.     for(int i=2; i
    234.     {
    235.         if(s[i].val==0&&book1[s[i].b]&&book2[s[i].e])
    236.         {
    237.             v[s[i].b].push_back(s[i].e);
    238.  
    239.             v[s[i].e].push_back(s[i].b);
    240.         }
    241.     }
    242.     for(int i=1; i<=len1; i++)
    243.     {
    244.         if(!vis[L[i]])
    245.         {
    246.             cnt++;
    247.  
    248.             getans(L[i],1);
    249.         }
    250.     }
    251.  
    252.  
    253.  
    254.     cout<
    255.  
    256.     for(int i=1; i<=cnt; i++)
    257.     {
    258.  
    259.         cout<size()<<" ";
    260.  
    261.         for(auto it:work[i])
    262.         {
    263.             cout<" ";
    264.  
    265.  
    266.         }
    267.  
    268.         cout<
    269.     }
    270.  
    271.  
    272.     return 0;
    273. }

    其他例题 

    [USACO07OPEN]Dining G - 洛谷

    每种食物或者饮料都只能被使用一次，每个牛只能享用一种食物和一种饮料，考虑把牛建立在饮料与食物之间，这样流过去之后，一个牛势必要和饮料和食物相连

    值得注意的是，牛必须被拆点，否则就会出现下图上面牛的情况，而我们拆点之后就可以完美避开一个牛占有了多个食物与饮料的情况

     

    1. #include
    2. using namespace std;
    3.  
    4. typedef long long int ll;
    5.  
    6. //超级原点对饮料F进行连边
    7. //内部奶牛正负链边
    8. //副奶牛连接食物D
    9. //食物对超级汇点进行连边
    10. typedef struct
    11. {
    12.     int b,e;
    13.     ll val;
    14. } xinxi;
    15. xinxi s[101010];
    16. int f[101010],nex[101010],len=2;
    17.  
    18. void add(int x,int y,ll z)
    19. {
    20.     s[len].b=x;
    21.     s[len].e=y;
    22.     s[len].val=z;
    23.     nex[len]=f[x];
    24.     f[x]=len;
    25.     len++;
    26. }
    27. int n,m1,m2,st,ed, dep[101010];
    28. queue<int>q;
    29. bool bfs()
    30. {
    31.     memset(dep,0,sizeof(dep));
    32.  
    33.     while(!q.empty())
    34.         q.pop();
    35.  
    36.     q.push(st);
    37.     dep[st]=1;
    38.  
    39.     while(!q.empty())
    40.     {
    41.         int now=q.front();
    42.         q.pop();
    43.  
    44.         int x=f[now];
    45.  
    46.         while(x!=-1)
    47.         {
    48.             int j=s[x].e;
    49.  
    50.             if(!dep[j]&&s[x].val)
    51.             {
    52.                 dep[j]=dep[now]+1;
    53.                 q.push(j);
    54.             }
    55.  
    56.             x=nex[x];
    57.         }
    58.     }
    59.  
    60.     return dep[ed];
    61. }
    62.  
    63.  
    64. ll dfs(int now, ll flow)
    65. {
    66.     if(now==ed)
    67.         return flow;
    68.  
    69.     ll out=0;
    70.  
    71.     int x=f[now];
    72.  
    73.     while(x!=-1)
    74.     {
    75.         int j=s[x].e;
    76.  
    77.         if(dep[j]==dep[now]+1&&s[x].val)
    78.         {
    79.             ll res=dfs(j,min(flow,s[x].val));
    80.  
    81.             s[x].val-=res;
    82.  
    83.             s[x^1].val+=res;
    84.  
    85.             flow-=res;
    86.  
    87.             out+=res;
    88.         }
    89.  
    90.         if(!flow)
    91.             break;
    92.         x=nex[x];
    93.     }
    94.  
    95.     if(!out)
    96.         dep[now]=0;
    97.  
    98.     return out;
    99. }
    100. int main()
    101. {
    102.  
    103.     memset(f,-1,sizeof(f));
    104.  
    105.     cin>>n>>m1>>m2;
    106.  
    107.     //1-m1是饮料
    108.     //m1+1-m1+n是正点
    109.     //m1+1+n-m1+2n是副点
    110.     //m1+2n+1 -m1+2n+m2是食物
    111.     //m1+2n+m2+1是超级汇点
    112.  
    113.     ed=m1+2*n+m2+1;
    114.  
    115.  
    116.     for(int i=1; i<=m1; i++)
    117.     {
    118.         add(st,i,1);
    119.  
    120.         add(i,st,0);
    121.     }
    122.  
    123.     for(int i=1; i<=m2; i++)
    124.     {
    125.         add(i+m1+2*n,ed,1);
    126.  
    127.         add(ed,i+m1+2*n,0);
    128.  
    129.     }
    130.  
    131.     for(int i=1; i<=n; i++)
    132.     {
    133.         add(i+m1,i+m1+n,1);
    134.  
    135.         add(i+m1+n,i+m1,0);
    136.     }
    137.     for(int i=1; i<=n; i++)
    138.     {
    139.         int cntf,cntd;
    140.         cin>>cntf>>cntd;
    141.  
    142.         while(cntf--)
    143.         {
    144.             int x;
    145.             cin>>x;
    146.  
    147.             add(x,i+m1,1);
    148.  
    149.             add(i+m1,x,0);
    150.         }
    151.  
    152.         while(cntd--)
    153.         {
    154.             int x;
    155.             cin>>x;
    156.  
    157.             add(i+m1+n,x+m1+2*n,1);
    158.  
    159.             add(x+m1+2*n,i+m1+n,0);
    160.         }
    161.     }
    162.  
    163.     ll ans=0;
    164.  
    165.     while(bfs())
    166.     {
    167.         ans+=dfs(st,1e18);
    168.     }
    169.  
    170.     cout<
    171.  
    172.  
    173.  
    174.  
    175.     return 0;
    176. }

    分层图与网络流 

     [CTSC1999]家园 / 星际转移问题 - 洛谷

     地球初始与k人，那就先在time=0的时候超级原点给地球k的流量

    之后，time每加1，我们需要完成顺承与转运操作，之后跑最大流，无需担心本次的顺承会对转运造成影响，因为为了增加最大流，本次一定会优先考虑从上一个状态转运来使得月球获得流量，其次才是顺承，本次的顺承对于增加本次最大流毫无意义，即顺承的结果是在考虑到转运最优之后的结果。

    细节多，思维大，码量不少，还是比较有难度 

    1. #include
    2. using namespace std;
    3.  
    4. typedef long long int ll;
    5.  
    6. int fa[1010];
    7.  
    8. int n;
    9. int st,ed,m,sum;
    10. int getf(int x)
    11. {
    12.  
    13.  
    14.  
    15.     if(x==fa[x])
    16.         return x;
    17.     else
    18.     {
    19.         fa[x]=getf(fa[x]);
    20.  
    21.         return fa[x];
    22.     }
    23. }
    24.  
    25. int ren[1010];
    26. vector<int>zhou[1010];
    27.  
    28. void hebing(int x,int y)
    29. {
    30.     int t1=getf(x);
    31.     int t2=getf(y);
    32.  
    33.     fa[t1]=t2;
    34. }
    35.  
    36. typedef struct
    37. {
    38.     int b,e;
    39.     ll val;
    40. } xinxi;
    41. xinxi s[101010];
    42. int f[101010],nex[101010],len=2;
    43. ll inf=1e18;
    44.  
    45. void add(int x,int y,ll z)
    46. {
    47.     s[len].b=x;
    48.     s[len].e=y;
    49.     s[len].val=z;
    50.     nex[len]=f[x];
    51.     f[x]=len;
    52.     len++;
    53. }
    54.  
    55. int dep[101010];
    56. queue<int>q;
    57.  
    58. bool bfs()
    59. {
    60.     memset(dep,0,sizeof(dep));
    61.  
    62.     while(!q.empty())
    63.         q.pop();
    64.  
    65.     q.push(st);
    66.  
    67.     dep[st]=1;
    68.  
    69.     while(!q.empty())
    70.     {
    71.         int now=q.front();
    72.  
    73.         q.pop();
    74.         int x=f[now];
    75.  
    76.         while(x!=-1)
    77.         {
    78.             int j=s[x].e;
    79.  
    80.             if(s[x].val&&!dep[j])
    81.             {
    82.                 dep[j]=dep[now]+1;
    83.  
    84.                 q.push(j);
    85.             }
    86.  
    87.             x=nex[x];
    88.         }
    89.  
    90.     }
    91.  
    92.     return dep[ed];
    93. }
    94.  
    95. ll dfs(int now,ll flow)
    96. {
    97.     if(now==ed)
    98.         return flow;
    99.  
    100.     ll out=0;
    101.  
    102.     int x=f[now];
    103.  
    104.     while(x!=-1)
    105.     {
    106.         int j=s[x].e;
    107.  
    108.         if(dep[j]==dep[now]+1&&s[x].val)
    109.         {
    110.             ll res=dfs(j,min(flow,s[x].val));
    111.  
    112.             s[x].val-=res;
    113.  
    114.             s[x^1].val+=res;
    115.  
    116.             flow-=res;
    117.  
    118.             out+=res;
    119.         }
    120.  
    121.         x=nex[x];
    122.     }
    123.  
    124.     if(!out)
    125.         dep[now]=0;
    126.  
    127.     return out;
    128.  
    129. }
    130. int main()
    131. {
    132.  
    133.  
    134.     memset(f,-1,sizeof(f));
    135.  
    136.     cin>>n>>m>>sum;
    137.  
    138.     for(int i=0; i<=n+1; i++)
    139.     {
    140.         fa[i]=i;
    141.     }
    142.  
    143.     ed=10100;
    144.  
    145.     st=0;
    146.  
    147.     for(int i=1; i<=m; i++)
    148.     {
    149.         cin>>ren[i];
    150.  
    151.         int t;
    152.         cin>>t;
    153.         while(t--)
    154.         {
    155.             int x;
    156.             cin>>x;
    157.  
    158.             if(x==-1)
    159.                 x=n+1;
    160.             if(x==0)
    161.                 x=n+2;
    162.  
    163.             zhou[i].push_back(x);
    164.  
    165.         }
    166.  
    167.  
    168.     }
    169.  
    170.     int now=0;
    171.  
    172.     ll ans=0;
    173.     while(now<=500)
    174.     {
    175.  
    176.     if(now==0)
    177.         {
    178.             add(st,n+2+now*(n+2),sum);
    179.  
    180.         add(n+2+now*(n+2),st,0);
    181.         }
    182.  
    183.         add(n+1+now*(n+2),ed,inf);
    184.  
    185.         add(ed,n+1+now*(n+2),0);
    186.  
    187.         while(bfs())
    188.         {
    189.             ans+=dfs(st,1e18);
    190.  
    191.         }
    192.  
    193.         if(ans>=sum)
    194.         {
    195.             cout<
    196.  
    197.             return 0;
    198.         }
    199.  
    200.  
    201.         for(int i=1; i<=n+2; i++)
    202.         {
    203.             add(i+now*(n+2),i+(now+1)*(n+2),inf);
    204.  
    205.             add(i+(now+1)*(n+2),i+now*(n+2),0);
    206.  
    207.         }
    208.  
    209.         now++;
    210.  
    211.         for(int i=1; i<=m; i++)
    212.         {
    213.             int now1=now%zhou[i].size();
    214.  
    215.             int pre1=(now1-1+zhou[i].size())%zhou[i].size();
    216.  
    217.             now1=zhou[i][now1];
    218.  
    219.             pre1=zhou[i][pre1];
    220.  
    221.             add((n+2)*(now-1)+pre1,(n+2)*(now)+now1,ren[i]);
    222.  
    223.             add((n+2)*(now)+now1,(n+2)*(now-1)+pre1,0);
    224.         }
    225.  
    226.  
    227.     }
    228.  
    229.  
    230.     cout<<0;
    231.  
    232.  
    233.     return 0;
    234. }

    并查集思想 

    1149 -- PIGS

    网上的建图几乎是一模一样，省略掉了人，比较抽象，我这里建立了更好于理解的图，也就是猪圈与人共存的方式。注意，打开就是合并，之前打开了1,2，一万年之后打开2,3也是合并，123之间可以任意调度

    建图要点

    一， 第一次出现的猪开辟新的集合，出现在同一个客户，且是第一次出现的猪进行合并，如下图一号人打开了1,2猪圈，1,2猪圈第一次被打开，那么合并，并且合并权值

    二，已经被打开的猪，通过之前的标记找到第一次出现的位置，并向人连边

    三，inf表示各个猪圈，猪圈与人之间可以任意调度，limit与val已经严格保证了合理性，故无需在意

    下图样例

    一号人 1 2

    二号人物 3

    三号人物 1 2 4

    1. #include
    2. # include
    3. # include
    4. using namespace std;
    5.  
    6. typedef long long int ll;
    7.  
    8. typedef struct
    9. {
    10.     int b,e;
    11.     ll val;
    12. } xinxi;
    13. xinxi s[101010];
    14. int f[101010],nex[101010],len=2;
    15. ll inf=1e18;
    16. void add(int x,int y,ll z)
    17. {
    18.     s[len].b=x;
    19.     s[len].e=y;
    20.     s[len].val=z;
    21.  
    22.     nex[len]=f[x];
    23.     f[x]=len;
    24.     len++;
    25. }
    26. int book[1010], n,m,st,ed,val[1010],a[1010],last[1010],dep[1010];
    27. queue<int>q;
    28. bool bfs()
    29. {
    30.     memset(dep,0,sizeof(dep));
    31.  
    32.     while(!q.empty())
    33.         q.pop();
    34.  
    35.     dep[st]=1;
    36.  
    37.     q.push(st);
    38.  
    39.     while(!q.empty())
    40.     {
    41.         int now=q.front();
    42.  
    43.         q.pop();
    44.  
    45.         int x=f[now];
    46.  
    47.         while(x!=-1)
    48.         {
    49.             int j=s[x].e;
    50.  
    51.             if(s[x].val&&!dep[j])
    52.             {
    53.                 dep[j]=dep[now]+1;
    54.  
    55.                 q.push(j);
    56.             }
    57.             x=nex[x];
    58.         }
    59.  
    60.     }
    61.  
    62.     return dep[ed];
    63. }
    64.  
    65. ll dfs(int now, ll flow)
    66. {
    67.  
    68.     if(now==ed)
    69.         return flow;
    70.  
    71.     ll out=0;
    72.  
    73.     int x=f[now];
    74.  
    75.     while(x!=-1)
    76.     {
    77.         int j=s[x].e;
    78.  
    79.         if(s[x].val&&dep[j]==dep[now]+1)
    80.         {
    81.             ll res=dfs(j,min(flow,s[x].val));
    82.  
    83.             s[x].val-=res;
    84.  
    85.             s[x^1].val+=res;
    86.  
    87.             flow-=res;
    88.  
    89.             out+=res;
    90.         }
    91.         if(!flow)
    92.             break;
    93.         x=nex[x];
    94.     }
    95.  
    96.     if(!out)
    97.         dep[now]=0;
    98.  
    99.     return out;
    100. }
    101. int main()
    102. {
    103.  
    104.     cin>>m>>n;
    105.  
    106.     memset(f,-1,sizeof(f));
    107.  
    108.     for(int i=1; i<=m; i++)
    109.     {
    110.         cin>>a[i];
    111.     }
    112.  
    113.     ed=n+1;
    114.     int cnt=ed;
    115.  
    116.     for(int i=1; i<=n; i++)
    117.     {
    118.         int t;
    119.         cin>>t;
    120.  
    121.         cnt++;
    122.         int flag=0;
    123.         while(t--)
    124.         {
    125.             int x;
    126.             cin>>x;
    127.  
    128.  
    129.             if(!book[x])
    130.             {
    131.                 book[x]=1;
    132.                 val[cnt]+=a[x];
    133.                 last[x]=cnt;
    134.                 flag=1;
    135.             }
    136.             else
    137.             {
    138.  
    139.                 add(last[x],i,inf);
    140.  
    141.                 add(i,last[x],0);
    142.                 //last[x]=i;
    143.             }
    144.         }
    145.  
    146.         ll z;
    147.         cin>>z;
    148.         if(flag)
    149.         {
    150.             add(cnt,i,inf);
    151.             add(i,cnt,0);
    152.             add(st,cnt,val[cnt]);
    153.             add(cnt,st,0);
    154.         }
    155.         add(i,ed,z);
    156.         add(ed,i,0);
    157.     }
    158.  
    159.  
    160.  
    161.     ll ans=0;
    162.  
    163.     while(bfs())
    164.     {
    165.         ans+=dfs(st,1e18);
    166.  
    167.         //cout<
    168.     }
    169.  
    170.     cout<
    171.     return 0;
    172. }

    其他例题 

    [CQOI2014]危桥 - 洛谷

     首先最可能想到如下建图方式

     即针对经历次数设置流量，判断是否满流

    但细究起来，是非常不正确的。最大流，一切以使得T获得最大流量为宗旨，一旦我们为了最大流，而使得原来正确的路线跑偏，便错误了

    例如上图，完全有一种情况是，b1-a2 a1-b2能够跑出最大流，而这完全违背了题目要求

    考虑下图构图，即将a1 a2交换位置，两次都能跑出最大流就能判断是否可能 

    1. #include
    2. # include
    3. # include
    4. using namespace std;
    5.  
    6. typedef long long int ll;
    7.  
    8. int n,st1,ed1,st2,ed2,st,ed;
    9. typedef struct
    10. {
    11.     int b,e;
    12.     ll val;
    13. } xinxi;
    14. xinxi s[101010];
    15. int f[101010],nex[101010],len=2;
    16.  
    17. void add(int x,int y,ll z)
    18. {
    19.     s[len].b=x;
    20.     s[len].e=y;
    21.     s[len].val=z;
    22.     nex[len]=f[x];
    23.     f[x]=len;
    24.     len++;
    25. }
    26.  
    27. queue<int>q;
    28. int dep[1010];
    29. ll inf=1e18;
    30.  
    31. bool bfs()
    32. {
    33.     memset(dep,0,sizeof(dep));
    34.  
    35.     while(!q.empty())
    36.         q.pop();
    37.  
    38.     q.push(st);
    39.     dep[st]=1;
    40.  
    41.     while(!q.empty())
    42.     {
    43.         int now=q.front();
    44.         q.pop();
    45.  
    46.         int x=f[now];
    47.  
    48.         while(x!=-1)
    49.         {
    50.             int j=s[x].e;
    51.  
    52.             if(s[x].val&&!dep[j])
    53.             {
    54.                 dep[j]=dep[now]+1;
    55.                 q.push(j);
    56.             }
    57.  
    58.             x=nex[x];
    59.         }
    60.     }
    61.  
    62.     return dep[ed];
    63. }
    64.  
    65.  
    66. ll dfs(int now,ll flow)
    67. {
    68.     if(now==ed)
    69.         return flow;
    70.  
    71.     ll out=0;
    72.     int x=f[now];
    73.     while(x!=-1)
    74.     {
    75.         int j=s[x].e;
    76.         if(s[x].val&&dep[j]==dep[now]+1)
    77.         {
    78.             ll res=dfs(j,min(flow,s[x].val));
    79.  
    80.             s[x].val-=res;
    81.             s[x^1].val+=res;
    82.             flow-=res;
    83.             out+=res;
    84.         }
    85.         x=nex[x];
    86.     }
    87.  
    88.     if(!out)
    89.         dep[now]=0;
    90.     return out;
    91. }
    92.  
    93. char ch[100][100];
    94. int main()
    95. {
    96.  
    97.  
    98.  
    99.     int cnt1,cnt2;
    100.     while(cin>>n>>st1>>ed1>>cnt1>>st2>>ed2>>cnt2)
    101.     {
    102.  
    103.         st1++;
    104.         ed1++;
    105.         st2++;
    106.         ed2++;
    107.         st=0;
    108.         ed=n+1;
    109.         len=2;
    110.  
    111.         cnt1*=2;
    112.         cnt2*=2;
    113.  
    114.         memset(f,-1,sizeof(f));
    115.         memset(nex,0,sizeof(nex));
    116.         for(int i=1; i<=n; i++)
    117.         {
    118.             for(int j=1; j<=n; j++)
    119.             {
    120.  
    121.                 cin>>ch[i][j];
    122.  
    123.                 if(ch[i][j]=='N')
    124.                 {
    125.                     add(i,j,inf);
    126.  
    127.                     add(j,i,0);
    128.                 }
    129.                 else if(ch[i][j]=='O')
    130.                 {
    131.                     add(i,j,2);
    132.  
    133.                     add(j,i,0);
    134.                 }
    135.             }
    136.         }
    137.  
    138.  
    139.         add(st,st1,cnt1);
    140.         add(st1,st,0);
    141.         add(st,st2,cnt2);
    142.         add(st2,st,0);
    143.  
    144.         add(ed2,ed,cnt2);
    145.         add(ed,ed2,0);
    146.  
    147.         add(ed1,ed,cnt1);
    148.         add(ed,ed1,0);
    149.  
    150.  
    151.         ll ans1=0;
    152.         while(bfs())
    153.         {
    154.             ans1+=dfs(st,1e18);
    155.  
    156.  
    157.         }
    158.  
    159.         if(ans1!=cnt1+cnt2)
    160.         {
    161.             cout<<"No"<
    162.  
    163.             continue;
    164.         }
    165.  
    166.         st=0;
    167.         ed=n+1;
    168.         len=2;
    169.         memset(f,-1,sizeof(f));
    170.         memset(nex,0,sizeof(nex));
    171.  
    172.  
    173.         for(int i=1; i<=n; i++)
    174.         {
    175.             for(int j=1; j<=n; j++)
    176.             {
    177.  
    178.                 if(ch[i][j]=='N')
    179.                 {
    180.                     add(i,j,inf);
    181.  
    182.                     add(j,i,0);
    183.                 }
    184.                 else if(ch[i][j]=='O')
    185.                 {
    186.                     add(i,j,2);
    187.  
    188.                     add(j,i,0);
    189.                 }
    190.             }
    191.         }
    192.  
    193.  
    194.         swap(ed2,st2);
    195.         add(st,st1,cnt1);
    196.         add(st1,st,0);
    197.         add(st,st2,cnt2);
    198.         add(st2,st,0);
    199.  
    200.         add(ed2,ed,cnt2);
    201.         add(ed,ed2,0);
    202.  
    203.         add(ed1,ed,cnt1);
    204.         add(ed,ed1,0);
    205.  
    206.         ll ans2=0;
    207.  
    208.         while(bfs())
    209.         {
    210.             ans2+=dfs(st,1e18);
    211.         }
    212.  
    213.  
    214.  
    215.         if(ans1==ans2)
    216.         {
    217.             cout<<"Yes"<
    218.         }
    219.         else
    220.         {
    221.             cout<<"No"<
    222.         }
    223.  
    224.     }
    225.  
    226.  
    227.     return 0;
    228. }

    黑白染色 

    [SCOI2012]奇怪的游戏 - 洛谷

     黑白染色之后，分成左右集，黑点改变，可以向上下左右四个方向的白点进行增加

    当点数为偶数个的时候，黑点与白点个数相同，二分答案求解，得出的最大值的最小值，答案为左集或者右集流量（流满是前提）

    当点数为奇数个的时候，黑点与白点个数不同，但一个黑点改变若干次必定有若干白点改变相同次数，即黑点与白点的改变次数是相同的，有以下方程

    cnt白*max-sum 白= cnt黑*max-sum 黑 

    (cnt白-cnt黑）max=sum白-sum黑

    max= （sum白-sum黑 ）/（cnt白-cnt黑）

    最终答案就是方程左边或者右边的值

    1. #include
    2. # include
    3. # include
    4. using namespace std;
    5.  
    6. typedef long long int  ll;
    7.  
    8. ll a[100][100],ji,ou,sumji,sumou,cnt,st,ed,inf=1e18;
    9. int n,m;
    10. int id[100][100];
    11.  
    12. typedef struct
    13. {
    14.     int b,e;
    15.     ll val;
    16. } xinxi;
    17. xinxi s[10000];
    18. int f[10000],nex[10000],len=2;
    19. int nx[4]= {0,0,-1,1};
    20. int ny[4]= {1,-1,0,0};
    21.  
    22.  
    23. void add(int x,int y,ll z)
    24. {
    25.     s[len].b=x;
    26.     s[len].e=y;
    27.     s[len].val=z;
    28.     nex[len]=f[x];
    29.     f[x]=len;
    30.     len++;
    31. }
    32. int dep[2020];
    33. queue<int>q;
    34.  
    35. bool bfs()
    36. {
    37.     memset(dep,0,sizeof(dep));
    38.  
    39.     while(!q.empty())
    40.         q.pop();
    41.  
    42.     dep[st]=1;
    43.     q.push(st);
    44.  
    45.     while(!q.empty())
    46.     {
    47.         int now=q.front();
    48.         q.pop();
    49.         int x=f[now];
    50.  
    51.         while(x!=-1)
    52.         {
    53.             int j=s[x].e;
    54.  
    55.             if(s[x].val&&!dep[j])
    56.             {
    57.                 dep[j]=dep[now]+1;
    58.                 q.push(j);
    59.             }
    60.  
    61.  
    62.             x=nex[x];
    63.         }
    64.     }
    65.  
    66.     return dep[ed];
    67. }
    68.  
    69. ll dfs(int now, ll flow)
    70. {
    71.     if(now==ed)
    72.         return flow;
    73.  
    74.     ll out=0;
    75.     int x=f[now];
    76.  
    77.     while(x!=-1)
    78.     {
    79.         int j=s[x].e;
    80.  
    81.         if(dep[j]==dep[now]+1&&s[x].val)
    82.         {
    83.             ll res=dfs(j,min(flow,s[x].val));
    84.  
    85.             s[x].val-=res;
    86.  
    87.             s[x^1].val+=res;
    88.  
    89.             flow-=res;
    90.  
    91.             out+=res;
    92.         }
    93.  
    94.         if(flow==0)
    95.             break;
    96.         x=nex[x];
    97.     }
    98.     if(!out)
    99.         dep[now]=0;
    100.     return out;
    101. }
    102. bool check(ll x)
    103. {
    104.     len=2;
    105.     memset(f,-1,sizeof(f));
    106.     memset(nex,0,sizeof(nex));
    107.  
    108.     for(int i=1; i<=n; i++)
    109.     {
    110.         for(int j=1; j<=m; j++)
    111.         {
    112.  
    113.             if(x
    114.                 return 0;
    115.  
    116.  
    117.             if((i+j)%2)
    118.             {
    119.                 add(st,id[i][j],x-a[i][j]);
    120.  
    121.                 add(id[i][j],st,0);
    122.             }
    123.             else
    124.             {
    125.                 add(id[i][j],ed,x-a[i][j]);
    126.  
    127.                 add(ed,id[i][j],0);
    128.             }
    129.         }
    130.     }
    131.  
    132.  
    133.     for(int i=1; i<=n; i++)
    134.     {
    135.         for(int j=1; j<=m; j++)
    136.         {
    137.             if((i+j)%2)
    138.             {
    139.                 for(int k=0; k<4; k++)
    140.                 {
    141.                     int xx=i+nx[k];
    142.  
    143.                     int yy=j+ny[k];
    144.  
    145.                     if(xx<1||xx>n||yy<1||yy>m)
    146.                         continue;
    147.  
    148.                     add(id[i][j],id[xx][yy],inf);
    149.  
    150.                     add(id[xx][yy],id[i][j],0);
    151.                 }
    152.             }
    153.         }
    154.     }
    155.  
    156.  
    157.    ll ans=0;
    158.     while(bfs())
    159.     {
    160.         ans+=dfs(st,1e18);
    161.     }
    162.  
    163.     return ans==x*ou-sumou;
    164.  
    165. }
    166. int main()
    167. {
    168.  
    169. //先对每个点进行序号标记
    170. //再统计白色点，黑色点的个数，和
    171. //求出x
    172. //如果是奇数，那么对这个x进行检测
    173. //建边白色点建立超级原点到该节点的mx-a[i][j]
    174. //否则建立 到超级汇点的
    175. //随后是，白色点对黑色点的单向边
    176. //最后进行检测，要求出完全等于入
    177.  
    178.     int t;
    179.     cin>>t;
    180.  
    181.     while(t--)
    182.     {
    183.  
    184.         cin>>n>>m;
    185.         ji=0;
    186.         ou=0;
    187.         sumji=0;
    188.         sumou=0;
    189.         cnt=0;
    190.  
    191.         st=0;
    192.         ed=n*m+1;
    193.  
    194.         for(int i=1; i<=n; i++)
    195.         {
    196.             for(int j=1; j<=m; j++)
    197.             {
    198.                 cnt++;
    199.                 id[i][j]=cnt;
    200.             }
    201.         }
    202.  
    203.         for(int i=1; i<=n; i++)
    204.         {
    205.             for(int j=1; j<=m; j++)
    206.             {
    207.                 cin>>a[i][j];
    208.  
    209.                 if((i+j)%2)
    210.                 {
    211.                     ji++;
    212.                     sumji+=a[i][j];
    213.                 }
    214.                 else
    215.                 {
    216.                     ou++;
    217.                     sumou+=a[i][j];
    218.                 }
    219.             }
    220.         }
    221.  
    222.         if((n*m)%2)
    223.         {
    224.             ll x=(sumji-sumou)/(ji-ou);
    225.  
    226.  
    227.             if((sumji-sumou)%(ji-ou)||!check(x))
    228.             {
    229.                 cout<<-1<
    230.  
    231.             }
    232.             else
    233.             {
    234.                 cout<
    235.             }
    236.         }
    237.         else
    238.         {
    239.             ll l=1,r=2e9;
    240.  
    241.             for(int i=1; i<=n; i++)
    242.             {
    243.                 for(int j=1; j<=m; j++)
    244.                 {
    245.                     l=max(l,a[i][j]);
    246.                 }
    247.             }
    248.  
    249.             while(l<=r)
    250.             {
    251.                 ll mid=(l+r)>>1;
    252.  
    253.                 if(check(mid))
    254.                     r=mid-1;
    255.                 else
    256.                     l=mid+1;
    257.             }
    258.  
    259.  
    260.           cout<
    261.         }
    262.     }
    263.     return 0;
    264. }

    最小割问题

    所谓最小割，是针对左右集与S,T的分属关系，将左右集全部点分割成两个集合，使得全部点分属于两个集合，两个集合不连通的最小代价，最小割等于最大流

    如下图，可以通过割取val1来实现1点脱离S集合，划归T集合，也可以通过val2,val3的割取来实现2,3点脱离T集合，划归S集合

     

    例题 

    方格取数问题 - 洛谷

     本题对方格进行黑白染色，按照上图进行连边，考虑上图，1,2,3点在本题中的实际意义，最终流到T的流量是val1与val2+val3的最小值，这也就是对边进行了割取，割取之和，1,2,3被划归到同一集合，我们消耗了min(val1,val2+val3)的代价，同一集合是没有边相连的，也就是我们删去了一种最小耗费的情况，体现了最小割的本质。即超级汇点一旦接受了val的流量，势必是一个点与其冲突的点之间做了取舍，完成了一次最小割

    1. #include
    2. # include
    3. # include
    4. using namespace std;
    5.  
    6. typedef long long int  ll;
    7.  
    8. ll a[100][100],ji,ou,sumji,sumou,cnt,st,ed,inf=1e18;
    9. int n,m;
    10.  
    11.  
    12. typedef struct
    13. {
    14.     int b,e;
    15.     ll val;
    16. } xinxi;
    17. xinxi s[10000];
    18. int f[10000],nex[10000],len=2;
    19. int nx[4]= {0,0,-1,1};
    20. int ny[4]= {1,-1,0,0};
    21.  
    22. void add(int x,int y,ll z)
    23. {
    24.     s[len].b=x;
    25.     s[len].e=y;
    26.     s[len].val=z;
    27.     nex[len]=f[x];
    28.     f[x]=len;
    29.     len++;
    30. }
    31. int dep[2020];
    32. queue<int>q;
    33. int id[110][110];
    34. bool bfs()
    35. {
    36.     memset(dep,0,sizeof(dep));
    37.  
    38.     while(!q.empty())
    39.         q.pop();
    40.  
    41.     dep[st]=1;
    42.     q.push(st);
    43.  
    44.     while(!q.empty())
    45.     {
    46.         int now=q.front();
    47.         q.pop();
    48.         int x=f[now];
    49.  
    50.         while(x!=-1)
    51.         {
    52.             int j=s[x].e;
    53.  
    54.             if(s[x].val&&!dep[j])
    55.             {
    56.                 dep[j]=dep[now]+1;
    57.                 q.push(j);
    58.             }
    59.  
    60.  
    61.             x=nex[x];
    62.         }
    63.     }
    64.  
    65.     return dep[ed];
    66. }
    67.  
    68. ll dfs(int now, ll flow)
    69. {
    70.     if(now==ed)
    71.         return flow;
    72.  
    73.     ll out=0;
    74.     int x=f[now];
    75.  
    76.     while(x!=-1)
    77.     {
    78.         int j=s[x].e;
    79.  
    80.         if(dep[j]==dep[now]+1&&s[x].val)
    81.         {
    82.             ll res=dfs(j,min(flow,s[x].val));
    83.  
    84.             s[x].val-=res;
    85.  
    86.             s[x^1].val+=res;
    87.  
    88.             flow-=res;
    89.  
    90.             out+=res;
    91.         }
    92.  
    93.         if(flow==0)
    94.             break;
    95.         x=nex[x];
    96.     }
    97.     if(!out)
    98.         dep[now]=0;
    99.     return out;
    100. }
    101.  
    102. int main()
    103. {
    104.  
    105.  int n,m;
    106.  cin>>n>>m;
    107.  memset(f,-1,sizeof(f));
    108.  ll ans=0;
    109.  for(int i=1;i<=n;i++)
    110.  {
    111.      for(int j=1;j<=m;j++)
    112.      {
    113.          cin>>a[i][j];
    114.          id[i][j]=(i-1)*m+j;
    115.          ans+=a[i][j];
    116.      }
    117.  }
    118.  
    119.  st=0;
    120.  ed=n*m+1;
    121.  
    122.  for(int i=1;i<=n;i++)
    123.  {
    124.      for(int j=1;j<=m;j++)
    125.      {
    126.          if((i+j)%2)
    127.          {
    128.              add(st,id[i][j],a[i][j]);
    129.              add(id[i][j],st,0);
    130.  
    131.              if(id[i-1][j])
    132.              {
    133.                  add(id[i][j],id[i-1][j],inf);
    134.                  add(id[i-1][j],id[i][j],0);
    135.              }
    136.  
    137.              if(id[i+1][j])
    138.              {
    139.  
    140.                  add(id[i][j],id[i+1][j],inf);
    141.                  add(id[i+1][j],id[i][j],0);
    142.              }
    143.              if(id[i][j-1])
    144.              {
    145.                    add(id[i][j],id[i][j-1],inf);
    146.                  add(id[i][j-1],id[i][j],0);
    147.              }
    148.  
    149.              if(id[i][j+1])
    150.              {
    151.                   add(id[i][j],id[i][j+1],inf);
    152.                  add(id[i][j+1],id[i][j],0);
    153.              }
    154.          }
    155.          else
    156.          {
    157.                add(id[i][j],ed,a[i][j]);
    158.              add(ed,id[i][j],0);
    159.          }
    160.      }
    161.  }
    162.  
    163.  while(bfs())
    164.  {
    165.      ans-=dfs(st,inf);
    166.  }
    167.  
    168.  cout<
    169.  
    170.  
    171.  
    172.     return 0;
    173. }

    最小割 

    [JSOI2016]反质数序列 - 洛谷

     仍旧是类似套路，所谓选择的点数两两之和不是质数，且长度最长，其实就是删除最少的点，使得剩下的是两两没有边相连的，只不过这里我们每个点的代价是1。跑一个最大流，求出来最小割就OK了。值得注意的是，偶数集完全可以做到两两之间合不是质数，但是奇数集里面的1与1是无法做到的，而我们注意到其实1只需要选择一个就行了，故可以对原数据进行修改，全部的1当成一个1就行

    1.  
    2. #include
    3. using namespace std;
    4.  
    5. typedef long long int ll;
    6.  
    7. bool not_prime[200000+10];
    8. int prime[200000+10],tot;
    9.  
    10. void init()
    11. {
    12.     for(int i=2; i<=200000; i++)
    13.     {
    14.         if(!not_prime[i])
    15.         {
    16.             tot++;
    17.             prime[tot]=i;
    18.         }
    19.         for(int j=1; j<=tot&&i*prime[j]<=200000; j++)
    20.         {
    21.             not_prime[i*prime[j]]=1;
    22.  
    23.             if(i%prime[j]==0)
    24.                 break;
    25.         }
    26.     }
    27. }
    28. int st,ed,n;
    29. typedef struct
    30. {
    31.     int b,e;
    32.     ll val;
    33. } xinxi;
    34. xinxi s[5010100];
    35. int f[5010100],nex[5010100],len=2;
    36. ll inf=1e18;
    37. void add(int x,int y,ll z)
    38. {
    39.     s[len].b=x;
    40.     s[len].e=y;
    41.     s[len].val=z;
    42.     nex[len]=f[x];
    43.     f[x]=len;
    44.     len++;
    45. }
    46.  
    47. queue<int>q;
    48. int dep[5000];
    49. bool bfs()
    50. {
    51.     memset(dep,0,sizeof(dep));
    52.     while(!q.empty())
    53.         q.pop();
    54.  
    55.     dep[st]=1;
    56.     q.push(st);
    57.  
    58.     while(!q.empty())
    59.     {
    60.         int now=q.front();
    61.         q.pop();
    62.         int x=f[now];
    63.         while(x!=-1)
    64.         {
    65.             int j=s[x].e;
    66.             if(s[x].val&&!dep[j])
    67.             {
    68.                 dep[j]=dep[now]+1;
    69.  
    70.                 q.push(j);
    71.             }
    72.             x=nex[x];
    73.         }
    74.     }
    75.     return dep[ed];
    76. }
    77.  
    78. ll dfs(int now,ll flow)
    79. {
    80.     if(ed==now)
    81.         return flow;
    82.  
    83.     ll out=0;
    84.     int x=f[now];
    85.     while(x!=-1)
    86.     {
    87.         int j=s[x].e;
    88.  
    89.         if(s[x].val&&dep[j]==dep[now]+1)
    90.         {
    91.             ll res=dfs(j,min(flow,s[x].val));
    92.  
    93.             s[x].val-=res;
    94.             s[x^1].val+=res;
    95.             flow-=res;
    96.             out+=res;
    97.         }
    98.         if(flow==0)
    99.             break;
    100.         x=nex[x];
    101.     }
    102.     if(!out)
    103.         dep[now]=0;
    104.     return out;
    105. }
    106.  
    107. int L[5000],R[5000],a[5000];
    108. int main()
    109. {
    110.     init();
    111.  
    112.  
    113.     memset(f,-1,sizeof(f));
    114.     int flag=0;
    115.     int len1=0,len2=0;
    116.  
    117.     cin>>n;
    118.     ed=n+1;
    119.     int cnt=0;
    120.  
    121.     for(int i=1; i<=n; i++)
    122.     {
    123.         int x;
    124.         cin>>x;
    125.  
    126.         a[i]=x;
    127.         
    128.         if(x==1&&flag==0)
    129.         {
    130.             flag=1;
    131.             len1++;
    132.             
    133.             L[len1]=i;
    134.             cnt++;
    135.             continue;
    136.         }
    137.         else if(x==1)
    138.             {
    139.                 cnt++;
    140.                 continue;
    141.             }
    142.  
    143.         if(x%2==1)
    144.         {
    145.             len1++;
    146.             L[len1]=i;
    147.         }
    148.         else
    149.         {
    150.             len2++;
    151.             R[len2]=i;
    152.         }
    153.     }
    154.  
    155.     for(int i=1; i<=len1; i++)
    156.     {
    157.         add(st,L[i],1);
    158.         add(L[i],st,0);
    159.     }
    160.  
    161.     for(int i=1; i<=len2; i++)
    162.     {
    163.         add(R[i],ed,1);
    164.  
    165.         add(ed,R[i],0);
    166.     }
    167.  
    168.     for(int i=1; i<=len1; i++)
    169.     {
    170.         for(int j=1; j<=len2; j++)
    171.         {
    172.             if(!not_prime[a[L[i]]+a[R[j]]])
    173.             {
    174.                 add(L[i],R[j],inf);
    175.  
    176.                 add(R[j],L[i],0);
    177.             }
    178.         }
    179.     }
    180.  
    181.     ll ans=0;
    182.  
    183.     while(bfs())
    184.     {
    185.         ans+=dfs(st,1e18);
    186.  
    187.     }
    188.  
    189.     if(cnt)
    190.     cout<1-ans;
    191.     else
    192.         cout<
    193.  
    194.     return 0;
    195. }

    集内连边的最小割 

    [SHOI2007] 善意的投票 / [JLOI2010] 冠军调查 - 洛谷

    不难看出仍然是最小割的套路，左右两集分别进行超级源点与超级汇点的连边，按照是否同意午觉进行划分 。但本题的好朋友关系也存在与集内，即最小割也会存在通过割掉集内边来实现最小割的目的。特别注意朋友关系是双向的，我们平时建立的正副边虽然有两条，但确是单向作用，副边仅起到退流作用。

    1. # include
    2. using namespace std;
    3.  
    4. typedef long long int ll;
    5. int n,m, st,ed, book[1000],dep[1000];
    6. typedef struct
    7. {
    8.     int b,e;
    9.     ll val;
    10. } xinxi;
    11. xinxi s[1010100];
    12. int f[1010100],nex[1010100],len=2;
    13. void add(int x,int y,ll z)
    14. {
    15.     s[len].b=x;
    16.     s[len].e=y;
    17.     s[len].val=z;
    18.     nex[len]=f[x];
    19.     f[x]=len;
    20.     len++;
    21. }
    22.  
    23. queue<int>q;
    24. bool bfs()
    25. {
    26.     memset(dep,0,sizeof(dep));
    27.     while(!q.empty())
    28.         q.pop();
    29.     dep[st]=1;
    30.     q.push(st);
    31.  
    32.     while(!q.empty())
    33.     {
    34.         int now=q.front();
    35.         q.pop();
    36.         int x=f[now];
    37.         while(x!=-1)
    38.         {
    39.             int j=s[x].e;
    40.             if(s[x].val&&!dep[j])
    41.             {
    42.                 dep[j]=dep[now]+1;
    43.                 q.push(j);
    44.             }
    45.             x=nex[x];
    46.         }
    47.     }
    48.     return dep[ed];
    49. }
    50.  
    51. ll dfs(int now, ll flow)
    52. {
    53.     if(now==ed)
    54.         return flow;
    55.     ll out=0;
    56.     int x=f[now];
    57.     while(x!=-1)
    58.     {
    59.         int j=s[x].e;
    60.         if(s[x].val&&dep[j]==dep[now]+1)
    61.         {
    62.             ll res=dfs(j,min(flow,s[x].val));
    63.  
    64.             s[x].val-=res;
    65.             s[x^1].val+=res;
    66.             flow-=res;
    67.             out+=res;
    68.         }
    69.         if(flow==0)
    70.             break;
    71.         x=nex[x];
    72.     }
    73.     if(out==0)
    74.         dep[now]=0;
    75.     return out;
    76. }
    77. int main()
    78. {
    79.     cin>>n>>m;
    80.     ed=n+1;
    81.     memset(f,-1,sizeof(f));
    82.     for(int i=1; i<=n; i++)
    83.     {
    84.         cin>>book[i];
    85.         if(book[i])
    86.         {
    87.             add(st,i,1);
    88.             add(i,st,0);
    89.         }
    90.         else
    91.         {
    92.             add(i,ed,1);
    93.             add(ed,i,0);
    94.         }
    95.     }
    96.  
    97.     for(int i=1; i<=m; i++)
    98.     {
    99.         int x,y;
    100.         cin>>x>>y;
    101.         add(x,y,1);
    102.         add(y,x,0);
    103.  
    104.     }
    105.  
    106.     ll ans=0;
    107.  
    108.     while(bfs())
    109.     {
    110.         ans=dfs(st,1e18);
    111.     }
    112.     cout<
    113.  
    114.     return 0;
    115. }

    最大权闭合子图 

    [NOI2006] 最大获利 - 洛谷

    最大权闭合子图是最小割问题中的变形，常用套路与数据特点是，事件具有因果，事件具有正负收益 。

    连边方式为

    超级源点连接正权收益点，超级汇点连接负权收益点，结果事件连接条件事件

    正权集一般是结果，负权集一般是条件，图便有了实际意义，即耗费一定条件，获得一定收益结果

    最大权闭合子图在最小割时取得最优解

    1. # include 
    2. # include
    3. # include
    4.  
    5. using namespace std;
    6.  
    7. typedef long long int  ll;
    8.  
    9. int dep[101010*5];
    10. queue<int>q;
    11.  
    12. int st,ed,n,m;
    13. typedef struct
    14. {
    15.     int b,e;
    16.     ll val;
    17. }xinxi;
    18. xinxi s[101010*5];
    19. int f[101010*5],nex[101010*5],len=2;
    20.  
    21. ll inf=1e18;
    22.  
    23. bool bfs()
    24. {
    25.     memset(dep,0,sizeof(dep));
    26.  
    27.     while(!q.empty())
    28.         q.pop();
    29.  
    30.     dep[st]=1;
    31.     q.push(st);
    32.  
    33.     while(!q.empty())
    34.     {
    35.         int now=q.front();
    36.         q.pop();
    37.         int x=f[now];
    38.         while(x!=-1)
    39.         {
    40.             int j=s[x].e;
    41.  
    42.             if(s[x].val&&!dep[j])
    43.             {
    44.                 dep[j]=dep[now]+1;
    45.                 q.push(j);
    46.             }
    47.             x=nex[x];
    48.         }
    49.     }
    50.  
    51.     return dep[ed];
    52. }
    53.  
    54.  
    55. ll dfs(int now, ll flow)
    56. {
    57.     if(now==ed)
    58.         return flow;
    59.  
    60.     ll out=0;
    61.     int x=f[now];
    62.  
    63.     while(x!=-1)
    64.     {
    65.         int j=s[x].e;
    66.  
    67.         if(s[x].val&&dep[j]==dep[now]+1)
    68.         {
    69.             ll res=dfs(j,min(flow,s[x].val));
    70.  
    71.             s[x].val-=res;
    72.  
    73.             s[x^1].val+=res;
    74.  
    75.             flow-=res;
    76.  
    77.             out+=res;
    78.         }
    79.  
    80.         if(!flow)
    81.             break;
    82.         x=nex[x];
    83.  
    84.     }
    85.  
    86.     if(!out)
    87.         dep[now]=0;
    88.  
    89.     return out;
    90.  
    91. }
    92. void add(int x,int y,ll z)
    93. {
    94.     s[len].b=x;
    95.     s[len].e=y;
    96.     s[len].val=z;
    97.     nex[len]=f[x];
    98.     f[x]=len;
    99.     len++;
    100. }
    101.  
    102. ll val[101010];
    103. int x[101010],y[101010],z[101010];
    104.  
    105. int main()
    106. {
    107. //建造不同的中转站耗费是同的，一旦建立
    108. //具有该中转站的用户便可以进行通信，
    109. //进行通信便可以获利
    110. //最大权闭合图的构图方法
    111. //增加超级源点S 汇点 T
    112. //超级源点连接原图正权点，负权点连接汇点T
    113. //正权点总和减去对应割的容量
    114. //割最小时，闭合权最大
    115. //首先，用户是贡献收益的，正权边连接源点
    116. //编号是1-M个用户
    117. //然后用户连接中转站，边权是INF，
    118. //用户编号是M+1-M+N,
    119. //超级源点是0，超级汇点是M+N+1
    120.  
    121. cin>>n>>m;
    122. st=0;
    123. ed=m+n+1;
    124.  
    125. memset(f,-1,sizeof(f));
    126.  
    127.  
    128. for(int i=1;i<=n;i++)
    129. {
    130.     cin>>val[i];
    131. }
    132.  
    133. ll sum=0;
    134.  
    135. for(int i=1;i<=m;i++)
    136. {
    137.     cin>>x[i]>>y[i]>>z[i];
    138.  
    139.     sum+=z[i];
    140.  
    141. }
    142.  
    143. for(int i=1;i<=m;i++)
    144. {
    145.     add(st,i,z[i]);
    146.     add(i,st,0);
    147. }
    148.  
    149. for(int i=1;i<=m;i++)
    150. {
    151.     add(i,x[i]+m,inf);  //结果连接条件
    152.     add(x[i]+m,i,0);
    153.  
    154.     add(i,y[i]+m,inf);
    155.     add(y[i]+m,i,0);
    156. }
    157.  
    158. for(int i=1;i<=n;i++)
    159. {
    160.     add(i+m,ed,val[i]);
    161.  
    162.     add(ed,i+m,0);
    163. }
    164.  
    165. ll ans=0;
    166.  
    167. while(bfs())
    168. {
    169.     ans+=dfs(st,1e18);
    170. }
    171.  
    172.  
    173. cout<
    174.  
    175.  
    176.  
    177.    return 0;
    178. }

    最大权闭合子图 

    NC23832Magic Slab

     仍旧是有代价，有收益，有条件（行列生成点），故为最大权闭合子图的典型。考虑把点作为左集点获得收益，另外特殊奖励点需要另外开辟点，只不过连接的右集点变多。

    1. # include 
    2. # include
    3. # include
    4.  
    5. using namespace std;
    6.  
    7. typedef long long int  ll;
    8.  
    9. int n,m,st,ed;
    10. int a[100][100];
    11. int val1[100],val2[100];
    12. int hang[100],lie[100];
    13.  
    14.  
    15. typedef struct
    16. {
    17.     int b,e;
    18.     ll val;
    19. }xinxi;
    20. xinxi s[101010];
    21. int f[101010],nex[101010],len=2;
    22. ll inf=1e18;
    23. void add(int x,int y,ll z)
    24. {
    25.     s[len].b=x;
    26.     s[len].e=y;
    27.     s[len].val=z;
    28.     nex[len]=f[x];
    29.     f[x]=len;
    30.     len++;
    31. }
    32.  
    33. queue<int>q;
    34. int dep[101010];
    35. bool bfs()
    36. {
    37.     memset(dep,0,sizeof(dep));
    38.     while(!q.empty())
    39.         q.pop();
    40.     dep[st]=1;
    41.     q.push(st);
    42.  
    43.     while(!q.empty())
    44.     {
    45.         int now=q.front();
    46.         q.pop();
    47.         int x=f[now];
    48.         while(x!=-1)
    49.         {
    50.             int j=s[x].e;
    51.             if(s[x].val&&!dep[j])
    52.             {
    53.                 dep[j]=dep[now]+1;
    54.                 q.push(j);
    55.             }
    56.             x=nex[x];
    57.         }
    58.     }
    59.  
    60.     return dep[ed];
    61. }
    62.  
    63.  
    64. ll dfs(int now, ll flow)
    65. {
    66.     if(now==ed)
    67.         return flow;
    68.  
    69.     ll out=0;
    70.  
    71.     int x=f[now];
    72.     while(x!=-1)
    73.     {
    74.         int j=s[x].e;
    75.  
    76.         if(dep[j]==dep[now]+1&&s[x].val)
    77.         {
    78.             ll res=dfs(j,min(flow,s[x].val));
    79.             s[x].val-=res;
    80.             s[x^1].val+=res;
    81.             flow-=res;
    82.             out+=res;
    83.         }
    84.         if(!flow)
    85.             break;
    86.         x=nex[x];
    87.     }
    88.  
    89.     if(!out)
    90.         dep[now]=0;
    91.  
    92.     return out;
    93. }
    94. int main()
    95. {
    96.    //左集点编号是1-n*m
    97.    //右集点是1-n 的行 n+1 - n+m的列
    98.  
    99.    //超级汇点是 n*m+n+m+1
    100.    cin>>n>>m;
    101.  
    102.    memset(f,-1,sizeof(f));
    103.  
    104.    for(int i=1;i<=n;i++)
    105.    {
    106.        hang[i]=n*n+i;
    107.    }
    108.  
    109.    for(int i=1;i<=n;i++)
    110.    {
    111.        lie[i]=n*n+n+i;
    112.    }
    113.    ed=n*n+n+n+m+1;
    114.    ll sum=0;
    115.    for(int i=1;i<=n;i++)
    116.    {
    117.        for(int j=1;j<=n;j++)
    118.        {
    119.            cin>>a[i][j];
    120.            sum+=a[i][j];
    121.        }
    122.    }
    123.  
    124.    for(int i=1;i<=n;i++)
    125.    {
    126.        cin>>val1[i];
    127.    }
    128.  
    129.    for(int i=1;i<=n;i++)
    130.    {
    131.        cin>>val2[i];
    132.    }
    133.  
    134.    for(int i=1;i<=n;i++)
    135.    {
    136.        for(int j=1;j<=n;j++)
    137.        {
    138.            add(st,(i-1)*n+j,a[i][j]);
    139.            add((i-1)*n+j,st,0);
    140.        }
    141.    }
    142.  
    143.    for(int i=1;i<=n;i++)
    144.    {
    145.        for(int j=1;j<=n;j++)
    146.        {
    147.            add((i-1)*n+j,hang[i],inf);
    148.  
    149.            add(hang[i],(i-1)*n+j,0);
    150.  
    151.            add((i-1)*n+j,lie[j],inf);
    152.  
    153.            add(lie[j],(i-1)*n+j,0);
    154.        }
    155.    }
    156.  
    157.   for(int i=1;i<=n;i++)
    158.   {
    159.       add(hang[i],ed,val1[i]);
    160.  
    161.       add(ed,hang[i],0);
    162.   }
    163.  
    164.   for(int i=1;i<=n;i++)
    165.   {
    166.       add(lie[i],ed,val2[i]);
    167.       add(ed,lie[i],0);
    168.   }
    169.  
    170.   for(int i=1;i<=m;i++)
    171.   {
    172.       int now=n*n+n+n+i;
    173.       int x1,x2,x3,x4;
    174.       int c;
    175.       cin>>x1>>x2>>x3>>x4>>c;
    176.  
    177.       add(st,now,c);
    178.       add(now,st,0);
    179.  
    180.       add(now,hang[x1],inf);
    181.  
    182.       add(hang[x1],now,0);
    183.  
    184.       add(now,lie[x2],inf);
    185.  
    186.       add(lie[x2],now,0);
    187.  
    188.       add(now,hang[x3],inf);
    189.  
    190.       add(hang[x3],now,0);
    191.  
    192.       add(now,lie[x4],inf);
    193.  
    194.       add(lie[x4],now,0);
    195.  
    196.       sum+=c;
    197.  
    198.   }
    199.   ll ans=0;
    200.   while(bfs())
    201.   {
    202.       ans+=dfs(st,inf);
    203.   }
    204.  
    205.   cout<
    206.    return 0;
    207. }

    例题 

     Petya and Graph - 洛谷

    仍旧是最大权闭合子图的典型，点是条件，且本题是负权，边是结果，且本题是正权

     

    1. # include 
    2. # include
    3. # include
    4.  
    5. using namespace std;
    6.  
    7. typedef long long int  ll;
    8.  
    9.  
    10. int id[1010],n,m,val[1010],st,ed;
    11. ll inf=1e18;
    12. queue<int>q;
    13. int dep[101010];
    14. typedef struct
    15. {
    16.     int b,e;
    17.     ll val;
    18. }xinxi;
    19. xinxi s[101010];
    20. int f[101010],nex[101010],len=2;
    21.  
    22. void add(int x,int y,ll z)
    23. {
    24.     s[len].b=x;
    25.     s[len].e=y;
    26.     s[len].val=z;
    27.     nex[len]=f[x];
    28.     f[x]=len;
    29.     len++;
    30. }
    31.  
    32. bool bfs()
    33. {
    34.     memset(dep,0,sizeof(dep));
    35.  
    36.     while(!q.empty())
    37.         q.pop();
    38.  
    39.     dep[st]=1;
    40.  
    41.     q.push(st);
    42.  
    43.     while(!q.empty())
    44.     {
    45.         int now=q.front();
    46.         q.pop();
    47.         int x=f[now];
    48.  
    49.         while(x!=-1)
    50.         {
    51.             int j=s[x].e;
    52.  
    53.             if(!dep[j]&&s[x].val)
    54.             {
    55.                 dep[j]=dep[now]+1;
    56.                 q.push(j);
    57.             }
    58.             x=nex[x];
    59.         }
    60.     }
    61.  
    62.     return dep[ed];
    63. }
    64.  
    65. ll dfs(int now, ll flow)
    66. {
    67.     if(now==ed)
    68.         return flow;
    69.  
    70.     ll out=0;
    71.     int x=f[now];
    72.     while(x!=-1)
    73.     {
    74.         int j=s[x].e;
    75.  
    76.         if(dep[j]==dep[now]+1&&s[x].val)
    77.         {
    78.             ll res=dfs(j,min(s[x].val,flow));
    79.  
    80.             s[x].val-=res;
    81.  
    82.             s[x^1].val+=res;
    83.  
    84.             flow-=res;
    85.  
    86.             out+=res;
    87.         }
    88.  
    89.         if(!flow)
    90.             break;
    91.  
    92.         x=nex[x];
    93.     }
    94.  
    95.     if(!out)
    96.         dep[now]=0;
    97.  
    98.     return out;
    99. }
    100. int main()
    101. {
    102.  
    103.  
    104.     memset(f,-1,sizeof(f));
    105.   //一条边的先决条件是两个点，而两个点是需要负权
    106.   //对m条边进行重新编号，对剩余n个点编号为m+i
    107.  
    108.   cin>>n>>m;ed=n+m+1;
    109.   for(int i=1;i<=n;i++)
    110.   {
    111.       cin>>val[i];
    112.  
    113.       id[i]=i+m;
    114.  
    115.       add(id[i],ed,val[i]);
    116.  
    117.       add(ed,id[i],0);
    118.   }
    119.   st=0;
    120.  
    121.   ll sum=0;
    122.   for(int i=1;i<=m;i++)
    123.   {
    124.       int x,y,z;
    125.       cin>>x>>y>>z;
    126.  
    127.       sum+=z;
    128.       add(st,i,z);
    129.       add(i,st,0);
    130.  
    131.       x=id[x];
    132.       y=id[y];
    133.  
    134.       add(i,x,inf);
    135.       add(x,i,0);
    136.       add(i,y,inf);
    137.       add(y,i,0);
    138.  
    139.  
    140.   }
    141.   ll ans=0;
    142.   while(bfs())
    143.   {
    144.       ans+=dfs(st,inf);
    145.   }
    146.  
    147.   
    148.  
    149.   cout<
    150.  
    151.    return 0;
    152. }

    最小割 

    1966 -- Cable TV Network

    本题考察最小割的本质，除了将左右集点完全划分为两个不相连边的集合之外，最小割的另一个本质是切掉最小的边，使得ST不再联通。

    本题并没有明确的超级源点与汇点，且本题是要求删去点，而非边。本题也没有明确的左集（具有左右集时直接进行删边）故本题需要枚举超级源点与汇点，并且需要拆点，超级源点与汇点是不能删去的，其余的边也是不能删去的，超级源点与汇点之外的点即正副点之间的删除才是有意义的。注意这里的连通性指的是删除点之后的连通性，所以我们单纯删掉一个点的思路是不正确的。

    1. # include 
    2. # include
    3. # include
    4.  
    5. using namespace std;
    6.  
    7. typedef long long int  ll;
    8.  
    9.  
    10. //最小割树
    11. int x[1000],y[1000];
    12. int n,m,st,ed;
    13.  
    14. typedef struct
    15. {
    16.     int b,e;
    17.     ll val;
    18. } xinxi;
    19. xinxi s[101010];
    20. int f[101010],nex[101010],len=2;
    21. void add(int x,int y,ll z)
    22. {
    23.     s[len].b=x;
    24.     s[len].e=y;
    25.     s[len].val=z;
    26.     nex[len]=f[x];
    27.     f[x]=len;
    28.     len++;
    29. }
    30. ll inf=1e18;
    31.  
    32. queue<int>q;
    33. int dep[1010];
    34.  
    35. bool bfs()
    36. {
    37.     memset(dep,0,sizeof(dep));
    38.     while(!q.empty())
    39.         q.pop();
    40.     dep[st]=1;
    41.     q.push(st);
    42.  
    43.     while(!q.empty())
    44.     {
    45.         int now=q.front();
    46.         q.pop();
    47.         int x=f[now];
    48.         while(x!=-1)
    49.         {
    50.             int j=s[x].e;
    51.  
    52.             if(s[x].val&&!dep[j])
    53.             {
    54.                 dep[j]=dep[now]+1;
    55.                 q.push(j);
    56.             }
    57.             x=nex[x];
    58.         }
    59.     }
    60.  
    61.     return dep[ed];
    62. }
    63.  
    64. ll dfs(int now, ll flow)
    65. {
    66.     if(now==ed)
    67.         return flow;
    68.  
    69.     ll out=0;
    70.  
    71.     int x=f[now];
    72.  
    73.     while(x!=-1)
    74.     {
    75.         int j=s[x].e;
    76.  
    77.         if(dep[j]==dep[now]+1&&s[x].val)
    78.         {
    79.             ll res=dfs(j,min(flow,s[x].val));
    80.  
    81.             s[x].val-=res;
    82.  
    83.             s[x^1].val+=res;
    84.  
    85.             flow-=res;
    86.  
    87.             out+=res;
    88.         }
    89.  
    90.         if(flow==0)
    91.             break;
    92.         x=nex[x];
    93.     }
    94.  
    95.     if(out==0)
    96.         dep[now]=0;
    97.  
    98.     return out;
    99. }
    100. int main()
    101. {
    102.  
    103.  
    104.     while(cin>>n>>m)
    105.     {
    106.  
    107.  
    108.         for(int i=1; i<=m; i++)
    109.         {
    110.             scanf(" (%d,%d)",&x[i],&y[i]);
    111.  
    112.         }
    113.         ll ans=inf;
    114.  
    115.         for(int i=0; i
    116.         {
    117.             for(int j=0; j
    118.             {
    119.                 if(i==j)
    120.                     continue;
    121.  
    122.                 st=i;
    123.                 ed=j;
    124.  
    125.                 memset(f,-1,sizeof(f));
    126.                 len=2;
    127.                 memset(nex,0,sizeof(nex));
    128.  
    129.  
    130.  
    131.                 for(int k=0; k
    132.                 {
    133.                     if(k==st||k==ed)
    134.                     {
    135.                         add(k,k+n,inf);
    136.  
    137.                         add(k+n,k,0);
    138.                         continue;
    139.  
    140.                     }
    141.  
    142.                     add(k,k+n,1);
    143.  
    144.                     add(k+n,k,0);
    145.                 }
    146.                 for(int k=1; k<=m; k++)
    147.                 {
    148.                     add(x[k]+n,y[k],inf);
    149.  
    150.                     add(y[k],x[k]+n,0);
    151.  
    152.                     add(y[k]+n,x[k],inf);
    153.  
    154.                     add(x[k],y[k]+n,0);
    155.                 }
    156.  
    157.  
    158.                 ll temp=0;
    159.                 while(bfs())
    160.                 {
    161.                     temp+=dfs(st,inf);
    162.                 }
    163.  
    164.                 ans=min(ans,temp);
    165.             }
    166.         }
    167.  
    168.         if(n<=1||ans==inf)
    169.         cout<
    170.         else
    171.             cout<
    172.  
    173.     }
    174.  
    175.  
    176.     return 0;
    177. }

    最小割的 删除点操作

    NC238090Anti LIS

     本题建图套路就是按照大小顺序，位置顺序，dp值递增顺序建图。而本题考察的最小割知识点在于最小割的第二个本质也就是ST之间不再联通。

    首先观察，按照我们传统的建图方式跑出来的流量建立在ST联通的基础上，也就是路径长度为最长上升子序列长度。一旦我们在中间删除若干点（这里是拆点之后形成的边），ST联通路径上的全部路径都不再联通，那么我们就达成了降低最长上升子序列的目的，且跑最小割就是最小花费。

    1. # include 
    2. # include
    3. # include
    4.  
    5. using namespace std;
    6.  
    7. typedef long long int  ll;
    8.  
    9. int dp[1010];
    10. int a[1010];
    11. int n,st,ed;
    12. queue<int>q;
    13. int dep[20200];
    14. typedef struct
    15. {
    16.     int b,e;
    17.     ll val;
    18. }xinxi;
    19. xinxi s[1010100];
    20. int f[1010100],nex[1010100],len=2;
    21.  
    22. void add(int x,int y,ll z)
    23. {
    24.     s[len].b=x;
    25.     s[len].e=y;
    26.     s[len].val=z;
    27.     nex[len]=f[x];
    28.     f[x]=len;
    29.     len++;
    30. }
    31.  
    32. bool bfs()
    33. {
    34.     memset(dep,0,sizeof(dep));
    35.  
    36.     dep[st]=1;
    37.     while(!q.empty())
    38.         q.pop();
    39.     q.push(st);
    40.  
    41.     while(!q.empty())
    42.     {
    43.         int now=q.front();
    44.         q.pop();
    45.         int x=f[now];
    46.  
    47.         while(x!=-1)
    48.         {
    49.             int j=s[x].e;
    50.             if(s[x].val&&!dep[j])
    51.             {
    52.                 dep[j]=dep[now]+1;
    53.                 q.push(j);
    54.             }
    55.             x=nex[x];
    56.         }
    57.     }
    58.  
    59.     return dep[ed];
    60. }
    61.  
    62. ll dfs(int now, ll flow)
    63. {
    64.     if(ed==now)
    65.         return flow;
    66.     ll out=0;
    67.     int x=f[now];
    68.     while(x!=-1)
    69.     {
    70.         int j=s[x].e;
    71.         if(s[x].val&&dep[j]==dep[now]+1)
    72.         {
    73.             ll res=dfs(j,min(flow,s[x].val));
    74.  
    75.             s[x].val-=res;
    76.             s[x^1].val+=res;
    77.  
    78.             flow-=res;
    79.             out+=res;
    80.  
    81.         }
    82.         if(flow==0)
    83.             break;
    84.         x=nex[x];
    85.     }
    86.  
    87.     if(!out)
    88.         dep[now]=0;
    89.     return out;
    90.  
    91. }
    92.  
    93. ll inf=1e18;
    94. int main()
    95. {
    96.  
    97.  
    98.    int t;
    99.    cin>>t;
    100.    while(t--)
    101.    {
    102.        cin>>n;
    103.  
    104.        memset(f,-1,sizeof(f));
    105.        len=2;
    106.        memset(nex,0,sizeof(nex));
    107.  
    108.        for(int i=1;i<=n;i++)
    109.        {
    110.            cin>>a[i];
    111.            dp[i]=1;
    112.        }
    113.  
    114.        int maxx=0;
    115.        for(int i=1;i<=n;i++)
    116.        {
    117.            for(int j=1;j
    118.            {
    119.                if(a[i]>a[j])
    120.                dp[i]=max(dp[i],dp[j]+1);
    121.            }
    122.            maxx=max(maxx,dp[i]);
    123.        }
    124.  
    125.        st=0;
    126.        ed=2*n+1;
    127.  
    128.        for(int i=1;i<=n;i++)
    129.        {
    130.            if(dp[i]==1)
    131.            {
    132.                add(st,i,inf);
    133.                add(i,st,0);
    134.            }
    135.            else if(dp[i]==maxx)
    136.            {
    137.                add(i+n,ed,inf);
    138.                add(ed,i+n,0);
    139.            }
    140.  
    141.            add(i,i+n,1);
    142.            add(i+n,i,0);
    143.  
    144.            for(int j=1;j
    145.            {
    146.                if(a[i]>a[j]&&dp[i]==dp[j]+1)
    147.                {
    148.                    add(j+n,i,inf);
    149.  
    150.                    add(i,j+n,0);
    151.                }
    152.            }
    153.        }
    154.        ll ans=0;
    155.        while(bfs())
    156.        {
    157.            ans+=dfs(st,inf);
    158.        }
    159.  
    160.        cout<
    161.  
    162.    }
    163.  
    164.  
    165.     return 0;
    166. }

    费用流

    运输问题 - 洛谷

    费用流的入门题

    1. # include 
    2. # include
    3. # include
    4.  
    5. using namespace std;
    6.  
    7. typedef long long int  ll;
    8.  
    9. ll a[1010],b[1010],c[1010][1010],inf=1e18;
    10. int n,m,st,ed;
    11. typedef struct
    12. {
    13.     int b,e;
    14.     ll flow,dis;
    15. } xinxi;
    16. xinxi s[101010];
    17. int f[101010],nex[101010],len=2;
    18. void add(int x,int y, ll flow, ll dis)
    19. {
    20.     s[len].b=x;
    21.     s[len].e=y;
    22.     s[len].flow=flow;
    23.     s[len].dis=dis;
    24.     nex[len]=f[x];
    25.     f[x]=len;
    26.     len++;
    27. }
    28. queue<int>q;
    29. ll dis[1010],minn[1010],pre[1010];
    30. bool book[1010];
    31.  
    32. bool SPFA()
    33. {
    34.     for(int i=st; i<=ed; i++)
    35.     {
    36.         book[i]=0;
    37.         dis[i]=inf;
    38.     }
    39.     dis[st]=0;
    40.     book[st]=1;
    41.     q.push(st);
    42.     minn[st]=inf;
    43.     q.push(st);
    44.  
    45.     while(!q.empty())
    46.     {
    47.         int now=q.front();
    48.         q.pop();
    49.         book[now]=0;
    50.         int x=f[now];
    51.         while(x!=-1)
    52.         {
    53.             int j=s[x].e;
    54.             if(s[x].flow==0)
    55.             {
    56.                 x=nex[x];
    57.                 continue;
    58.             }
    59.             if(dis[j]>dis[now]+s[x].dis)
    60.             {
    61.                 dis[j]=dis[now]+s[x].dis;
    62.                 minn[j]=min(minn[now],s[x].flow);
    63.                 pre[j]=x;
    64.                 if(!book[j])
    65.                 {
    66.                     book[j]=1;
    67.                     q.push(j);
    68.                 }
    69.             }
    70.  
    71.             x=nex[x];
    72.         }
    73.     }
    74.  
    75.     return (dis[ed]!=inf);
    76. }
    77. ll maxflow,mindis;
    78. void work()
    79. {
    80.  
    81.  
    82.     while(SPFA())
    83.     {
    84.         int x=ed;
    85.  
    86.         maxflow+=minn[ed];
    87.         mindis+=minn[ed]*dis[ed];
    88.  
    89.         int i;
    90.  
    91.         while(x!=st)
    92.         {
    93.             i=pre[x];
    94.  
    95.             s[i].flow-=minn[ed];
    96.             s[i^1].flow+=minn[ed];
    97.             x=s[i^1].e;
    98.         }
    99.     }
    100. }
    101. int main()
    102. {
    103.  
    104.     memset(f,-1,sizeof(f));
    105.  
    106.     cin>>n>>m;
    107.  
    108.     for(int i=1; i<=n; i++)
    109.     {
    110.         cin>>a[i];
    111.  
    112.         add(st,i,a[i],0);
    113.         add(i,st,0,0);
    114.     }
    115.  
    116.     ed=n+m+1;
    117.  
    118.     for(int i=1; i<=m; i++)
    119.     {
    120.         cin>>b[i];
    121.  
    122.         add(i+n,ed,b[i],0);
    123.  
    124.         add(ed,i+n,0,0);
    125.     }
    126.     for(int i=1; i<=n; i++)
    127.     {
    128.         for(int j=1; j<=m; j++)
    129.         {
    130.             cin>>c[i][j];
    131.  
    132.             add(i,j+n,inf,c[i][j]);
    133.  
    134.             add(j+n,i,0,-c[i][j]);
    135.         }
    136.     }
    137.  
    138.     work();
    139.  
    140.     cout<
    141.  
    142.     ed=n+m+1;
    143.  
    144.     memset(f,-1,sizeof(f));
    145.     len=2;
    146.  
    147.     mindis=0;
    148.     for(int i=1; i<=n; i++)
    149.     {
    150.         add(st,i,a[i],0);
    151.         add(i,st,0,0);
    152.     }
    153.  
    154.     for(int i=1; i<=m; i++)
    155.     {
    156.  
    157.         add(i+n,ed,b[i],0);
    158.  
    159.         add(ed,i+n,0,0);
    160.     }
    161.     for(int i=1; i<=n; i++)
    162.     {
    163.         for(int j=1; j<=m; j++)
    164.         {
    165.  
    166.  
    167.             add(i,j+n,inf,-c[i][j]);
    168.  
    169.             add(j+n,i,0,c[i][j]);
    170.         }
    171.     }
    172.  
    173.     work();
    174.     cout<<-mindis<
    175.  
    176.  
    177.  
    178.     return 0;
    179. }

    航空路线问题 - 洛谷

    求从起点开始到终点再到起点的路径费用最小，起点与终点只经过两次，其余点经过一次，我们只需要拆点之后，起点与终点之间的边权设置为2，其余点设置为1即可。判断是否能够跑个来回，只需要判断流量是否是2.再此基础上，从起点跑一次残留网络到终点，再跑另一边即可。

    1. # include 
    2. # include
    3. # include
    4. # include
    5. using namespace std;
    6.  
    7. typedef long long int  ll;
    8.  
    9. int n,m,st,ed;
    10. mapint>mp;
    11. string city[1010];
    12.  
    13. typedef struct
    14. {
    15.     int b,e;
    16.     ll flow,dis;
    17. }xinxi;
    18. xinxi s[101010];
    19. int f[101010],nex[101010],len=2;
    20. void add(int x,int y,ll flow,ll dis)
    21. {
    22.     s[len].b=x;
    23.     s[len].e=y;
    24.     s[len].flow=flow;
    25.     s[len].dis=dis;
    26.  
    27.     nex[len]=f[x];
    28.     f[x]=len;
    29.     len++;
    30. }
    31. ll pre[1010],dis[1010],book[1010],minn[1010],inf=1e18;
    32. queue<int>q;
    33.  
    34. bool SPFA()
    35. {
    36.     for(int i=st;i<=ed;i++)
    37.     {
    38.         book[i]=0;
    39.         dis[i]=-inf;
    40.     }
    41.  
    42.     book[st]=1;
    43.     dis[st]=0;
    44.     minn[st]=inf;
    45.     q.push(st);
    46.  
    47.     while(!q.empty())
    48.     {
    49.         int now=q.front();
    50.         q.pop();
    51.         book[now]=0;
    52.  
    53.       //  cout<
    54.  
    55.         int x=f[now];
    56.  
    57.         while(x!=-1)
    58.         {
    59.             int j=s[x].e;
    60.             if(s[x].flow==0)
    61.             {
    62.                 x=nex[x];
    63.                 continue;
    64.             }
    65.             if(dis[j]
    66.             {
    67.                 dis[j]=dis[now]+s[x].dis;
    68.                 pre[j]=x;
    69.                 minn[j]=min(minn[now],s[x].flow);
    70.  
    71.                 if(book[j]==0)
    72.                 {
    73.                     book[j]=1;
    74.                     q.push(j);
    75.                 }
    76.             }
    77.             x=nex[x];
    78.         }
    79.     }
    80.  
    81.     //cout<
    82.  
    83.     return dis[ed]!=-inf;
    84. }
    85. ll maxcost,maxflow;
    86.  
    87. void work()
    88. {
    89.     while(SPFA())
    90.     {
    91.         int x=ed;
    92.         maxflow+=minn[ed];
    93.  
    94.         maxcost+=minn[ed]*dis[ed];
    95.  
    96.         int i;
    97.         while(x!=st)
    98.         {
    99.             i=pre[x];
    100.             s[i].flow-=minn[ed];
    101.             s[i^1].flow+=minn[ed];
    102.  
    103.             x=s[i^1].e;
    104.         }
    105.  
    106.     }
    107. }
    108.  
    109. bool vis[1010];
    110.  
    111. void dfs1(int now)
    112. {
    113.     vis[now-n]=1;
    114.     cout<
    115.  
    116.     int x=f[now];
    117.     while(x!=-1)
    118.     {
    119.         int j=s[x].e;
    120.  
    121.        // cout<
    122.  
    123.         if(s[x].e>st&&s[x].e<=n&&vis[s[x].e]==0&&s[x].flow==0)
    124.         {
    125.             dfs1(s[x].e+n);
    126.             break;
    127.         }
    128.         x=nex[x];
    129.     }
    130. }
    131.  
    132.  
    133. void dfs2(int now)
    134. {
    135.     vis[now-n]=1;
    136.  
    137.     int x=f[now];
    138.     while(x!=-1)
    139.     {
    140.         int j=s[x].e;
    141.  
    142.         if(s[x].e>st&&s[x].e<=n&vis[s[x].e]==0&&s[x].flow==0)
    143.         {
    144.             dfs2(s[x].e+n);
    145.             //break;
    146.         }
    147.         x=nex[x];
    148.     }
    149.  
    150.       cout<
    151. }
    152. int main()
    153. {
    154.     cin>>n>>m;
    155.  
    156.     memset(f,-1,sizeof(f));
    157.     for(int i=1;i<=n;i++)
    158.     {
    159.         cin>>city[i];
    160.         mp[city[i]]=i;
    161.     }
    162.     st=0;
    163.     ed=2*n+1;
    164.  
    165.     int flag=0;
    166.     for(int i=1;i<=m;i++)
    167.     {
    168.         string x,y;
    169.         cin>>x>>y;
    170.         int xx,yy;
    171.  
    172.         xx=mp[x];
    173.         yy=mp[y];
    174.  
    175.         if(xx>yy)
    176.             swap(xx,yy);
    177.  
    178.         if(xx==1&&yy==n)
    179.             flag=1;
    180.  
    181.  
    182.  
    183.         add(xx+n,yy,1,1);
    184.         add(yy,xx+n,0,-1);
    185.  
    186.     }
    187.  
    188.     for(int i=1;i<=n;i++)
    189.     {
    190.         if(i==1||i==n)
    191.         {
    192.             add(i,i+n,2,0);
    193.             add(i+n,i,0,0);
    194.             continue;
    195.         }
    196.  
    197.         add(i,i+n,1,0);
    198.         add(i+n,i,0,0);
    199.     }
    200.  
    201.     add(st,1,inf,0);
    202.  
    203.     add(1,st,0,0);
    204.  
    205.     add(2*n,ed,inf,0);
    206.  
    207.     add(ed,2*n,0,0);
    208.  
    209.     work();
    210.  
    211.     if(maxflow==2)
    212.     {
    213.         cout<
    214.  
    215.         dfs1(1+n);
    216.  
    217.         dfs2(1+n);
    218.     }
    219.     else
    220.     {
    221.        if(maxflow==1)
    222.        {
    223.            if(flag)
    224.            {
    225.                cout<<2<
    226.                
    227.                cout<1]<1]<
    228.            }
    229.            else
    230.            {
    231.                cout<<"No Solution!"<
    232.            }
    233.        }
    234.        else
    235.        {
    236.            cout<<"No Solution!"<
    237.        }
    238.  
    239.     }
    240.  
    241.  
    242.     return 0;
    243. }

    数字梯形问题 - 洛谷

    仍旧是考察拆点，所谓路径不想交，也就是边与点都不相交，即拆点权为1，边也为1，拆点之后费用为权值。这是第一问的解法

    第二问，不再拆点，上层点流向下层点时，边的费用改为上层点的权值即可

    第三问，取消边的流量限制即可

    值得注意的是，我们这三问，第一行的m个点全部只能经过一次，因为我们严格需要m条路径。

    1. # include
    2. using namespace std;
    3.  
    4. typedef long long int ll;
    5. ll a[100][100];
    6. typedef struct
    7. {
    8.     int b,e;
    9.     ll flow,dis;
    10. } xinxi;
    11. xinxi s[101010];
    12. int f[101010],nex[101010],len=2;
    13. void addd(int x,int y,ll flow, ll dis)
    14. {
    15.     s[len].b=x;
    16.     s[len].e=y;
    17.     s[len].flow=flow;
    18.     s[len].dis=dis;
    19.     nex[len]=f[x];
    20.     f[x]=len;
    21.     len++;
    22. }
    23. void add(int x,int y,ll flow, ll dis)
    24. {
    25.     s[len].b=x;
    26.     s[len].e=y;
    27.     s[len].flow=flow;
    28.     s[len].dis=dis;
    29.     nex[len]=f[x];
    30.     f[x]=len;
    31.     len++;
    32.  
    33.     addd(y,x,0,-dis);
    34. }
    35.  
    36. int pre[10100],vis[10100],st,ed;
    37. ll minn[10100],dis[10100],inf=1e18;
    38. queue<int>q;
    39.  
    40. bool SPFA()
    41. {
    42.     for(int i=st; i<=ed; i++)
    43.     {
    44.         vis[i]=0;
    45.         dis[i]=-inf;
    46.     }
    47.     q.push(st);
    48.     minn[st]=inf;
    49.     dis[st]=0;
    50.     vis[st]=1;
    51.  
    52.     while(!q.empty())
    53.     {
    54.         int now=q.front();
    55.         q.pop();
    56.         vis[now]=0;
    57.  
    58.         int x=f[now];
    59.         while(x!=-1)
    60.         {
    61.             int j=s[x].e;
    62.             if(s[x].flow==0)
    63.             {
    64.                 x=nex[x];
    65.                 continue;
    66.             }
    67.             if(dis[j]
    68.             {
    69.                 dis[j]=dis[now]+s[x].dis;
    70.                 minn[j]=min(minn[now],s[x].flow);
    71.  
    72.                 pre[j]=x;
    73.  
    74.                 if(!vis[j])
    75.                 {
    76.                     vis[j]=1;
    77.                     q.push(j);
    78.                 }
    79.             }
    80.             x=nex[x];
    81.         }
    82.     }
    83.  
    84.     return (dis[ed]!=-inf);
    85.  
    86. }
    87. ll ans=0;
    88. void work()
    89. {
    90.  
    91.     ans=0;
    92.  
    93.     while(SPFA())
    94.     {
    95.         int x=ed;
    96.  
    97.         ans+=minn[ed]*dis[ed];
    98.         int i;
    99.  
    100.         while(x!=st)
    101.         {
    102.             i=pre[x];
    103.             s[i].flow-=minn[ed];
    104.             s[i^1].flow+=minn[ed];
    105.  
    106.             x=s[i^1].e;
    107.         }
    108.     }
    109. }
    110. void init()
    111. {
    112.     len=2;
    113.     memset(f,-1,sizeof(f));
    114.     memset(nex,0,sizeof(nex));
    115.     st=0;
    116.     ed=10000;
    117. }
    118. int n,m,tot,id[100][100];
    119. int main()
    120. {
    121.  
    122.     cin>>m>>n;
    123.     init();
    124.  
    125.     for(int i=1; i<=n; i++)
    126.     {
    127.         for(int j=1; j<=m+i-1; j++)
    128.         {
    129.             tot++;
    130.             id[i][j]=tot;
    131.             cin>>a[i][j];
    132.         }
    133.     }
    134.  
    135.     for(int i=1; i<=n; i++)
    136.     {
    137.         for(int j=1; j<=m+i-1; j++)
    138.         {
    139.             add(id[i][j],id[i][j]+tot,1,a[i][j]);
    140.  
    141.             if(i
    142.             {
    143.  
    144.                 add(id[i][j]+tot,id[i+1][j],1,0);
    145.  
    146.  
    147.                 add(id[i][j]+tot,id[i+1][j+1],1,0);
    148.             }
    149.  
    150.         }
    151.     }
    152.  
    153.     for(int i=1; i<=m; i++)
    154.     {
    155.         add(st,id[1][i],1,0);
    156.     }
    157.     for(int i=1; i<=m+n-1; i++)
    158.     {
    159.         add(id[n][i]+tot,ed,1,0);
    160.     }
    161.  
    162.     work();
    163.  
    164.     cout<
    165.  
    166.     init();
    167.  
    168.     for(int i=1;i<=m;i++)
    169.     {
    170.         add(st,id[1][i],1,0);
    171.  
    172.     }
    173.  
    174.     for(int i=1;i<=m+n-1;i++)
    175.     {
    176.         add(id[n][i],ed,inf,a[n][i]);
    177.     }
    178.  
    179.     for(int i=1;i<=n;i++)
    180.     {
    181.         for(int j=1;j<=m+i-1;j++)
    182.         {
    183.             if(i==n)
    184.                 continue;
    185.  
    186.             add(id[i][j],id[i+1][j],1,a[i][j]);
    187.  
    188.  
    189.             add(id[i][j],id[i+1][j+1],1,a[i][j]);
    190.         }
    191.     }
    192.  
    193.     work();
    194.  
    195.     cout<
    196.  
    197.     init();
    198.  
    199.  
    200.     for(int i=1;i<=m;i++)
    201.     {
    202.         add(st,id[1][i],1,0);
    203.  
    204.     }
    205.  
    206.     for(int i=1;i<=m+n-1;i++)
    207.     {
    208.         add(id[n][i],ed,inf,a[n][i]);
    209.     }
    210.  
    211.     for(int i=1;i<=n;i++)
    212.     {
    213.         for(int j=1;j<=m+i-1;j++)
    214.         {
    215.             if(i==n)
    216.                 continue;
    217.  
    218.             add(id[i][j],id[i+1][j],inf,a[i][j]);
    219.  
    220.  
    221.             add(id[i][j],id[i+1][j+1],inf,a[i][j]);
    222.         }
    223.     }
    224.  
    225.     work();
    226.  
    227.     cout<
    228.     return 0;
    229. }

        

     最长k可重区间集问题 - 洛谷

     比较独特的建图方式，离散化取点之后，为了使费用最大，我们最终是一定会走原线段。我们不相交的若干条路径，所耗费的流量仅仅为1，否则会多消耗一个流量。在最大流上限为k的前提下，我们最终会选取最多k路不相交线段，且费用最大

    1. #include 
    2.  
    3. using namespace std;
    4. typedef long long int  ll;
    5.  
    6. int x[1000],y[1000],a[10100],tot;
    7. int st,ed;
    8. typedef struct
    9. {
    10.     int b,e;
    11.     ll flow,dis;
    12. }xinxi;
    13. xinxi s[101010];
    14. int f[101010],nex[101010],len=2;
    15. void add(int x,int y,ll flow, ll dis)
    16. {
    17.     s[len].b=x;
    18.     s[len].e=y;
    19.     s[len].flow=flow;
    20.     s[len].dis=dis;
    21.     nex[len]=f[x];
    22.     f[x]=len;
    23.     len++;
    24. }
    25. ll minn[1010],dis[1010],pre[1010];
    26. bool vis[1010];
    27. queue<int>q;
    28. ll inf=1e18;
    29. bool SPFA()
    30. {
    31.     for(int i=0;i<=ed;i++)
    32.     {
    33.         vis[i]=0;
    34.         dis[i]=-inf;
    35.     }
    36.  
    37.     vis[st]=1;
    38.     dis[st]=0;
    39.  
    40.     minn[st]=inf;
    41.  
    42.     q.push(st);
    43.  
    44.     while(!q.empty())
    45.     {
    46.         int now=q.front();
    47.         q.pop();
    48.         vis[now]=0;
    49.         int x=f[now];
    50.         while(x!=-1)
    51.         {
    52.             int j=s[x].e;
    53.             if(s[x].flow==0)
    54.             {
    55.                 x=nex[x];
    56.                 continue;
    57.             }
    58.  
    59.             if(dis[j]
    60.             {
    61.                 dis[j]=dis[now]+s[x].dis;
    62.                 pre[j]=x;
    63.  
    64.                 minn[j]=min(minn[now],s[x].flow);
    65.  
    66.                 if(!vis[j])
    67.                 {
    68.                     vis[j]=1;
    69.                     q.push(j);
    70.                 }
    71.             }
    72.             x=nex[x];
    73.         }
    74.     }
    75.  
    76.  
    77.  
    78.     return dis[ed]!=-inf;
    79. }
    80. ll ans;
    81. void work()
    82. {
    83.     while(SPFA())
    84.     {
    85.  
    86.  
    87.         ans+=minn[ed]*dis[ed];
    88.         int x=ed;
    89.         int i;
    90.         while(x!=st)
    91.         {
    92.             i=pre[x];
    93.  
    94.             s[i].flow-=minn[ed];
    95.             s[i^1].flow+=minn[ed];
    96.  
    97.             x=s[i^1].e;
    98.  
    99.         }
    100.     }
    101. }
    102. int n,k;
    103.  
    104. int main()
    105. {
    106.  
    107.   cin>>n>>k;
    108.  
    109.   memset(f,-1,sizeof(f));
    110.  
    111.   for(int i=1;i<=n;i++)
    112.   {
    113.       cin>>x[i]>>y[i];
    114.       tot++;
    115.       a[tot]=x[i];
    116.       tot++;
    117.       a[tot]=y[i];
    118.   }
    119.  
    120.   sort(a+1,a+1+tot);
    121.   int newlen=unique(a+1,a+1+tot)-a-1;
    122.  
    123.   ed=newlen+1;
    124.  
    125.  
    126.   for(int i=1;i<=n;i++)
    127.   {
    128.       int now=y[i]-x[i];
    129.       x[i]=lower_bound(a+1,a+1+newlen,x[i])-a;
    130.       y[i]=lower_bound(a+1,a+1+newlen,y[i])-a;
    131.  
    132.  
    133.  
    134.       add(x[i],y[i],1,now);
    135.  
    136.       add(y[i],x[i],0,-now);
    137.  
    138.   }
    139.  
    140.   for(int i=1;i
    141.   {
    142.       add(i,i+1,inf,0);
    143.       add(i+1,i,0,0);
    144.   }
    145.  
    146.   add(st,1,k,0);
    147.  
    148.   add(1,st,0,0);
    149.  
    150.   add(newlen,ed,k,0);
    151.  
    152.   add(ed,newlen,0,0);
    153.  
    154.  
    155.   work();
    156.   cout<
    157.  
    158.  
    159.  
    160.  
    161.     return 0;
    162. }

    深海机器人问题 - 洛谷

    比较容易想到的建边思路，每个边只能采集一次也就是边建立两次，一次是一次性，有价值的，二次是无限次无价值的。难在下标与编号的分配，细节较多

    1. #include 
    2.  
    3. using namespace std;
    4. typedef long long int  ll;
    5.  
    6. int st,ed;
    7.  
    8. typedef struct
    9. {
    10.     int b,e;
    11.     ll flow,dis;
    12. }xinxi;
    13. xinxi s[101010];
    14. int f[101010],nex[101010],len=2;
    15. ll inf=1e18;
    16.  
    17. void add(int x,int y,ll flow,ll dis)
    18. {
    19.     s[len].b=x;
    20.     s[len].e=y;
    21.     s[len].flow=flow;
    22.     s[len].dis=dis;
    23.     nex[len]=f[x];
    24.     f[x]=len;
    25.     len++;
    26.  
    27. }
    28. ll minn[101010],pre[101010],dis[101010];
    29. queue<int>q;
    30. bool vis[101010];
    31.  
    32. bool SPFA()
    33. {
    34.     for(int i=st;i<=ed;i++)
    35.     {
    36.         dis[i]=-inf;
    37.         vis[i]=0;
    38.     }
    39.     vis[st]=1;
    40.     dis[st]=0;
    41.     minn[st]=inf;
    42.     q.push(st);
    43.     while(!q.empty())
    44.     {
    45.         int now=q.front();
    46.         q.pop();
    47.         vis[now]=0;
    48.         int x=f[now];
    49.         while(x!=-1)
    50.         {
    51.             int j=s[x].e;
    52.             if(s[x].flow==0)
    53.             {
    54.                 x=nex[x];
    55.                 continue;
    56.             }
    57.  
    58.             if(dis[j]
    59.             {
    60.                 dis[j]=dis[now]+s[x].dis;
    61.                 pre[j]=x;
    62.                 minn[j]=min(minn[now],s[x].flow);
    63.                 if(!vis[j])
    64.                 {
    65.                     vis[j]=1;
    66.                     q.push(j);
    67.                 }
    68.  
    69.             }
    70.  
    71.             x=nex[x];
    72.         }
    73.     }
    74.  
    75.     return dis[ed]!=-inf;
    76. }
    77.  
    78. ll ans;
    79. void work()
    80. {
    81.     while(SPFA())
    82.     {
    83.         ans+=minn[ed]*dis[ed];
    84.         int x=ed;
    85.         int i;
    86.         while(x!=st)
    87.         {
    88.             i=pre[x];
    89.             s[i].flow-=minn[ed];
    90.             s[i^1].flow+=minn[ed];
    91.  
    92.             x=s[i^1].e;
    93.         }
    94.     }
    95. }
    96. int main()
    97. {
    98.  
    99.   int a,b;
    100.   cin>>a>>b;
    101.  
    102.   int p,q;
    103.   cin>>p>>q;
    104. memset(f,-1,sizeof(f));
    105.  
    106.  
    107.  
    108.   for(int i=1;i<=p+1;i++)
    109.   {
    110.       for(int j=1;j<=q;j++)
    111.       {
    112.           int cost;
    113.           cin>>cost;
    114.           int l=(i-1)*(q+1)+j;
    115.           int r=(i-1)*(q+1)+j+1;
    116.  
    117.          // cout<
    118.           add(l,r,1,cost);
    119.           add(r,l,0,-cost);
    120.  
    121.           add(l,r,inf,0);
    122.           add(r,l,0,0);
    123.  
    124.       }
    125.   }
    126.  
    127.  for(int j=1;j<=q+1;j++)
    128.  {
    129.      for(int i=1;i<=p;i++)
    130.      {
    131.          int cost;
    132.           cin>>cost;
    133.           int l=(i-1)*(q+1)+j;
    134.  
    135.  
    136.           int r=(i)*(q+1)+j;
    137.  
    138.          // cout<
    139.  
    140.           add(l,r,1,cost);
    141.           add(r,l,0,-cost);
    142.  
    143.           add(l,r,inf,0);
    144.           add(r,l,0,0);
    145.      }
    146.  }
    147.  
    148.  st=0,ed=(p+2)*(q+2);
    149.  
    150.  
    151.  while(a--)
    152.  {
    153.      int k,x,y;
    154.      cin>>k>>x>>y;
    155.  
    156.      int id=(q+1)*x+y+1;
    157.  
    158.      add(st,id,k,0);
    159.      add(id,st,0,0);
    160.  }
    161.  
    162.  while(b--)
    163.  {
    164.      int k,x,y;
    165.  
    166.      cin>>k>>x>>y;
    167.  
    168.      int id=(q+1)*x+y+1;
    169.  
    170.      add(id,ed,k,0);
    171.      add(ed,id,0,0);
    172.  }
    173.  
    174.  
    175.  
    176.  work();
    177.  
    178.  cout<
    179.  
    180.     return 0;
    181. }

    负载平衡问题 - 洛谷

    小于平均值的点需要接受流量，接受流量之后需要连接汇点，大于平均值的点需要提供流量，连接源点。每个相邻点之间可以交换，也就是费用为1.跑费用流即可

    1. #include 
    2.  
    3. using namespace std;
    4. typedef long long int  ll;
    5.  
    6. ll a[1000],sum;
    7. int n,st,ed;
    8.  
    9. typedef struct
    10. {
    11.     int b,e;
    12.     ll flow,dis;
    13. }xinxi;
    14. xinxi s[101010];
    15. int f[101010],nex[101010],len=2;
    16. void add(int x,int y,ll flow, ll dis)
    17. {
    18.     s[len].b=x;
    19.     s[len].e=y;
    20.  
    21.     s[len].flow=flow;
    22.     s[len].dis=dis;
    23.  
    24.     nex[len]=f[x];
    25.     f[x]=len;
    26.     len++;
    27. }
    28.  
    29. ll minn[1010],pre[1010],dis[1010],inf=1e18;
    30. queue<int>q;
    31. bool vis[1010];
    32. bool  SPFA()
    33. {
    34.     for(int i=st;i<=ed;i++)
    35.     {
    36.         vis[i]=0;
    37.         dis[i]=inf;
    38.     }
    39.  
    40.     dis[st]=0;
    41.  
    42.     vis[st]=1;
    43.  
    44.     minn[st]=inf;
    45.     q.push(st);
    46.  
    47.     while(!q.empty())
    48.     {
    49.         int now=q.front();
    50.         q.pop();
    51.  
    52.       //  cout<
    53.  
    54.         vis[now]=0;
    55.  
    56.         int x=f[now];
    57.  
    58.         while(x!=-1)
    59.         {
    60.             int j=s[x].e;
    61.  
    62.             if(s[x].flow==0)
    63.             {
    64.                 x=nex[x];
    65.                 continue;
    66.             }
    67.  
    68.             if(dis[j]>dis[now]+s[x].dis)
    69.             {
    70.                 dis[j]=dis[now]+s[x].dis;
    71.  
    72.                 pre[j]=x;
    73.  
    74.                 minn[j]=min(minn[now],s[x].flow);
    75.  
    76.                 if(!vis[j])
    77.                 {
    78.                     vis[j]=1;
    79.                     q.push(j);
    80.                 }
    81.             }
    82.  
    83.             x=nex[x];
    84.         }
    85.     }
    86.  
    87.  //   cout<
    88.  
    89.     return dis[ed]!=inf;
    90. }
    91.  
    92. ll ans;
    93. void work()
    94. {
    95.     while(SPFA())
    96.     {
    97.  
    98.  
    99. //    cout<<"*"<
    100.  
    101.         int x=ed;
    102.  
    103.         ans+=minn[ed]*dis[ed];
    104.  
    105.         int i;
    106.         while(x!=st)
    107.         {
    108.             i=pre[x];
    109.  
    110.            // cout<
    111.  
    112.             s[i].flow-=minn[ed];
    113.  
    114.             s[i^1].flow+=minn[ed];
    115.  
    116.             x=s[i^1].e;
    117.         }
    118.     }
    119. }
    120. int main()
    121. {
    122.     memset(f,-1,sizeof(f));
    123.  
    124.  
    125.    cin>>n;
    126.    for(int i=1;i<=n;i++)
    127.    {
    128.        cin>>a[i];
    129.        sum+=a[i];
    130.    }
    131.  
    132.    st=0;
    133.    ed=n+1;
    134.  
    135.    sum/=n;
    136.  
    137.    for(int i=1;i<=n;i++)
    138.    {
    139.        if(i==1)
    140.        {
    141.            add(i,n,inf,1);
    142.  
    143.            add(n,i,0,-1);
    144.  
    145.            add(i,i+1,inf,1);
    146.  
    147.            add(i+1,i,0,-1);
    148.        }
    149.        else if(i==n)
    150.        {
    151.            add(i,i-1,inf,1);
    152.  
    153.            add(i-1,i,0,-1);
    154.  
    155.            add(i,1,inf,1);
    156.  
    157.            add(1,i,0,-1);
    158.        }
    159.        else
    160.        {
    161.            add(i,i-1,inf,1);
    162.  
    163.            add(i-1,i,0,-1);
    164.  
    165.            add(i,i+1,inf,1);
    166.  
    167.            add(i+1,i,0,-1);
    168.        }
    169.  
    170.    }
    171.  
    172.    for(int i=1;i<=n;i++)
    173.    {
    174.        if(a[i]
    175.        {
    176.            add(i,ed,sum-a[i],0);
    177.  
    178.            add(ed,i,0,0);
    179.        }
    180.        else if(a[i]>sum)
    181.        {
    182.            add(st,i,a[i]-sum,0);
    183.  
    184.            add(i,st,0,0);
    185.        }
    186.    }
    187.  
    188.    work();
    189.  
    190.    cout<
    191.  
    192.  
    193.     return 0;
    194. }

    餐巾计划问题 - 洛谷 

    餐巾纸的干净与否是需要拆点才能达成的，我们主点代表每日接受的干净纸巾，每日的干净纸巾用完之后由超级源点强制输送给脏纸巾，而不用干净纸巾和脏纸巾之间连边来完成。否则，我们每天的干净纸巾不一定真的就留给脏纸巾。我们每天产生的脏纸巾是一定的，是强制的 

    1. #include 
    2.  
    3. using namespace std;
    4. typedef long long int  ll;
    5.  
    6. int n;
    7. int a[5000];
    8. int st=0,ed;
    9.  
    10. typedef struct
    11. {
    12.     int b,e;
    13.     ll flow,dis;
    14. }xinxi;
    15. xinxi s[1010100];
    16. int f[1010100],nex[1010100],len=2;
    17. void add(int x,int y,ll flow,ll dis)
    18. {
    19.     s[len].b=x;
    20.     s[len].e=y;
    21.     s[len].flow=flow;
    22.     s[len].dis=dis;
    23.     nex[len]=f[x];
    24.     f[x]=len;
    25.     len++;
    26. }
    27.  
    28. ll minn[1010010],dis[1010010],pre[1010100],inf=1e18;
    29. bool vis[101010];
    30. queue<int>q;
    31.  
    32. bool SPFA()
    33. {
    34.     for(int i=st;i<=ed;i++)
    35.     {
    36.         vis[i]=0;
    37.         dis[i]=inf;
    38.     }
    39.     vis[st]=1;
    40.     dis[st]=0;
    41.     minn[st]=inf;
    42.     q.push(st);
    43.  
    44.     while(!q.empty())
    45.     {
    46.         int now=q.front();
    47.         q.pop();
    48.         vis[now]=0;
    49.  
    50.         int x=f[now];
    51.         while(x!=-1)
    52.         {
    53.             int j=s[x].e;
    54.  
    55.             if(s[x].flow==0)
    56.             {
    57.                 x=nex[x];
    58.  
    59.                 continue;
    60.             }
    61.  
    62.             if(dis[j]>dis[now]+s[x].dis)
    63.             {
    64.                 dis[j]=dis[now]+s[x].dis;
    65.  
    66.                  minn[j]=min(minn[now],s[x].flow);
    67.  
    68.                  pre[j]=x;
    69.  
    70.                  if(!vis[j])
    71.                  {
    72.                      vis[j]=1;
    73.                      q.push(j);
    74.                  }
    75.             }
    76.  
    77.             x=nex[x];
    78.         }
    79.     }
    80.  
    81.  
    82.   //  cout<
    83.  
    84.     return dis[ed]!=inf;
    85. }
    86. ll ans;
    87.  
    88. void work()
    89. {
    90.     while(SPFA())
    91.     {
    92.         ans+=minn[ed]*dis[ed];
    93.         int x=ed;
    94.         int i;
    95.  
    96.         while(x!=st)
    97.         {
    98.             i=pre[x];
    99.             s[i].flow-=minn[ed];
    100.             s[i^1].flow+=minn[ed];
    101.  
    102.             x=s[i^1].e;
    103.         }
    104.     }
    105. }
    106. int main()
    107. {
    108.      cin>>n;
    109.  
    110.      memset(f,-1,sizeof(f));
    111.  
    112.      for(int i=1;i<=n;i++)
    113.      {
    114.          cin>>a[i];
    115.      }
    116.      int price,time1,price1,time2,price2;
    117.  
    118.      cin>>price>>time1>>price1>>time2>>price2;
    119.  
    120.      ed=n+n+1;
    121.  
    122.      for(int i=1;i<=n;i++)
    123.      {
    124.          int zhu=i;
    125.          int fu=i+n;
    126.  
    127.        
    128.          add(zhu,ed,a[i],0);
    129.          add(ed,zhu,0,0);
    130.  
    131.          add(st,zhu,inf,price);
    132.          add(zhu,st,0,-price);  
    133.  
    134.          add(st,fu,a[i],0);
    135.  
    136.          add(fu,st,0,0);  
    137.  
    138.          if(i+time1<=n)
    139.          {
    140.              add(fu,i+time1,inf,price1);
    141.  
    142.              add(i+time1,fu,0,-price1);
    143.  
    144.          }
    145.  
    146.          if(i+time2<=n)
    147.          {
    148.  
    149.              add(fu,i+time2,inf,price2);
    150.  
    151.              add(i+time2,fu,0,-price2);
    152.          }
    153.  
    154.          if(i+1<=n)
    155.          {
    156.              add(fu,i+1+n,inf,0);
    157.  
    158.              add(i+1+n,fu,0,0);
    159.          }
    160.      }
    161.  
    162.  
    163.  
    164.      work();
    165.  
    166.  
    167.  
    168.      cout<
    169.  
    170.  
    171.  
    172.     return 0;
    173. }

     

     有上下界的网络流

    每条路径的流量是有上下界的，我们需要强制把下限先流满的网络流。

    构造方式

    将每条边的上下界求出之后，原图上构造上界减去下界的边。

    对于一条u-v的下界边 新建超级源点SS,汇点TT，u要流出，那么就与TT连接下界权值，v同理

    连接原图的T-S 边权inf 

    新跑出的最大流应该是全部下界的和。

    NC238100Budget

    本题中，按照上述方法建图验证之后，残留网络上剩余的流量（反向边上），加上下界即可

     

    1. #include
    2. using namespace std;
    3. typedef long long int  ll;
    4.  
    5. ll up[500][500],down[500][500],inf=1e18;
    6. ll a[500],b[500];
    7. int n,m;
    8.  
    9. int S,T,SS,TT;
    10.  
    11. typedef struct
    12. {
    13.     int b,e;
    14.     ll flow;
    15. }xinxi;
    16. xinxi s[101010];
    17. int f[101010],nex[101010],len=2;
    18.  
    19. void add(int x,int y,ll flow)
    20. {
    21.     s[len].b=x;
    22.     s[len].e=y;
    23.     s[len].flow=flow;
    24.     nex[len]=f[x];
    25.     f[x]=len;
    26.     len++;
    27. }
    28. int dep[101010];
    29. queue<int>q;
    30. bool BFS()
    31. {
    32.     for(int i=0;i<=TT;i++)
    33.     {
    34.         dep[i]=0;
    35.     }
    36.     q.push(SS);
    37.     dep[SS]=1;
    38.  
    39.     while(!q.empty())
    40.     {
    41.         int now=q.front();
    42.         q.pop();
    43.  
    44.         int x=f[now];
    45.         while(x!=-1)
    46.         {
    47.             int j=s[x].e;
    48.             if(s[x].flow&&!dep[j])
    49.             {
    50.                 dep[j]=dep[now]+1;
    51.                 q.push(j);
    52.             }
    53.             x=nex[x];
    54.         }
    55.     }
    56.  
    57.     return dep[TT];
    58.  
    59. }
    60.  
    61. ll dfs(int now, ll flow)
    62. {
    63.     if(now==TT)
    64.         return flow;
    65.  
    66.  
    67.         ll out=0;
    68.  
    69.        int x=f[now];
    70.  
    71.        while(x!=-1)
    72.        {
    73.            int j=s[x].e;
    74.  
    75.            if(dep[j]==dep[now]+1&&s[x].flow)
    76.            {
    77.                ll temp=dfs(j,min(flow,s[x].flow));
    78.  
    79.                s[x].flow-=temp;
    80.                s[x^1].flow+=temp;
    81.  
    82.                flow-=temp;
    83.                out+=temp;
    84.             }
    85.  
    86.             if(!flow)
    87.                 break;
    88.             x=nex[x];
    89.        }
    90.  
    91.  
    92.     if(!out)
    93.         dep[now]=0;
    94.     return out;
    95. }
    96. void init(ll r,ll c,char ch, ll val)
    97. {
    98.     if(ch=='>')
    99.     {
    100.         if(!r&&!c)
    101.         {
    102.             for(int i=1; i<=n; i++)
    103.             {
    104.                 for(int j=1; j<=m; j++)
    105.                 {
    106.                     down[i][j]=max(down[i][j],val+1);
    107.                 }
    108.             }
    109.         }
    110.         else if(!r)
    111.         {
    112.             for(int i=1; i<=n; i++)
    113.             {
    114.                 down[i][c]=max(down[i][c],val+1);
    115.             }
    116.         }
    117.         else if(!c)
    118.         {
    119.             for(int j=1; j<=m; j++)
    120.             {
    121.                 down[r][j]=max(down[r][j],val+1);
    122.             }
    123.         }
    124.         else
    125.         {
    126.             down[r][c]=max(down[r][c],val+1);
    127.         }
    128.     }
    129.     else if(ch=='<')
    130.     {
    131.         if(!r&&!c)
    132.         {
    133.             for(int i=1; i<=n; i++)
    134.             {
    135.                 for(int j=1; j<=m; j++)
    136.                 {
    137.                     down[i][j]=max(down[i][j],0ll);
    138.                     up[i][j]=min(up[i][j],val-1);
    139.                 }
    140.             }
    141.         }
    142.         else if(!r)
    143.         {
    144.             for(int i=1; i<=n; i++)
    145.             {
    146.                 down[i][c]=max(down[i][c],0ll);
    147.                 up[i][c]=min(up[i][c],val-1);
    148.             }
    149.         }
    150.         else if(!c)
    151.         {
    152.             for(int j=1; j<=m; j++)
    153.             {
    154.                 down[r][j]=max(down[r][j],0ll);
    155.                 up[r][j]=min(up[r][j],val-1);
    156.             }
    157.         }
    158.         else
    159.         {
    160.             down[r][c]=max(down[r][c],0ll);
    161.             up[r][c]=min(up[r][c],val-1);
    162.         }
    163.     }
    164.     else
    165.     {
    166.  
    167.         if(!r&&!c)
    168.         {
    169.             for(int i=1; i<=n; i++)
    170.             {
    171.                 for(int j=1; j<=m; j++)
    172.                 {
    173.                     down[i][j]=val;
    174.                     up[i][j]=val;
    175.                 }
    176.             }
    177.         }
    178.         else if(!r)
    179.         {
    180.             for(int i=1; i<=n; i++)
    181.             {
    182.                 down[i][c]=val;
    183.                 up[i][c]=val;
    184.             }
    185.         }
    186.         else if(!c)
    187.         {
    188.             for(int j=1; j<=m; j++)
    189.             {
    190.                 down[r][j]=val;
    191.                 up[r][j]=val;
    192.             }
    193.         }
    194.         else
    195.         {
    196.             down[r][c]=val;
    197.             up[r][c]=val;
    198.         }
    199.     }
    200. }
    201. ll res[500][500];
    202. int main()
    203. {
    204.  
    205.     cin>>n>>m;
    206.     memset(f,-1,sizeof(f));
    207.  
    208.     for(int i=1; i<=n; i++)
    209.     {
    210.         for(int j=1; j<=m; j++)
    211.         {
    212.             up[i][j]=inf;
    213.  
    214.         }
    215.     }
    216.     for(int i=1; i<=n; i++)
    217.     {
    218.         cin>>a[i];
    219.     }
    220.     for(int i=1; i<=m; i++)
    221.     {
    222.         cin>>b[i];
    223.     }
    224.  
    225.     int t;
    226.     cin>>t;
    227.     while(t--)
    228.     {
    229.         ll r,c,val;
    230.         char ch;
    231.         cin>>r>>c>>ch>>val;
    232.  
    233.         init(r,c,ch,val);
    234.     }
    235.  
    236.     S=n+m+1;
    237.     T=n+m+2;
    238.     SS=n+m+3;
    239.     TT=n+m+4;
    240.  
    241.     ll sum=0;
    242.  
    243.     for(int i=1;i<=n;i++)
    244.     {
    245.         add(S,i,a[i]);
    246.         add(i,S,0);
    247.         sum+=a[i];
    248.     }
    249.  
    250.     for(int i=1;i<=m;i++)
    251.     {
    252.         add(i+n,T,b[i]);
    253.         add(T,i+n,0);
    254.         sum+=b[i];
    255.     }
    256.  
    257.     for(int i=1;i<=n;i++)
    258.     {
    259.         for(int j=1;j<=m;j++)
    260.         {
    261.             add(i,j+n,up[i][j]-down[i][j]);
    262.             add(j+n,i,0);
    263.         }
    264.     }
    265.  
    266.     for(int i=1;i<=n;i++)
    267.     {
    268.         for(int j=1;j<=m;j++)
    269.         {
    270.             add(i,TT,down[i][j]);
    271.             add(TT,i,0);
    272.             sum+=down[i][j];
    273.  
    274.             add(SS,j+n,down[i][j]);
    275.             add(j+n,SS,0);
    276.         }
    277.     }
    278.  
    279.     for(int i=1;i<=n;i++)
    280.     {
    281.         add(S,TT,a[i]);
    282.  
    283.         add(TT,S,0);
    284.  
    285.         add(SS,i,a[i]);
    286.  
    287.         add(i,SS,0);
    288.     }
    289.  
    290.     for(int i=1;i<=m;i++)
    291.     {
    292.         add(i+n,TT,b[i]);
    293.         add(TT,i+n,0);
    294.  
    295.         add(SS,T,b[i]);
    296.         add(T,SS,0);
    297.     }
    298.  
    299.     add(T,S,inf);
    300.  
    301.     ll ans=0;
    302.  
    303.     while(BFS())
    304.     {
    305.         ans+=dfs(SS,inf);
    306.     }
    307.  
    308.    if(ans!=sum)
    309.    {
    310.        cout<<"IMPOSSIBLE"<
    311.        return 0;
    312.    }
    313.  
    314.    for(int i=1;i<=n;i++)
    315.    {
    316.        int x=f[i];
    317.  
    318.        while(x!=-1)
    319.        {
    320.            int j=s[x].e;
    321.  
    322.            if(j>=n+1&&j<=n+m)
    323.            {
    324.                res[i][j-n]=s[x^1].flow+down[i][j-n];
    325.  
    326.            }
    327.            x=nex[x];
    328.        }
    329.    }
    330.  
    331.    for(int i=1;i<=n;i++)
    332.    {
    333.        for(int j=1;j<=m;j++)
    334.        {
    335.            cout<" ";
    336.        }
    337.        cout<
    338.    }
    339.     return 0;
    340. }

  • 相关阅读:
    算法基础：单链表图解及模板总结
    java计算机毕业设计网上教学管理系统源代码+数据库+系统+lw文档
    【学习笔记】MySQL（Ⅱ）
    PTA 7-68 Redemption
    删库跑路、“投毒”、改协议，开源有哪几大红线千万不能踩？
    Java Map集合面试题汇总
    全网最全Django面试题整理（一）
    C# Solidworks二次开发：创建距离配合以及移动组件API详解
    基于 FFmpeg 的跨平台视频播放器简明教程（十一）：一种简易播放器的架构介绍
    【科普】ARM架构
  • 原文地址：https://blog.csdn.net/jisuanji2606414/article/details/126956348