网络瘤

卢本伟！！ · 2020-04-21 10:11:18 · 个人记录

• - 算法 每一次暴力流到底，每次流的边要建反向边。 每一次暴力流出的结果累加至答案。 清零$vis$数组. 枚举时一定不能走流量为$0$与走过的点。 $cout<<ans return$ $0
  • 代码 过
• 过
• 先使用$bfs$跑分层图。 每次多路增广。有好多博客都没有加多路增广。 每次水流只能流向下一层的点。 - 多路增广优化 只要能流出就流出 没得流就暴力跳出，返回流量 - 当前弧优化 如果已经走过，流量肯定会用光，直接跳过。 从没走过的地方开始走。 - 不走优化 如果原来走时就不行了，下一次就不走这条边 - 代码优化

/*      西江月·证明
    即得易见平凡，仿照上例显然。
   留作习题答案略， 读者自证不难。

    反之亦然同理，推论自然成立。
    略去过程QED，由上可知证毕。*/
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
#define kkk register
#define ll long long
#define inf 2147098934832ll
using namespace std;
int read(){int ans=0,f=1;char a=getchar();while(a>'9'||a<'0')f|=a=='-',a=getchar();while(a>='0'&&a<='9')ans=(ans<<3)+(ans<<1)+a-'0',a=getchar();return ans*f;}
//一条long long的黄金分割线-----------------------------------------------------------------------------------------------------------------------------------
int n,m,s,t,first[10005],csp=1,pre[10005],dis[10005],cur[10005];
bool vis[10005];
queue<int>q;
struct edge{
    int u,to,w,nxt;
}e[240005];
void add(int a,int b,int w){
    e[++csp]=edge{a,b,w,first[a]};
    first[a]=csp;
}
bool bfs(int s,int t){
    for(int i=1;i<=n;i++)dis[i]=2e9,cur[i]=first[i],vis[i]=0;
    dis[s]=0;q.push(s);
    while(!q.empty()){
        int u=q.front();q.pop();
        for(int i=first[u];i;i=e[i].nxt){
            int v=e[i].to;
            if(dis[u]+1<dis[v]&&e[i].w)
                dis[v]=dis[u]+1,q.push(v);
        }
    }
    return dis[t]!=2e9;
}
int dfs(int now,int t,int flew){
    if(now==t)return flew;
    int ans=0;
    for(int i=cur[now];i;i=e[i].nxt){
        cur[now]=i;
        int v=e[i].to,w=e[i].w;
        if(e[i].w&&dis[now]+1==dis[v]&&!vis[v]){
            int now_ans=dfs(v,t,min(w,flew));
            ans+=now_ans;
            flew-=now_ans;
            e[i].w-=now_ans;
            e[i^1].w+=now_ans;
            if(!flew)break;
        }
    }
    if(ans==0)vis[now]=1;
    return ans;
}
int dinic(int s,int t){
    int ans=0;
    while(bfs(s,t))
        ans+=dfs(s,t,2e9);
    return ans;
}
int main(){
    n=read();m=read();s=read();t=read();
    for(int i=1;i<=m;i++){
        int u=read(),v=read(),w=read();
        add(u,v,w);
        add(v,u,0);
    }
    cout<<dinic(s,t);
    return 0;
}
/*
 * ┌───┐   ┌───┬───┬───┬───┐ ┌───┬───┬───┬───┐ ┌───┬───┬───┬───┐ ┌───┬───┬───┐
 * │Esc│   │ F1│ F2│ F3│ F4│ │ F5│ F6│ F7│ F8│ │ F9│F10│F11│F12│ │P/S│S L│P/B│  ┌┐    ┌┐    ┌┐
 * └───┘   └───┴───┴───┴───┘ └───┴───┴───┴───┘ └───┴───┴───┴───┘ └───┴───┴───┘  └┘    └┘    └┘
 * ┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───────┐ ┌───┬───┬───┐ ┌───┬───┬───┬───┐
 * │~ `│! 1│@ 2│# 3│$ 4│% 5│^ 6│& 7│* 8│( 9│) 0│_ -│+ =│ BacSp │ │Ins│Hom│PUp│ │Num│ / │ * │ - │
 * ├───┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─────┤ ├───┼───┼───┤ ├───┼───┼───┼───┤
 * │ Tab │ Q │ W │ E │ R │ T │ Y │ U │ I │ O │ P │{ [│} ]│ | \ │ │Del│End│PDn│ │ 7 │ 8 │ 9 │   │
 * ├─────┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴┬──┴─────┤ └───┴───┴───┘ ├───┼───┼───┤ + │
 * │ Caps │ A │ S │ D │ F │ G │ H │ J │ K │ L │: ;│" '│ Enter  │               │ 4 │ 5 │ 6 │   │
 * ├──────┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴─┬─┴────────┤     ┌───┐     ├───┼───┼───┼───┤
 * │ Shift  │ Z │ X │ C │ V │ B │ N │ M │< ,│> .│? /│  Shift   │     │ ↑ │     │ 1 │ 2 │ 3 │   │
 * ├─────┬──┴─┬─┴──┬┴───┴───┴───┴───┴───┴──┬┴───┼───┴┬────┬────┤ ┌───┼───┼───┐ ├───┴───┼───┤ E││
 * │ Ctrl│ Win│ Alt│         Space         │ Alt│ Win│Menu│Ctrl│ │ ← │ ↓ │ → │ │   0   │ . │←─┘│
 * └─────┴────┴────┴───────────────────────┴────┴────┴────┴────┘ └───┴───┴───┘ └───────┴───┴───┘
 */

成功肝完网络瘤。Yeah！