洛谷P1343地震逃生_Dinic

发表于 更新于 分类于 本文字数： 384 阅读时长 ≈ 1 分钟

洛谷P1343最大流问题的Dinic解法，bfs分层然后dfs增广，还得捋捋弧优化

因为在Dinic算法中，一条边增广一次后就不会再次增广了，所以下次增广时不需要再考虑这条边。我们把head数组复制一份，但不断更新增广的起点。

UPD:原来是这里写错了 
1
for(int eg=hd[p];eg;eg=e[eg].nxt)
 应该是 
1
for (int eg = cur[p]; eg && r; eg = e[eg].nxt)
于是对于每次dfs完之后，cur数组指向该点上次dfs的边下标 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
const int N=2e3+86;
struct edge{int to,nxt,w;}e[N*2];int hd[N],cur[N],tot=1;
void add(int u,int v,int w){
	e[++tot]=(edge){v,hd[u],w}; hd[u]=tot;
}
int n,m,x,lv[N];

int bfs(){
    memset(lv,0,sizeof(lv));
    memcpy(cur, hd, sizeof(hd)); // 当前弧优化初始化
    queue<int> q;
    q.push(1);
    lv[1]=1;
    while(!q.empty()){
        int p=q.front();
        q.pop();
        for(int eg=hd[p];eg;eg=e[eg].nxt){
            int to=e[eg].to,vol=e[eg].w;
            if(vol&&!lv[to]){
                lv[to]=lv[p]+1,q.push(to);
            }
        }
    }
    return  lv[n];
}

int dfs(int p,int flow){
    if(p==n)
    return flow;
    int r=flow;
    for (int eg = cur[p]; eg && r; eg = e[eg].nxt){
        cur[p]=eg;
        int to = e[eg].to, vol = e[eg].w;
        if(vol&&lv[to]==lv[p]+1){
            int c=dfs(to,min(r,vol));
            r-=c;
            e[eg].w-=c;
            e[eg^1].w+=c;
        }
    }
    return flow-r;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m>>x;
    f(i,1,m){
        int aa,bb,cc;
        cin>>aa>>bb>>cc;
        add(aa,bb,cc);
        add(bb,aa,0);
    }
    LL ans=0;
    while(bfs()){
        ans+=dfs(1,3e8);
    }
    if(ans)cout<<ans<<" "<<(x-1)/ans+1;
    else cout<<"Orz Ni Jinan Saint Cow!";
    return 0;
}