Network flow 2 · Maximum flow minimum cut theorem

The time limit :10000ms
Single point time limit :1000ms
Memory limit :256MB

describe

Small Hi: In the last week's Hiho In the following part, we will initially explain the concept of network flow and the conventional solution , Small Ho Do you remember the content ?

Small Ho: I remember ! Network flow is given a graph G=(V,E), And the source s And meeting point t. Every side e(u,v) With capacity c(u,v). The maximum flow problem of network flow is solved from s To t How much traffic can there be at most .

Small Hi: The solution to this problem ?

Small Ho: The basic idea to solve the network flow is to find the augmentation path , Keep updating the residual network . Until we can't find a new way to expand , The flow obtained at this time is the maximum flow of the network .

Small Hi: you 're right , It seems that you remember very well .

Small Ho: Hey, hey, hey , But here I have a problem , Why can't we find Zengguang road and find the maximum flow ?

Small Hi: This time I'll solve your doubts , First of all, let's start with the cut of network flow .

For a network flow graph G=(V,E), Its cut is defined as a way of dividing points : Divide all the points into S and T=V-S Two parts , Where the source point s∈S, Confluence t∈T.

For a cut (S,T), We define net flow f(S,T) It means to cut through (S,T) The sum of all the traffic , namely :

f(S,T) = Σf(u,v) | u∈S,v∈T

for instance ( This example is from introduction to Algorithms ):

 Net flow f = f(2,4)+f(3,4)+f(3,5) = 12+(-4)+11 = 19

At the same time, we define the capacity of cuts C(S,T) For all from S To T The sum of the edge capacities of , namely :

C(S,T) = Σc(u,v) | u∈S,v∈T

Also in the example above , Its cutting capacity is :

c(2,4)+c(3,5)=12+11=23

Small Ho: That is to say, we are calculating the cut (S,T) The net flow of f(S,T) There may be a reverse flow that makes f(u,v)<0, And capacity C(S,T) It must be a non negative number .

Small Hi: You're right to say that . In fact, for any cut of the net flow f(S,T) It's always related to the flow of network traffic f equal . For example, in the above example, let's change the way of cutting :

We can calculate the net flow for both cases f(S,T) Still equal to 19.

An intuitive explanation is : According to the definition of network flow , Only the source s It creates traffic , Confluence t Will receive traffic . So any non s and t The point of u, Its net flow must be 0, That is to say Σ(f(u,v))=0. And the source s All the traffic will eventually pass through the cut (S,T) To the meeting point t, So the flow of network flow f It's equal to the static flow of the cut f(S,T).

The strict proof is as follows :

f(S,T) = f(S,V) - f(S,S)
from S To T The flow of is equal to from S The flow to all nodes is subtracted from S To S The flow of internal nodes
f(S,T) = f(S,V)
because S The flow between internal nodes must have corresponding reverse flow , therefore f(S,S)=0
f(S,T) = f(s,V) + f(S-s,V)
then S The set is divided into source points s And others belong to S The node of
f(S,T) = f(s,V)
Because in addition to the source point s No flow is generated by other nodes , therefore f(S-s,V)=0
f(S,T) = f(s,V) = f

therefore f(S,T) It's from the source s Out of the stream , That's the flow of the network f.

Small Ho: Simple words , That is to say, the net flow of any cut f(S,T) Is equal to the current network traffic f.

Small Hi: That's true . And for the net flow of any cut f(S,T) It must be less than or equal to the capacity of the cut C(S,T). That is to say , For any stream in the network f It must be less than or equal to the capacity of any cut C(S,T).

And in all possible cuts , There is a cut with the smallest capacity , We call it the minimal cut .

This minimal cut limits the flow of a network f upper bound , So there is :

For any network flow graph , The maximum flow must be less than or equal to the minimum cut .

Small Ho: But what does this have to do with Zengguang road ?

Small Hi: Next is the point . Using the knowledge above , We can deduce a maximum flow minimum cut theorem :

 For a network flow graph G=(V,E), One of the active points s And meeting point t, So the following three conditions are equivalent :
1. flow f The picture is G The maximum flow of
2. Residual network Gf There is no augmentation road
3. about G Some cut of (S,T), here f = C(S,T)

First of all, prove that 1 => 2:

 We use the counter evidence , Suppose the flow f The picture is G The maximum flow of , But there are still augmented paths in the residual network p, Its flow is fp. Then we have flow f'=f+fp>f. This is related to f It's the maximum flow that leads to conflict .

And then prove 2 => 3:

 Suppose the residual network Gf There is no augmentation road , So in the residual network Gf There is no path from s arrive t. We define S The set is : In the current network s Points that can be reached . At the same time define T=V-S.
here (S,T) Make a cut (S,T). And for any u∈S,v∈T, Yes f(u,v)=c(u,v). if f(u,v)<c(u,v), Then there are Gf(u,v)>0,s It can reach v, And v Belong to T contradiction .
So there is f(S,T)=Σf(u,v)=Σc(u,v)=C(S,T).

Finally, prove 3 => 1:

 because f The upper bound of is the minimum cut , When f When we reach the capacity of the cut , It's obvious that we've reached the maximum , therefore f For maximum flow .

This explains why we can't find Zengguang road , It must be the maximum flow .

Small Ho: I see , Oh, I see .

Input

The first 1 That's ok :2 A positive integer N,M.2≤N≤500,1≤M≤20,000.

The first 2..M+1 That's ok : Each row 3 It's an integer u,v,c(u,v), To represent an edge (u,v) And its capacity c(u,v).1≤u,v≤N,0≤c(u,v)≤100.

The default source point in the given graph is 1, The meeting point is N. There may be duplicate edges .

Output

The first 1 That's ok :2 It's an integer A B,A Represents the capacity of the smallest cut ,B Represents a given graph G Minimum cut S The number of points in the set .

The first 2 That's ok :B An integer separated by spaces , Express S The point number of the set .

If there are multiple minimal cuts, the solution of any one can be output .

The sample input
6 7
1 2 3
1 3 5
2 4 1
3 4 2
3 5 3
4 6 4
5 6 2
Sample output
5 4
1 2 3 5 analysis : Min cut max flow ,dicnic;
Code :
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <climits>
#include <cstring>
#include <string>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <vector>
#include <list>
#define rep(i,m,n) for(i=m;i<=n;i++)
#define rsp(it,s) for(set<int>::iterator it=s.begin();it!=s.end();it++)
#define mod 1000000007
#define inf 0x3f3f3f3f
#define vi vector<int>
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define ll long long
#define pi acos(-1.0)
#define pii pair<int,int>
#define Lson L, mid, rt<<1
#define Rson mid+1, R, rt<<1|1
const int maxn=5e2+;
using namespace std;
ll gcd(ll p,ll q){return q==?p:gcd(q,p%q);}
ll qpow(ll p,ll q){ll f=;while(q){if(q&)f=f*p;p=p*p;q>>=;}return f;}
int n,m,k,t,h[maxn],tot,vis[maxn],s,cur[maxn];
bool flag;
set<int>ans;
struct node
{
int to,nxt,cap,flow;
}e[<<];
void add(int x,int y,int z)
{
e[tot].to=y;
e[tot].nxt=h[x];
e[tot].cap=z;
h[x]=tot++;
e[tot].to=x;
e[tot].nxt=h[y];
h[y]=tot++;
}
bool bfs()
{
memset(vis,,sizeof vis);
queue<int>p;
p.push(s);
vis[s]=;
if(flag)ans.insert(s);
while(!p.empty())
{
int x=p.front();p.pop();
for(int i=h[x];i!=-;i=e[i].nxt)
{
int to=e[i].to,cap=e[i].cap,flow=e[i].flow;
if(!vis[to]&&cap>flow)
{
vis[to]=vis[x]+;
p.push(to);
if(flag)ans.insert(to);
}
}
}
return vis[t];
}
int dfs(int x,int a)
{
if(x==t||a==)return a;
int ans=,j;
for(int&i=cur[x];i!=-;i=e[i].nxt)
{
int to=e[i].to,cap=e[i].cap,flow=e[i].flow;
if(vis[to]==vis[x]+&&(j=dfs(to,min(a,cap-flow)))>)
{
e[i].flow+=j;
e[i^].flow-=j;
ans+=j;
a-=j;
if(a==)break;
}
}
return ans;
}
int max_flow(int s,int t)
{
int flow=,i;
while(bfs())
{
rep(i,,n)cur[i]=h[i];
flow+=dfs(s,inf);
}
return flow;
}
int main()
{
int i,j;
memset(h,-,sizeof h);
scanf("%d%d",&n,&m);
while(m--)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
add(a,b,c);
}
s=,t=n;
printf("%d",max_flow(s,t));
flag=true;
bfs();
printf(" %d\n",ans.size());
for(int x:ans)printf("%d ",x);
printf("\n");
//system("Pause");
return ;
}

hihocoder Network flow 2 · The maximum flow and minimum cut theorem

  1. [HihoCoder1378] Network flow 2 &#183; Maximum flow minimum cut theorem

    Ideas : According to the theorem of maximum flow and minimum cut, the maximum flow is equal to the minimum cut , So you can run it first EdmondsKarp Algorithm . The next requirement is the graph after the minimum cut $S$ The set of points to which it belongs . The original idea is to use union search to deal with the residual network formed by all forward edges , ...

  2. 【hihocoder 1378】 Network flow 2 · Maximum flow minimum cut theorem

    [Link]:http://hihocoder.com/problemset/problem/1378 [Description] [Solution] After finding the minimum cut ( Maximum flow ) after ; In the rest of the network ...

  3. hiho The first 116 Zhou , Maximum flow minimum cut theorem , Find the minimum cut set S,T

    Small Hi: In the last week's Hiho In the following part, we will initially explain the concept of network flow and the conventional solution , Small Ho Do you remember the content ? Small Ho: I remember ! Network flow is given a graph G=(V,E), And the source s And meeting point t. Every side e(u,v) With capacity c ...

  4. 【codevs1907】 Take the number of squares 3( Maximum flow minimum cut theorem )

    website :http://codevs.cn/problem/1907/ The question : Select several nonadjacent numbers in a matrix , Make the sum of these numbers maximum . We can think of it as a minimal cut , The answer is all the numbers in the matrix - Minimum cut . Let's put the matrix in international order ...

  5. Niuke summer session 6 G /// Tree form DP Maximum flow minimum cut theorem

    The main idea of the topic : Input t,t Test cases Each test case input n Next n That's ok Input u,v,w, The boundless side of the tree u Point to v The point weight is w Find the sum of the maximum flows between any two points 1. Maximum flow minimum cut theorem That is, the maximum flow equals the minimum cut 2. Arbitrary numbers on undirected trees ...

  6. [ shortest path , Maximum flow minimum cut theorem ] 2019 Multi-University Training Contest 1 Path

    subject :http://acm.hdu.edu.cn/showproblem.php?pid=6582 Path Time Limit: 2000/1000 MS (Java/Others)    Mem ...

  7. [ Network flow 24 topic #9] [cogs734] Take the number of squares [ Network flow , Max flow min cut ]

    Divide the grid into two parts , The method is black and white dyeing , Judgment (i+j)&1 that will do , After separation, connect the edges from the white grid to the black grid , Each point needs four ( There may be fewer boundary points ), That's four directions around each grid . Then the source point and sink point are connected on the black and white grid , ...

  8. cogs750 Grid network flow ( Minimum cut )

    750. Grid network flow ***   Input file :flowa.in   The output file :flowa.out    Simple comparison of time limits :1 s   Memory limit :128 MB [ Problem description ] Bob I think the maximum flow problem of general graph is too ...

  9. FZU 1844 Earthquake Damage( Max flow min cut )

    Problem Description Open Source Tools help earthquake researchers stay a step ahead. Many geological ...

Random recommendation

  1. Bzoj3450 Tyvj1952 Easy

    Time Limit: 10 Sec  Memory Limit: 128 MBSubmit: 570  Solved: 428[Submit][Status][Discuss] Descriptio ...

  2. 3. Android Program generation steps

      The main process is shown in the figure below :       List of tools needed name Function is introduced The path in the operating system aapt Android Resource packaging tool ${ANDROID_SDK_HOME}/platform-tools/ ...

  3. 7-11 Use UNION Merge query

    Syntax of merge query : SELECT ...FROM  Table name one UNION SELECT ...FROM Table name two The characteristics of merge query : 1: The number of columns in the merged table , Data types data types are the same or compatible . 2:UNION Silent ...

  4. WPF、Windows Forms and Silverlight The connection and difference between ( turn )

    WPF.Windows Forms and Silverlight The connection and difference between http://blog.csdn.net/bitfan/article/details/6128391 .NET Windows ...

  5. spoj 178

    Output adjacent points   It's simpler ....... #include <cstdio> #include <cstring> using namespace std; int main ...

  6. struts2 be based on Convention The Convention mapping of plug-ins uses

    One . First of all, let's make a point : So called based on Convention The Convention of plug-in is better than the use of configuration , It's not strictly zero configuration ,struts.xml Files are not completely discarded . get Convention Plug in features , Necessary jar Package has a :|a ...

  7. CUDA Programming -(3) The age of graphic pipeline

    The age of graphic pipeline The vertex in the graph , It's a polygonal angle .GeForce The purpose of series design graphics pipeline is to render the primitive elements of triangles , This is the angle of the triangle element . The smaller the triangle element is , The better the quality of the picture . The role of vertex control : from CPU in , Accept parameters ...

  8. OpenSceneGraph Several important function node exercises

    OpenSceneGraph Several important function node exercises One . Space transformation node The most important thing in space transformation is coordinate system and matrix operation .OSG Use the right-handed system in the coordinate system ,Z The axis is vertical up ,X The axis is horizontal to the right ,Y The axis is vertical and the screen is inward , And OpenGL and D ...

  9. Use @contextmanager The decorator implements the context manager

    Generally speaking , Implement the context manager , You need to write a program with __enter__ and __exit__ Class , Like this : class ListTransaction: def __init__(self, orig_lis ...

  10. Soft engineering practice —— Team work requirements specification —— Prototype UI Design

    Login screen It also includes the ability to forget your password and register The registration screen After successful registration, there will be a pop-up window prompt , And a mobile phone number can only be registered once . Forget the password interface Change the password through the verification code received by the mobile phone . Project interface The page after login is the project interface . In the owned interface ...