网络+网络流

访问网络：

域名=URL链接，通过dns解码可以把URL变成ip地址。实际上dns就是一个数据库，里面储存着许多对ip地址和URL。

建立TCP协议，发送HTTP请求，收到HTTP请求的响应。

HTTP的响应：404表示响应失败，200表示响应成功。

EK算法：

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
typedef long long ll;
const int M=200005,N=10005;
struct{ll v,w,ne;}e[M];
int h[N],idx=1;//从2开始编号，23是一对，45是一对
int n,m,s,t;
ll pre[N],mf[N];// mf指最大容量
void add(int a,int b,int c){
    e[++idx]={b,c,h[a]};
    h[a]=idx;
}
bool bfs(){
    memset(mf,0,sizeof mf);
    queue<int>q;
    q.push(s);mf[s]=1e9;
    while(q.size()){
        int u=q.front();q.pop();
        for(int i=h[u];i;i=e[i].ne){
            ll v=e[i].v;
            if(!mf[v]&&e[i].w){
                mf[v]=min(mf[u],e[i].w);
                pre[v]=i;// 前驱边
                q.push(v);
                if(v==t)return true;
            }
        }
    }
    return false;
}// 找增广路
ll ek(){
    ll flow=0;
    while(bfs()){
        int v=t;
        while(v!=s){
            int i=pre[v];
            e[i].w-=mf[t];
            e[i^1].w+=mf[t];
            v=e[i^1].v;
        }
        flow+=mf[t];
    }
    return flow;
}// 累加可行流
int main(){
    cin.tie(0);
    cin.sync_with_stdio(false);
    cin>>n>>m>>s>>t;
    int a,b,c;
    while(m--){
        cin>>a>>b>>c;
        add(a,b,c);
        add(b,a,0);
    }
    cout<<ek();
    return 0;
}

Dinic算法：宽搜+深搜的完美结合

在稀疏图中，EK和dinic都是O(N3),在稠密图中， dinic更好，总而言之，dinic更好；

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
typedef long long ll;
const int M=200005,N=10005;
int n,m,s,t;
struct edge{ll v,w,ne;}e[M];
int h[N],idx=1;// 从2，3开始编号，2，3是一对
int d[N],cur[N];// d是层数
void add(int a,int b,int c){
    e[++idx]={b,c,h[a]};
    h[a]=idx;
}
bool bfs(){// 对点分层，找增广路
    memset(d,0,sizeof(d));
    queue<int>q;
    q.push(s);d[s]=1;
    while(q.size()){
        int u=q.front();q.pop();
        for(int i=h[u];i;i=e[i].ne){
            int v=e[i].v;
            if(d[v]==0&&e[i].w){
                d[v]=d[u]+1;
                q.push(v);
                if(v==t)return true;
            }
        }
    }
    return false;
}
ll dfs(int u,ll mf){// 多路增广,mf指max flow，最大流
    if(u==t)return mf;
    ll sum=0;// 这个点流出去的流量总量
    for(int i=cur[u];i;i=e[i].ne){
        cur[u]=i;// 当前弧优化，下一次找寻流量时跳过那些已经检查过的弧
        int v=e[i].v;
        if(d[v]==d[u]+1&&e[i].w){
            ll f=dfs(v,min(e[i].w,mf));
            e[i].w-=f;
            e[i^1].w+=f;
            sum+=f;
            mf-=f;
            if(mf==0)break;// 余量优化
        }
    }
    if(sum==0)d[u]=0;// 残枝优化：此路不通，下次别找这条路了
    return sum;
}
ll dinic(){
    ll flow=0;
    while(bfs()){
        memcpy(cur,h,sizeof(h));
        flow+=dfs(s,1e9);
    }
    return flow;
}
int main(){
    cin.tie(0);
    cin.sync_with_stdio(false);
    cin>>n>>m>>s>>t;
    int a,b,c;
    while(m--){
        cin>>a>>b>>c;
        add(a,b,c);
        add(b,a,0);
    }
    cout<<dinic();
    return 0;
}