您的位置:首页 > 博客中心 > 互联网 >

网络流-最大流 Dinic模板

时间:2022-05-05 01:29

 1 #include 
 2 
 3 using namespace std;
 4 
 5 #define MP make_pair
 6 #define PB push_back
 7 #define ls first
 8 #define rs second
 9 typedef long long LL;
10 typedef pair PII;
11 const double eps=1e-8;
12 const double pi=acos(-1.0);
13 const int K=1e5+7;
14 const int mod=1e9+7;
15 
16 vector>mp[K];
17 int n,m,cnt,flow[K*2],deep[K],cur[K];  
18 
19 int bfs(int s,int t)
20 {
21     queueq;
22     memset(deep,0,sizeof deep);
23     q.push(s),deep[s]=1;
24     while(!q.empty())
25     {
26         int u=q.front();q.pop();
27         for(auto &it:mp[u])
28         if(!deep[it.ls]&&flow[it.rs])
29         {
30             deep[it.ls]=deep[u]+1;
31             q.push(it.ls);
32             if(it.ls==t)
33                 return 1;
34         }
35     }
36     return 0;
37 }
38 int dfs(int x,int d,int t)
39 {
40     if(x==t) return d;
41     for(int i=cur[x];i

 

热门排行

今日推荐

热门手游