求最大网络流（最小割）总结

mrh929

6 年前

求最大网络流总结

一个有向图，每条边都有最大可能的数据传输量c，要求一个点到某个点一次能传输的最大数据量，即为求最大网络流，每条边实际的数据传输量称为流量。

基本思路：使用贪心算法，每次找出能使总流量更大的边，将数据向那条边流。

Ford-fulkerson算法

读入所有有向边，并且加入流量为0的反向边
DFS查找所有点u的未被遍历的边(u,v)
如果满足这条边流量大于0，更新这条边以及它的反向边的流量（同时会DFS遍历v点）
重复2操作，直到所有点被遍历完成

算法复杂度：O(m+n)≈O(n^2)

Dinic算法

原理：利用BFS求最短路的方法将所有的边按从源点到汇点的距离排序，从而避免不必要的增广

BFS求源点到所有点的距离
DFS 遍历所有边(u,v)
如果dis[v]==dis[u]+1且边的长度大于0，那么更新这条边以及它的反向边的流量（同时DFS遍历了v点）

用dis数组的好处：不仅减少了不必要的增广步骤，而且使增广顺序有序，不必记录点是否已被遍历

重复2操作，直到没有符合条件的边为止
算法复杂度：O(n^2*m)。（最坏情况，平均情况大大优于FF算法）

割

在网络中，将源点与汇点通过割边的方式划分成两个部分，割掉的所有边都是割，其中，s到t为正向割边，t到s为逆向割边

割的容量：所有正向割边的容量和

最小割：容量和最小的割

定理1：如果f是网络中的一个流，那么f的流为割的正向边与逆向边容量之差

定理二：如果f是一个流，CUT (S,T)是一个割，且f的值等于割CUT(S,T)的容量，那么f是一个最大流，CUT(S,T)是一个最小割。

推论：f的流量<=此流的割的容量

求最小割与求最大网络流等价

POJ 1273 Drainage Ditches

Description

Every time itrains on Farmer John's fields, a pond forms over Bessie's favorite cloverpatch. This means that the clover is covered by water for awhile and takesquite a long time to regrow. Thus, Farmer John has built a set of drainageditches so that Bessie's clover patch is never covered in water. Instead, thewater is drained to a nearby stream. Being an ace engineer, Farmer John hasalso installed regulators at the beginning of each ditch, so he can control atwhat rate water flows into that ditch.
Farmer John knows not only how many gallons of water each ditch can transportper minute but also the exact layout of the ditches, which feed out of the pondand into each other and stream in a potentially complex network.
Given all this information, determine the maximum rate at which water can betransported out of the pond and into the stream. For any given ditch, waterflows in only one direction, but there might be a way that water can flow in acircle.

Input

The input includesseveral cases. For each case, the first line contains twospace-separated integers, N (0 <= N <= 200) and M (2 <= M <= 200).N is the number of ditches that Farmer John has dug. M is the number of intersectionspoints for those ditches. Intersection 1 is the pond. Intersection point M isthe stream. Each of the following N lines contains three integers, Si, Ei, andCi. Si and Ei (1 <= Si, Ei <= M) designate the intersections betweenwhich this ditch flows. Water will flow through this ditch from Si to Ei. Ci (0<= Ci <= 10,000,000) is the maximum rate at which water will flow throughthe ditch.

Output

For each case,output a single integer, the maximum rate at which water may emptied from thepond.

Sample Input

5 4

1 2 40

1 4 20

2 4 20

2 3 30

3 4 10

Sample Output

题意

现在有m个池塘(从1到m开始编号,1为源点,m为汇点),及n条水渠,给出这n条水渠所连接的点和所能流过的最大流量，

Ford-Fulkerson算法

#include
#include
#include
using namespace std;
const int MAX=600;
int first[MAX],nxt[MAX],go[MAX],flow[MAX],arcnum=1;
int vis[MAX];
void addarc(int a,int b,int c){//加边 
    nxt[++arcnum]=first[a];
    first[a]=arcnum;
    go[arcnum]=b;
    flow[arcnum]=c;//记录该边容量 
}

int Dfs(int u,int t,int minc){//起点u，终点t，整条路径中流量最小为minc
    if(u==t) return minc;
    vis[u]=1;
    for(int p=first[u];p!=0;p=nxt[p]){
        int v=go[p];
        if(!vis[v]&&flow[p]>0){
            int f=Dfs(v,t,min(minc,flow[p]));
            if(f>0){
                flow[p]-=f;//正向边减去算出的流量 
                flow[p^1]+=f;//逆向边加上算出的流量
                /* n为任意偶自然数，那么n^1=n+1;(n+1)^1=n    */
                return f; 
            }
        }
    }
    return 0;//如果都不符合条件，返回0 
}

int MaxFlow(int s,int t){
    int ans=0;
    while(1){
        memset(vis,0,sizeof(vis));
        int f=Dfs(s,t,99999999);
        if(f<=0) return ans;
        ans+=f;
    }
}

int main()
{
//   freopen("in.txt","r",stdin);
    int n,m,a,b,c;
    while(scanf("%d%d",&m,&n)!=EOF){
        memset(first,0,sizeof(first));
        memset(flow,0,sizeof(flow));
        arcnum=1;
        for(int i=1;i<=m;i++){
            scanf("%d%d%d",&a,&b,&c);
            addarc(a,b,c);//正向边流量为c 
            addarc(b,a,0);//逆向边流量为0 
        }
        printf("%d\n",MaxFlow(1,n));
    }
    
    return 0;
}

Dinic算法

#include
#include
#include
#include
using namespace std;
const int MAX=600;
const int INF=99999999;
int first[MAX],go[MAX],nxt[MAX],flow[MAX],arcnum=1;
int que[MAX*MAX],dis[MAX],top,rear,current[MAX],vis[MAX];
int n,m,a,b,c;
void addarc(int a,int b,int c){
    nxt[++arcnum]=first[a];
    first[a]=arcnum;
    go[arcnum]=b;
    flow[arcnum]=c;
}

int DFS(int u,int t,int minc){
//   printf("dfs %d %d start\n",u,t);
    if(u==t) return minc;
    for(int p=current[u];p!=0;p=nxt[p]){
    
        current[u]=p;
        int v=go[p]; 
//       printf("%d: %d->%d\n",p,u,v);
        if(dis[v]==dis[u]+1&&flow[p]>0){//边一定要存在 
            int f=DFS(v,t,min(minc,flow[p]));
            if(f){
                flow[p]-=f;
                flow[p^1]+=f;
                return f;
            }
        }
    }
    return 0;
}

int BFS(int s,int t){//BFS优化 
    for(int i=1;i<=MAX;i++)
        dis[i]=INF;
    top=rear=0;
    que[rear++]=s;
    dis[s]=1;
    do{
        int u=que[top++],v;
        for(int p=first[u];p!=0;p=nxt[p]){
            v=go[p];
            if(flow[p]>0&&dis[v]==INF){//边存在且点未被更新时才更新 
                dis[v]=dis[u]+1;
                que[rear++]=v;
            }
        }
    }while(top!=rear);
    return dis[t]int MaxFlow(int s,int t){//Dinic算法 
    int ans=0,f;
    
    while(BFS(s,t)){
        for(int i=1;i<=n;i++)
            current[i]=first[i];//每次BFS后都要重置current数组
        while(f=DFS(s,t,INF))
            ans+=f;
    }
        
    return ans;
}

int main(){
    freopen("in.txt","r",stdin);
    while(scanf("%d%d",&m,&n)!=EOF){
        memset(first,0,sizeof(first));
        memset(flow,0,sizeof(flow));
        arcnum=1;
        for(int i=1;i<=m;i++){
            scanf("%d%d%d",&a,&b,&c);
            addarc(a,b,c);
            addarc(b,a,0);
        }
/*       for(int i=1;i<=n;i++){
            printf("%d %d\n",i,first[i]);
        }
        printf("node end\n");
        for(int i=1;i<=2*m;i++){
            printf("%d %d %d\n",i,go[i],nxt[i]);
        }
        printf("edge end\n");*/
        printf("%d\n",MaxFlow(1,n));
    }

    return 0;
}

HDU4183 Pahom on Water

Problem Description

Pahom on Water isan interactive computer game inspired by a short story of Leo Tolstoy about apoor man who, in his lust for land, forfeits everything. The game's startingscreen displays a number of circular pads painted with colours from the visiblelight spectrum. More than one pad may be painted with the same colour (definedby a certain frequency) except for the two colours red and violet. The displaycontains only one red pad (the lowest frequency of 400 THz) and one violet pad(the highest frequency of 789 THz). A pad may intersect, or even containanother pad with a different colour but never merely touch its boundary. Thedisplay also shows a figure representing Pahom standing on the red pad.
The game's objective is to walk the figure of Pahom from the red pad to theviolet pad and return back to the red pad. The walk must observe the followingrules:
1.If pad α and pad β have a common intersection and the frequency of the colourof pad α is strictly smaller than the frequency of the colour of pad β, thenPahom figure can walk from α to β during the walk from the red pad to theviolet pad
2. If pad α and pad β have a common intersection and the frequency of thecolour of pad α is strictly greater than the frequency of the colour of pad β,then Pahom figure can walk from α to β during the walk from the violet pad tothe red pad
3. A coloured pad, with the exception of the red pad, disappears from displaywhen the Pahom figure walks away from it.
The developer of the game has programmed all the whizzbang features of thegame. All that is left is to ensure that Pahom has a chance to succeed in eachinstance of the game (that is, there is at least one valid walk from the redpad to the violet pad and then back again to the red pad.) Your task is towrite a program to check whether at least one valid path exists in eachinstance of the game.

Input

The input startswith an integer K (1 <= K <= 50) indicating the number of scenarios on aline by itself. The description for each scenario starts with an integer N (2<= N <= 300) indicating the number of pads, on a line by itself, followedby N lines that describe the colors, locations and sizes of the N pads. Eachline contains the frequency, followed by the x- and y-coordinates of the pad'scenter and then the radius. The frequency is given as a real value with no morethan three decimal places. The coordinates and radius are given, in meters, asintegers. All values are separated by a single space. All integer values are inthe range of -10,000 to 10,000 inclusive. In each scenario, all frequencies arein the range of 400.0 to 789.0 inclusive. Exactly one pad will have a frequencyof “400.0” and exactly one pad will have a frequency of “789.0”.

Output

The output foreach scenario consists of a single line that contains: Game is VALID, or Gameis NOT VALID

Sample Input

400.0 0 0 4

789.0 7 0 2

400.0 0 0 4

789.0 7 0 2

500.35 5 0 2

500.32 5 0 3

Sample Output

Game is NOT VALID

Game is VALID

题目大意：

有多个点，每个点给出坐标与半径，加入两个点相交，就可以从这两个点走。题目要求先从起点到终点，再从终点回到起点。从起点到终点的过程中，只能从频率小的走到频率大的点（前提是两点相交），从终点到起点的过程中，只能从频率大的走到频率小的。在走的过程中，除了起点与终点，别的只要走过就会消失，就是说只能走一次。问可不可以从起点到终点又回到起点。

找到输入数据中最小和最大的两个，求两个之间的最大网络流

#include
#include
#include
#include
using namespace std;
const int INF=99999999;
const int MAX=1500;
double data[MAX];
int first[MAX],go[MAX],nxt[MAX],arcnum=1,x[MAX],y[MAX],r[MAX];
int flow[MAX],que[MAX],top,rear,dis[MAX],vis[MAX];
int k,n,ans;
void addarc(int a,int b,int c){
    nxt[++arcnum]=first[a];
    first[a]=arcnum;
    go[arcnum]=b;
    flow[arcnum]=c;
}

int DFS(int u,int t,int minc){
    if(u==t) return minc;
    for(int p=first[u];p!=0;p=nxt[p]){
        int v=go[p],f;
        if(dis[v]==dis[u]+1&&flow[p]>0)
            if(f=DFS(v,t,min(minc,flow[p]))){
                flow[p]-=f;
                flow[p^1]+=f;
                return f;
            }
    }
    return 0;
}

int BFS(int s,int t){
    for(int i=1;i<=n;i++)
        dis[i]=INF;
    top=rear=0;
    que[rear++]=s;
    dis[s]=0;
    do{
        int u=que[top++],v;
        for(int p=first[u];p!=0;p=nxt[p]){
            v=go[p];
            if(dis[v]==INF&&flow[p]>0){
                dis[v]=dis[u]+1;
                que[rear++]=v;
            }
        }
    }while(top!=rear);
    return dis[t]int MaxFlow(int s,int t){
    int ans=0,f;
    while(BFS(s,t))
        while(f=DFS(s,t,INF))
            ans+=f;
    return ans;
}

int main()
{
//   freopen("in.txt","r",stdin);
    scanf("%d",&k);
    while(k--){
        memset(flow,0,sizeof(flow));
        memset(first,0,sizeof(first));
        arcnum=1;
        scanf("%d",&n);
        int red=0,purple=n+1;
        data[0]=9999; data[n+1]=0;
        for(int i=1;i<=n;i++){
            scanf("%f%d%d%d",&data[i],&x[i],&y[i],&r[i]);
            if(data[i]if(data[i]>data[purple]) purple=i;
        }
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                if(data[i]sqrt((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j]))<=r[i]+r[j])
                    addarc(i,j,1),addarc(j,i,0);
        if(MaxFlow(red,purple)<2) printf("Game is NOT VALID\n");
        else printf("Game is VALID\n");   
    }
    
    
    return 0;
}