洛谷P1343地震逃生

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

最大流问题，FF算法：

链式前向星建边，异或来求反向边。

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
const int N=2e3+86;
struct edge{int to,nxt,w;}e[N*2];int hd[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;
bitset<286> vis;

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n>>m>>x;
    f(i,1,m){
        int x,y,val;
        cin>>x>>y>>val;
        add(x,y,val);
        add(y,x,0);
    }
    LL ans=0,c;
    while((c=dfs(1,3e8))!=-1){
        vis.reset();
        //cout<<c<<"\n";
        ans+=c;
    }
    if(ans){
    cout<<ans<<" ";
    cout<<(x/ans+(x%ans?1:0));}
    else cout<<"Orz Ni Jinan Saint Cow!";
    return 0;
}